Mixing
'Low-algebra' examples of induction
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
What are good examples of proofs by induction that are relatively low on algebra? Examples might include simple results about graphs.
My aim is to help students get a sense of the logical form of an induction proof (in particular proving a statement of the form 'if $P(k)$ then $P(k+1)$'), independent of the way one might show that in a proof about series formulae specifically.
secondary-education induction
asked 4 hours ago
dbmag9
1855
 |Â
show 1 more comment
up vote
2
down vote
favorite
What are good examples of proofs by induction that are relatively low on algebra? Examples might include simple results about graphs.
My aim is to help students get a sense of the logical form of an induction proof (in particular proving a statement of the form 'if $P(k)$ then $P(k+1)$'), independent of the way one might show that in a proof about series formulae specifically.
secondary-education induction
asked 4 hours ago
dbmag9
1855
It's not clear what is meant by "series formulae".
– Number
4 hours ago
In a perverse way, the algebra rich nature of series induction can be a feature. Students need to build those muscles. Probably they need overall manipulative skill more than they need the method of induction.
– guest
4 hours ago
@guest Why not write an answer based on that? A frame challenge is an acceptable answer, though popularity varies more than with more usual answers.
– Tommi Brander
3 hours ago
@Number For example, proving that the sum of the first $n$ natural numbers is given by $frac12 n(n+1)$.
– dbmag9
1 hour ago
@dbmag9 Perhaps you means telescopy, i.e. inductive telescopic cancellation.
– Number
1 hour ago
 |Â
show 1 more comment
up vote
2
down vote
favorite
up vote
2
down vote
favorite
What are good examples of proofs by induction that are relatively low on algebra? Examples might include simple results about graphs.
My aim is to help students get a sense of the logical form of an induction proof (in particular proving a statement of the form 'if $P(k)$ then $P(k+1)$'), independent of the way one might show that in a proof about series formulae specifically.
secondary-education induction
asked 4 hours ago
dbmag9
1855
What are good examples of proofs by induction that are relatively low on algebra? Examples might include simple results about graphs.
My aim is to help students get a sense of the logical form of an induction proof (in particular proving a statement of the form 'if $P(k)$ then $P(k+1)$'), independent of the way one might show that in a proof about series formulae specifically.
secondary-education induction
secondary-education induction
asked 4 hours ago
dbmag9
1855
asked 4 hours ago
dbmag9
1855
asked 4 hours ago
dbmag9
1855
asked 4 hours ago
dbmag9
1855
asked 4 hours ago
dbmag9
1855
1855
It's not clear what is meant by "series formulae".
– Number
4 hours ago
In a perverse way, the algebra rich nature of series induction can be a feature. Students need to build those muscles. Probably they need overall manipulative skill more than they need the method of induction.
– guest
4 hours ago
@guest Why not write an answer based on that? A frame challenge is an acceptable answer, though popularity varies more than with more usual answers.
– Tommi Brander
3 hours ago
@Number For example, proving that the sum of the first $n$ natural numbers is given by $frac12 n(n+1)$.
– dbmag9
1 hour ago
@dbmag9 Perhaps you means telescopy, i.e. inductive telescopic cancellation.
– Number
1 hour ago
 |Â
show 1 more comment
It's not clear what is meant by "series formulae".
– Number
4 hours ago
In a perverse way, the algebra rich nature of series induction can be a feature. Students need to build those muscles. Probably they need overall manipulative skill more than they need the method of induction.
– guest
4 hours ago
@guest Why not write an answer based on that? A frame challenge is an acceptable answer, though popularity varies more than with more usual answers.
– Tommi Brander
3 hours ago
@Number For example, proving that the sum of the first $n$ natural numbers is given by $frac12 n(n+1)$.
– dbmag9
1 hour ago
@dbmag9 Perhaps you means telescopy, i.e. inductive telescopic cancellation.
– Number
1 hour ago
It's not clear what is meant by "series formulae".
– Number
4 hours ago
It's not clear what is meant by "series formulae".
– Number
4 hours ago
In a perverse way, the algebra rich nature of series induction can be a feature. Students need to build those muscles. Probably they need overall manipulative skill more than they need the method of induction.
– guest
4 hours ago
In a perverse way, the algebra rich nature of series induction can be a feature. Students need to build those muscles. Probably they need overall manipulative skill more than they need the method of induction.
– guest
4 hours ago
@guest Why not write an answer based on that? A frame challenge is an acceptable answer, though popularity varies more than with more usual answers.
– Tommi Brander
3 hours ago
@guest Why not write an answer based on that? A frame challenge is an acceptable answer, though popularity varies more than with more usual answers.
– Tommi Brander
3 hours ago
@Number For example, proving that the sum of the first $n$ natural numbers is given by $frac12 n(n+1)$.
– dbmag9
1 hour ago
@Number For example, proving that the sum of the first $n$ natural numbers is given by $frac12 n(n+1)$.
– dbmag9
1 hour ago
@dbmag9 Perhaps you means telescopy, i.e. inductive telescopic cancellation.
– Number
1 hour ago
@dbmag9 Perhaps you means telescopy, i.e. inductive telescopic cancellation.
– Number
1 hour ago
 |Â
show 1 more comment
5 Answers
5
active
oldest
votes
up vote
1
down vote
How about: A tree with $nge 1$ vertices has $n-1$ edges.
answered 3 hours ago
Aeryk
3,623630
add a comment |Â
up vote
1
down vote
A couple of simple examples come to mind:
1) Prove that there are $2^n$ subsets of an $n$-element set.
2) Prove the power rule of derivatives for non-negative integer powers using the product rule.
answered 3 hours ago
John Coleman
1,276411
add a comment |Â
up vote
1
down vote
I think tiling problems are good for this kind of thing. See, for example, this. There they describe how to prove the statement "if you have a $2^ntimes 2^n$ chessboard with one square missing, then you can tile it with L-shaped trominoes." There are other tiling questions, as well, such as the ones here that deal with triangular chessboards and trominoes. Yet others ask students to count the number of ways to tile something (e.g., here) via linear recurrences (which usually can easily be proved inductively).
answered 3 hours ago
ncr
2,546189
add a comment |Â
up vote
1
down vote
Tiling problems might meet your constraints. A nice simple example is Golomb's Theorem that a chessboard of side $2^n$ with any square omitted can be tiled by trominoes ("L" shapes of 3 squares).
In fact we can modify it to give an example of how strengthening the induction hypothesis is often needed: simply replace "any square omitted" by "central square omitted".
The induction step is easy and vivid: divide the board into four smaller $2^n-1$ boards. By induction we can tile the board with the missing (pink) square, and we can tile the other three omitting their (purple) corner squares (in the center of the big square), leaving 3 central squares that form an "L", which we tile with one final tromino.
answered 2 hours ago
Number
6581610
How can you "prove" that if the students don't have a logic class? ;)
– guest
2 hours ago
Presumably you're joking about the prior question on that topic. But that's a different question(er). Btw, ncr's answer wasn't there when I loaded the page, but since it doesn't mention the "strengthening" part I will leave this.
– Number
1 hour ago
add a comment |Â
up vote
0
down vote
How about the Tower of Hanoi puzzle and finding the optimal number of moves?
This link describes the recursive solution procedure and a proof of optimality using induction.
https://proofwiki.org/wiki/Tower_of_Hanoi
answered 17 mins ago
Brendan W. Sullivan
6,8892564
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
How about: A tree with $nge 1$ vertices has $n-1$ edges.
answered 3 hours ago
Aeryk
3,623630
add a comment |Â
up vote
1
down vote
How about: A tree with $nge 1$ vertices has $n-1$ edges.
answered 3 hours ago
Aeryk
3,623630
add a comment |Â
up vote
1
down vote
up vote
1
down vote
How about: A tree with $nge 1$ vertices has $n-1$ edges.
answered 3 hours ago
Aeryk
3,623630
How about: A tree with $nge 1$ vertices has $n-1$ edges.
answered 3 hours ago
Aeryk
3,623630
answered 3 hours ago
Aeryk
3,623630
answered 3 hours ago
Aeryk
3,623630
answered 3 hours ago
Aeryk
3,623630
3,623630
add a comment |Â
add a comment |Â
up vote
1
down vote
A couple of simple examples come to mind:
1) Prove that there are $2^n$ subsets of an $n$-element set.
2) Prove the power rule of derivatives for non-negative integer powers using the product rule.
answered 3 hours ago
John Coleman
1,276411
add a comment |Â
up vote
1
down vote
A couple of simple examples come to mind:
1) Prove that there are $2^n$ subsets of an $n$-element set.
2) Prove the power rule of derivatives for non-negative integer powers using the product rule.
answered 3 hours ago
John Coleman
1,276411
add a comment |Â
up vote
1
down vote
up vote
1
down vote
A couple of simple examples come to mind:
1) Prove that there are $2^n$ subsets of an $n$-element set.
2) Prove the power rule of derivatives for non-negative integer powers using the product rule.
answered 3 hours ago
John Coleman
1,276411
A couple of simple examples come to mind:
1) Prove that there are $2^n$ subsets of an $n$-element set.
2) Prove the power rule of derivatives for non-negative integer powers using the product rule.
answered 3 hours ago
John Coleman
1,276411
answered 3 hours ago
John Coleman
1,276411
answered 3 hours ago
John Coleman
1,276411
answered 3 hours ago
John Coleman
1,276411
1,276411
add a comment |Â
add a comment |Â
up vote
1
down vote
I think tiling problems are good for this kind of thing. See, for example, this. There they describe how to prove the statement "if you have a $2^ntimes 2^n$ chessboard with one square missing, then you can tile it with L-shaped trominoes." There are other tiling questions, as well, such as the ones here that deal with triangular chessboards and trominoes. Yet others ask students to count the number of ways to tile something (e.g., here) via linear recurrences (which usually can easily be proved inductively).
answered 3 hours ago
ncr
2,546189
add a comment |Â
up vote
1
down vote
I think tiling problems are good for this kind of thing. See, for example, this. There they describe how to prove the statement "if you have a $2^ntimes 2^n$ chessboard with one square missing, then you can tile it with L-shaped trominoes." There are other tiling questions, as well, such as the ones here that deal with triangular chessboards and trominoes. Yet others ask students to count the number of ways to tile something (e.g., here) via linear recurrences (which usually can easily be proved inductively).
answered 3 hours ago
ncr
2,546189
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I think tiling problems are good for this kind of thing. See, for example, this. There they describe how to prove the statement "if you have a $2^ntimes 2^n$ chessboard with one square missing, then you can tile it with L-shaped trominoes." There are other tiling questions, as well, such as the ones here that deal with triangular chessboards and trominoes. Yet others ask students to count the number of ways to tile something (e.g., here) via linear recurrences (which usually can easily be proved inductively).
answered 3 hours ago
ncr
2,546189
I think tiling problems are good for this kind of thing. See, for example, this. There they describe how to prove the statement "if you have a $2^ntimes 2^n$ chessboard with one square missing, then you can tile it with L-shaped trominoes." There are other tiling questions, as well, such as the ones here that deal with triangular chessboards and trominoes. Yet others ask students to count the number of ways to tile something (e.g., here) via linear recurrences (which usually can easily be proved inductively).
answered 3 hours ago
ncr
2,546189
answered 3 hours ago
ncr
2,546189
answered 3 hours ago
ncr
2,546189
answered 3 hours ago
ncr
2,546189
2,546189
add a comment |Â
add a comment |Â
up vote
1
down vote
Tiling problems might meet your constraints. A nice simple example is Golomb's Theorem that a chessboard of side $2^n$ with any square omitted can be tiled by trominoes ("L" shapes of 3 squares).
In fact we can modify it to give an example of how strengthening the induction hypothesis is often needed: simply replace "any square omitted" by "central square omitted".
The induction step is easy and vivid: divide the board into four smaller $2^n-1$ boards. By induction we can tile the board with the missing (pink) square, and we can tile the other three omitting their (purple) corner squares (in the center of the big square), leaving 3 central squares that form an "L", which we tile with one final tromino.
answered 2 hours ago
Number
6581610
How can you "prove" that if the students don't have a logic class? ;)
– guest
2 hours ago
Presumably you're joking about the prior question on that topic. But that's a different question(er). Btw, ncr's answer wasn't there when I loaded the page, but since it doesn't mention the "strengthening" part I will leave this.
– Number
1 hour ago
add a comment |Â
up vote
1
down vote
Tiling problems might meet your constraints. A nice simple example is Golomb's Theorem that a chessboard of side $2^n$ with any square omitted can be tiled by trominoes ("L" shapes of 3 squares).
In fact we can modify it to give an example of how strengthening the induction hypothesis is often needed: simply replace "any square omitted" by "central square omitted".
The induction step is easy and vivid: divide the board into four smaller $2^n-1$ boards. By induction we can tile the board with the missing (pink) square, and we can tile the other three omitting their (purple) corner squares (in the center of the big square), leaving 3 central squares that form an "L", which we tile with one final tromino.
answered 2 hours ago
Number
6581610
How can you "prove" that if the students don't have a logic class? ;)
– guest
2 hours ago
Presumably you're joking about the prior question on that topic. But that's a different question(er). Btw, ncr's answer wasn't there when I loaded the page, but since it doesn't mention the "strengthening" part I will leave this.
– Number
1 hour ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Tiling problems might meet your constraints. A nice simple example is Golomb's Theorem that a chessboard of side $2^n$ with any square omitted can be tiled by trominoes ("L" shapes of 3 squares).
In fact we can modify it to give an example of how strengthening the induction hypothesis is often needed: simply replace "any square omitted" by "central square omitted".
The induction step is easy and vivid: divide the board into four smaller $2^n-1$ boards. By induction we can tile the board with the missing (pink) square, and we can tile the other three omitting their (purple) corner squares (in the center of the big square), leaving 3 central squares that form an "L", which we tile with one final tromino.
answered 2 hours ago
Number
6581610
Tiling problems might meet your constraints. A nice simple example is Golomb's Theorem that a chessboard of side $2^n$ with any square omitted can be tiled by trominoes ("L" shapes of 3 squares).
In fact we can modify it to give an example of how strengthening the induction hypothesis is often needed: simply replace "any square omitted" by "central square omitted".
The induction step is easy and vivid: divide the board into four smaller $2^n-1$ boards. By induction we can tile the board with the missing (pink) square, and we can tile the other three omitting their (purple) corner squares (in the center of the big square), leaving 3 central squares that form an "L", which we tile with one final tromino.
answered 2 hours ago
Number
6581610
answered 2 hours ago
Number
6581610
answered 2 hours ago
Number
6581610
answered 2 hours ago
Number
6581610
6581610
How can you "prove" that if the students don't have a logic class? ;)
– guest
2 hours ago
Presumably you're joking about the prior question on that topic. But that's a different question(er). Btw, ncr's answer wasn't there when I loaded the page, but since it doesn't mention the "strengthening" part I will leave this.
– Number
1 hour ago
add a comment |Â
How can you "prove" that if the students don't have a logic class? ;)
– guest
2 hours ago
Presumably you're joking about the prior question on that topic. But that's a different question(er). Btw, ncr's answer wasn't there when I loaded the page, but since it doesn't mention the "strengthening" part I will leave this.
– Number
1 hour ago
How can you "prove" that if the students don't have a logic class? ;)
– guest
2 hours ago
How can you "prove" that if the students don't have a logic class? ;)
– guest
2 hours ago
Presumably you're joking about the prior question on that topic. But that's a different question(er). Btw, ncr's answer wasn't there when I loaded the page, but since it doesn't mention the "strengthening" part I will leave this.
– Number
1 hour ago
Presumably you're joking about the prior question on that topic. But that's a different question(er). Btw, ncr's answer wasn't there when I loaded the page, but since it doesn't mention the "strengthening" part I will leave this.
– Number
1 hour ago
add a comment |Â
up vote
0
down vote
How about the Tower of Hanoi puzzle and finding the optimal number of moves?
This link describes the recursive solution procedure and a proof of optimality using induction.
https://proofwiki.org/wiki/Tower_of_Hanoi
answered 17 mins ago
Brendan W. Sullivan
6,8892564
add a comment |Â
up vote
0
down vote
How about the Tower of Hanoi puzzle and finding the optimal number of moves?
This link describes the recursive solution procedure and a proof of optimality using induction.
https://proofwiki.org/wiki/Tower_of_Hanoi
answered 17 mins ago
Brendan W. Sullivan
6,8892564
add a comment |Â
up vote
0
down vote
up vote
0
down vote
How about the Tower of Hanoi puzzle and finding the optimal number of moves?
This link describes the recursive solution procedure and a proof of optimality using induction.
https://proofwiki.org/wiki/Tower_of_Hanoi
answered 17 mins ago
Brendan W. Sullivan
6,8892564
How about the Tower of Hanoi puzzle and finding the optimal number of moves?
This link describes the recursive solution procedure and a proof of optimality using induction.
https://proofwiki.org/wiki/Tower_of_Hanoi
answered 17 mins ago
Brendan W. Sullivan
6,8892564
answered 17 mins ago
Brendan W. Sullivan
6,8892564
answered 17 mins ago
Brendan W. Sullivan
6,8892564
answered 17 mins ago
Brendan W. Sullivan
6,8892564
6,8892564
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmatheducators.stackexchange.com%2fquestions%2f14552%2flow-algebra-examples-of-induction%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
It's not clear what is meant by "series formulae".
– Number
4 hours ago
In a perverse way, the algebra rich nature of series induction can be a feature. Students need to build those muscles. Probably they need overall manipulative skill more than they need the method of induction.
– guest
4 hours ago
@guest Why not write an answer based on that? A frame challenge is an acceptable answer, though popularity varies more than with more usual answers.
– Tommi Brander
3 hours ago
@Number For example, proving that the sum of the first $n$ natural numbers is given by $frac12 n(n+1)$.
– dbmag9
1 hour ago
@dbmag9 Perhaps you means telescopy, i.e. inductive telescopic cancellation.
– Number
1 hour ago