Author 
Message 
Chris Smith science forum beginner
Joined: 02 Apr 2005
Posts: 11

Posted: Wed Jul 19, 2006 4:38 pm Post subject:
Re: "Cool" inductive proofs



Dirk Van de moortel wrote:
Quote:  The best example with limited algebra is of course
1+2+...+N = 1/2 N (N+1), but if that is still too much
algebra,

The problem here isn't in explaining the theorem, which is simple
enough... but the induction step of the proof is basically made up
entirely of algebraic manipulation.
Quote:  try this one:
How many ways to line up a group of N 14yearolds?

That's a great one. Thanks!

Chris Smith  Lead Software Developer / Technical Trainer
MindIQ Corporation 

Back to top 


Arturo Magidin science forum Guru
Joined: 25 Mar 2005
Posts: 1838

Posted: Wed Jul 19, 2006 4:52 pm Post subject:
Re: "Cool" inductive proofs



In article <MPG.1f2772f07de96a59896a3@news.altopia.net>,
Chris Smith <cdsmith@twu.net> wrote:
Quote:  I am looking for examples of inductive proofs that:
1. Are simple enough to be understood by an average 14yearold.
2. Prove theorems that are easily *understood* by the average teenager,
but won't be too obvious so that the need for a proof is clear.
3. Involve minimal or no algebraic manipulation.

I confess I have never tried the following one in a classroom, but it
seems to satisfy the conditions.
Consider the following simplified game of Nim: there is a pile with N
matchsticks. Two players, A and B, alternate play by taking either 1,
2, or 3 matchsticks away from the pile (their choice). Whoever takes
the last matchstick wins.
You can play a few rounds. Then it is fairly easy to analyze the small
cases: if there is 1, 2, or 3 sticks, the first player wins by taking
all. If there are 4, the second player wins by taking whatever is
left. If there are 5, 6, or 7, the first player can win by reducing
the pile to 4, and then using the "second player strategy" after
that. With 8, the second player wins by reducing the pile to 4 in her
first turn, and so we are back to the case of a 4stick pile.
Note that of one player takes r sticks, then the resulting game is
just the same as before, but with Nr sticks, and with the old "second
player" now being the "first player." I believe this will be the
hardest step to conceptualize (that the 'old second player' is now the
'new first player').
Then you can do the induction, once the cases of 5, 6, 7, and 8 reveal
how to "use what we already know" for smaller piles:
THEOREM. For the game with N sticks, the first player has a winning
strategy if N is not a multiple of 4. If N is a multiple of 4, then
the second player has a winning strategy.
Proof by induction on N: For small N, (1,2,3, and 4), done directly.
Assume the result is true for smaller N. Think of N as being 4k+r,
r=0,1,2,3.
If r is not 0, then the first player takes r sticks. This leaves a
game with 4k sticks, which by induction will be lost by the player who
moves first, this being player B. So player A has a winning strategy
(1. reduce to a multiple of 4 in your first move; 2. use the
secondplayerstrategyformultiplesoffour after that).
If r=0, then regardless of what player A does, player B can use his
turn to leave exactly 4(k1) sticks. By induction, the player
who plays second in this situation (which is player B) has a winning
strategy, so player B has a winning strategy when N=4k.
QED

======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
 Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin 

Back to top 


Jeremy Boden science forum Guru Wannabe
Joined: 28 Apr 2005
Posts: 144

Posted: Wed Jul 19, 2006 5:14 pm Post subject:
Re: "Cool" inductive proofs



On Wed, 20060719 at 09:13 +0000, Richard Tobin wrote:
Quote:  In article <MPG.1f2772f07de96a59896a3@news.altopia.net>,
Chris Smith <cdsmith@twu.net> wrote:
I am looking for examples of inductive proofs that:
1. Are simple enough to be understood by an average 14yearold.
2. Prove theorems that are easily *understood* by the average teenager,
but won't be too obvious so that the need for a proof is clear.
3. Involve minimal or no algebraic manipulation.
Towers of Hanoi: that you can solve it in 2^n  1 moves, and that this
is the shortest solution.
I came across one the other day (proved by induction!) that is 
unbelievably complex (and slightly wrong) in Apostol "Introduction to
Analytic Number Theory"):
"Given any two integers a & b, there is a common divisor, d of a and b
of the form
d = ax + by where x & y are integers.
[Moreover, every common divisor of a and b divides this d]"

Jeremy Boden 

Back to top 


Yiftach Barnea science forum beginner
Joined: 19 Jul 2006
Posts: 1

Posted: Wed Jul 19, 2006 6:22 pm Post subject:
Re: "Cool" inductive proofs



You could prove that Hanoi Towers has a solution using induction. 

Back to top 


Gerry Myerson science forum Guru
Joined: 28 Apr 2005
Posts: 871

Posted: Thu Jul 20, 2006 12:05 am Post subject:
Re: "Cool" inductive proofs



In article <1153329277.10454.8.camel@localhost.localdomain>,
Jeremy Boden <jeremy@jboden.demon.co.uk> wrote:
Quote:  I came across one the other day (proved by induction!) that is
unbelievably complex (and slightly wrong) in Apostol "Introduction to
Analytic Number Theory"):
"Given any two integers a & b, there is a common divisor, d of a and b
of the form
d = ax + by where x & y are integers.
[Moreover, every common divisor of a and b divides this d]"

Apostol's proof comes to 16 lines of text. I guess it's a matter
of opinion, but I don't think that qualifies as "unbelievably
complex." I'm more interested to know what you think is "slightly
wrong" in Apostol?
It's more common to see the proof phrased in terms of wellordering.
Assuming a and b are not both zero (and handling separately the case
where they are both zero), consider all the positive numbers of the
form a x + b y where x and y are integers. There are such (just take
x = a and y = b to see that), so there's a least such; call it d.
Now all we have to do is show that d divides both a and b. By symmetry,
it's enough to show d divides a. Divide a by d, getting a quotient q
and a remainder r, r < d. Then
r = a  d q = a  (a x + b y) q = a X + b Y
where X = 1  x and Y =  q y, so by the hypothesis on d, r = 0.

Gerry Myerson (gerry@maths.mq.edi.ai) (i > u for email) 

Back to top 


msustik@gmail.com science forum beginner
Joined: 20 Jul 2006
Posts: 4

Posted: Thu Jul 20, 2006 3:10 am Post subject:
Re: "Cool" inductive proofs



Chris Smith wrote:
Quote:  I am looking for examples of inductive proofs that:
1. Are simple enough to be understood by an average 14yearold.
2. Prove theorems that are easily *understood* by the average teenager,
but won't be too obvious so that the need for a proof is clear.
3. Involve minimal or no algebraic manipulation.

I have one for you and it comes with a cute story as well.
There is an island on which there are 25 lions and a piece of meat. We
know the following facts:
1. The lions are hungry and they will starve if they do not eat.
2. Once a lion finished eating the piece of meat he becomes very sleepy
and while sleeping he is considered to be a piece of meat by the other
lions.
3. If a lion puts his paw on the meat claiming it, now other lion will
fight to take it away and the meat will not be divided but eaten as a
whole by the lion.
4. The lions are superintelligent. That is they are capable to forsee
the consequence of their actions and are aware of all the facts
described here.
5. If a lion has to choose between starving to death or being eaten
while asleep he will choose starvation.
Question: What will happen on the island? Will a lion eat the piece of
meat?
Enjoy.
Matyas 

Back to top 


Robert B. Israel science forum Guru
Joined: 24 Mar 2005
Posts: 2151

Posted: Thu Jul 20, 2006 4:33 am Post subject:
Re: "Cool" inductive proofs



In article <1153365053.806532.93710@b28g2000cwb.googlegroups.com>,
<msustik@gmail.com> wrote:
Quote:  Chris Smith wrote:
I am looking for examples of inductive proofs that:
1. Are simple enough to be understood by an average 14yearold.
2. Prove theorems that are easily *understood* by the average teenager,
but won't be too obvious so that the need for a proof is clear.
3. Involve minimal or no algebraic manipulation.
I have one for you and it comes with a cute story as well.
There is an island on which there are 25 lions and a piece of meat. We
know the following facts:
1. The lions are hungry and they will starve if they do not eat.
2. Once a lion finished eating the piece of meat he becomes very sleepy
and while sleeping he is considered to be a piece of meat by the other
lions.
3. If a lion puts his paw on the meat claiming it, now other lion will
fight to take it away and the meat will not be divided but eaten as a
whole by the lion.
4. The lions are superintelligent. That is they are capable to forsee
the consequence of their actions and are aware of all the facts
described here.
5. If a lion has to choose between starving to death or being eaten
while asleep he will choose starvation.
Question: What will happen on the island? Will a lion eat the piece of
meat?

Very cute. But there are flaws:
the way you wrote it, a lion that eats the piece of meat
and survives the night will still starve eventually, because there will
be nothing to eat after that (except perhaps other starved lions).
Under the circumstances, would the lion want to prolong the inevitable?
Also, the lion would have to worry about whether another lion will
drop dead of starvation during the night.
Perhaps a less melodramatic formulation would allow the lions to survive
on some other food, say tofu, that is readily available, but they prefer
to eat meat (including lion meat) if they can do so without being eaten
themselves.
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada 

Back to top 


vinay.sri48@gmail.com science forum beginner
Joined: 20 Jul 2006
Posts: 2

Posted: Thu Jul 20, 2006 8:48 am Post subject:
Re: "Cool" inductive proofs



Richard Henry wrote:
Quote:  Chris Smith wrote:
I am looking for examples of inductive proofs that:
1. Are simple enough to be understood by an average 14yearold.
2. Prove theorems that are easily *understood* by the average teenager,
but won't be too obvious so that the need for a proof is clear.
3. Involve minimal or no algebraic manipulation.
The one really good example I've found so far is the ability to tile an
NxN grid with one square removed with Lshaped pieces, provided N is a
power of two. Are there other good examples along these same lines?
Unfortunately, most introductions to induction that I've found seem to
be fieldspecific, or prove closed forms for members of a series; these
aren't suitable for the audience I've got.
The difference between squares of two successive integers is the sum of
the integers. 


Back to top 


vinay.sri48@gmail.com science forum beginner
Joined: 20 Jul 2006
Posts: 2

Posted: Thu Jul 20, 2006 8:50 am Post subject:
Re: "Cool" inductive proofs



msustik@gmail.com wrote:
Quote:  Chris Smith wrote:
I am looking for examples of inductive proofs that:
1. Are simple enough to be understood by an average 14yearold.
2. Prove theorems that are easily *understood* by the average teenager,
but won't be too obvious so that the need for a proof is clear.
3. Involve minimal or no algebraic manipulation.
I have one for you and it comes with a cute story as well.
There is an island on which there are 25 lions and a piece of meat. We
know the following facts:
1. The lions are hungry and they will starve if they do not eat.
2. Once a lion finished eating the piece of meat he becomes very sleepy
and while sleeping he is considered to be a piece of meat by the other
lions.
3. If a lion puts his paw on the meat claiming it, now other lion will
fight to take it away and the meat will not be divided but eaten as a
whole by the lion.
4. The lions are superintelligent. That is they are capable to forsee
the consequence of their actions and are aware of all the facts
described here.
5. If a lion has to choose between starving to death or being eaten
while asleep he will choose starvation.
Question: What will happen on the island? Will a lion eat the piece of
meat?
Enjoy.
Matyas 


Back to top 


Andrew Taylor science forum beginner
Joined: 31 May 2005
Posts: 9

Posted: Thu Jul 20, 2006 10:14 am Post subject:
Re: "Cool" inductive proofs



Chris Smith wrote:
Quote:  I am looking for examples of inductive proofs that:
1. Are simple enough to be understood by an average 14yearold.
2. Prove theorems that are easily *understood* by the average teenager,
but won't be too obvious so that the need for a proof is clear.
3. Involve minimal or no algebraic manipulation.
The one really good example I've found so far is the ability to tile an
NxN grid with one square removed with Lshaped pieces, provided N is a
power of two. Are there other good examples along these same lines?
Unfortunately, most introductions to induction that I've found seem to
be fieldspecific, or prove closed forms for members of a series; these
aren't suitable for the audience I've got.
Thanks,

You could also show them the inductive "proof"
that all numbers are equal, which is a good
object lesson against using induction
carelessly.
We will prove that for any set S_n of n numbers, all
the members of S_n are equal. This is clearly true
for n = 1. Assume it's true for n1, and consider a set
S_n with n members a_1, a_2,...a_n. By the inductive
hypothesis,
a_1 = a_2 = ... = a_(n1)
and also
a_2 = ... = a_(n1) = a_n
so all the member of S_n are equal. 

Back to top 


Catarina Dias science forum beginner
Joined: 18 Jun 2006
Posts: 4

Posted: Thu Jul 20, 2006 11:14 am Post subject:
Re: "Cool" inductive proofs



Hi!
When I started to learn induction in school, my teacher refers a "cool"
variant of Andrew Taylor sugestion, which I think resulted very well,
because is very "suggestive"
The problem is " All blond women have blue eyes"
P(n) = "If in a field of n blond women, one of then has blue eyes, so
all of then have blue eyes"
P(1) is true...
Its exactly what Andrew Taylor said.
Andrew Taylor wrote:
Quote:  Chris Smith wrote:
I am looking for examples of inductive proofs that:
1. Are simple enough to be understood by an average 14yearold.
2. Prove theorems that are easily *understood* by the average teenager,
but won't be too obvious so that the need for a proof is clear.
3. Involve minimal or no algebraic manipulation.
The one really good example I've found so far is the ability to tile an
NxN grid with one square removed with Lshaped pieces, provided N is a
power of two. Are there other good examples along these same lines?
Unfortunately, most introductions to induction that I've found seem to
be fieldspecific, or prove closed forms for members of a series; these
aren't suitable for the audience I've got.
Thanks,
You could also show them the inductive "proof"
that all numbers are equal, which is a good
object lesson against using induction
carelessly.
We will prove that for any set S_n of n numbers, all
the members of S_n are equal. This is clearly true
for n = 1. Assume it's true for n1, and consider a set
S_n with n members a_1, a_2,...a_n. By the inductive
hypothesis,
a_1 = a_2 = ... = a_(n1)
and also
a_2 = ... = a_(n1) = a_n
so all the member of S_n are equal. 


Back to top 


Jeremy Boden science forum Guru Wannabe
Joined: 28 Apr 2005
Posts: 144

Posted: Thu Jul 20, 2006 11:17 am Post subject:
Re: "Cool" inductive proofs



On Thu, 20060720 at 00:05 +0000, Gerry Myerson wrote:
Quote:  In article <1153329277.10454.8.camel@localhost.localdomain>,
Jeremy Boden <jeremy@jboden.demon.co.uk> wrote:
I came across one the other day (proved by induction!) that is
unbelievably complex (and slightly wrong) in Apostol "Introduction to
Analytic Number Theory"):
"Given any two integers a & b, there is a common divisor, d of a and b
of the form
d = ax + by where x & y are integers.
[Moreover, every common divisor of a and b divides this d]"
Apostol's proof comes to 16 lines of text. I guess it's a matter
of opinion, but I don't think that qualifies as "unbelievably
complex." I'm more interested to know what you think is "slightly
wrong" in Apostol?

I may be misunderstanding the final comment (enclosed in square
brackets, "Moreover, every common divisor of a and b divides this d")
but it's certainly not true for common divisors of a & b.
Quote: 
It's more common to see the proof phrased in terms of wellordering.
Assuming a and b are not both zero (and handling separately the case
where they are both zero), consider all the positive numbers of the
form a x + b y where x and y are integers. There are such (just take
x = a and y = b to see that), so there's a least such; call it d.
Now all we have to do is show that d divides both a and b. By symmetry,
it's enough to show d divides a. Divide a by d, getting a quotient q
and a remainder r, r < d. Then
r = a  d q = a  (a x + b y) q = a X + b Y
where X = 1  x and Y =  q y, so by the hypothesis on d, r = 0.

My complaint is really that Apostol's approach is using a sledgehammer
to crack a very small nut  it's probably inappropriate in this case to
prove a statements in two variables by assuming it has been proved for
1..n = a+b and hence proving, inductively that it is true for n+1.
BTW Can I say if da & db => d = ax and d = by (for some x,y) and hence
2d = 2ax
d = by
=> d = 2ax  by which is of the required form? [only 4 lines]

Jeremy Boden 

Back to top 


Chris Smith science forum beginner
Joined: 02 Apr 2005
Posts: 11

Posted: Thu Jul 20, 2006 2:31 pm Post subject:
Re: "Cool" inductive proofs



Catarina Dias <mcldias@gmail.com> wrote:
Quote:  When I started to learn induction in school, my teacher refers a "cool"
variant of Andrew Taylor sugestion, which I think resulted very well,
because is very "suggestive"
The problem is " All blond women have blue eyes"
P(n) = "If in a field of n blond women, one of then has blue eyes, so
all of then have blue eyes"
P(1) is true...
Its exactly what Andrew Taylor said.

I've always seen (in a couple different places) this expressed as a
proof that all horses are the same color. The source that I remember is
the mathematical preliminaries section of Michael Sipser's Introduction
to the Theory od Computation, but there are others as well.

Chris Smith  Lead Software Developer / Technical Trainer
MindIQ Corporation 

Back to top 


jamesbev science forum beginner
Joined: 02 Nov 2005
Posts: 2

Posted: Thu Jul 20, 2006 2:49 pm Post subject:
Re: "Cool" inductive proofs



It's likely too advanced for your nonalgebra students, but the proof
of infinite primes stands out to me as one of the simplest and most
elegant proofs out there and one of the first that many students learn.
Not as simple as some of the other suggestions, but a good one for
demonstrating the power of proofs.
Chris Smith wrote:
Quote:  I am looking for examples of inductive proofs that:
1. Are simple enough to be understood by an average 14yearold.
2. Prove theorems that are easily *understood* by the average teenager,
but won't be too obvious so that the need for a proof is clear.
3. Involve minimal or no algebraic manipulation.
The one really good example I've found so far is the ability to tile an
NxN grid with one square removed with Lshaped pieces, provided N is a
power of two. Are there other good examples along these same lines?
Unfortunately, most introductions to induction that I've found seem to
be fieldspecific, or prove closed forms for members of a series; these
aren't suitable for the audience I've got.
Thanks,

Chris Smith 


Back to top 


Chris Smith science forum beginner
Joined: 02 Apr 2005
Posts: 11

Posted: Thu Jul 20, 2006 3:12 pm Post subject:
Re: "Cool" inductive proofs



jamesbev <jamesbev@gmail.com> wrote:
Quote:  It's likely too advanced for your nonalgebra students, but the proof
of infinite primes stands out to me as one of the simplest and most
elegant proofs out there and one of the first that many students learn.
Not as simple as some of the other suggestions, but a good one for
demonstrating the power of proofs.

How does that go as an induction? I remember reading a proof in Hardy's
Apology book, but there it was a proof by contradiction, beginning with
"let p be the largest prime..." and ending by contradicting the
fundamental theorem of artihmetic.

Chris Smith  Lead Software Developer / Technical Trainer
MindIQ Corporation 

Back to top 


Google


Back to top 



The time now is Sat Oct 21, 2017 11:03 pm  All times are GMT

