Search   Memberlist   Usergroups
 Page 2 of 3 [41 Posts] View previous topic :: View next topic Goto page:  Previous  1, 2, 3 Next
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 14-year-olds?

That's a great one. Thanks!

--
Chris Smith - Lead Software Developer / Technical Trainer
MindIQ Corporation
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 14-year-old. 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 4-stick pile.

Note that of one player takes r sticks, then the resulting game is
just the same as before, but with N-r 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
second-player-strategy-for-multiples-of-four after that).

If r=0, then regardless of what player A does, player B can use his
turn to leave exactly 4(k-1) 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
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, 2006-07-19 at 09:13 +0000, Richard Tobin wrote:
 Quote: In article , Chris Smith wrote: I am looking for examples of inductive proofs that: 1. Are simple enough to be understood by an average 14-year-old. 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
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.
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 well-ordering.
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)
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 14-year-old. 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
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

<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 14-year-old. 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
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 14-year-old. 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 L-shaped 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 field-specific, 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.
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 14-year-old. 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
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 14-year-old. 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 L-shaped 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 field-specific, 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 n-1, and consider a set
S_n with n members a_1, a_2,...a_n. By the inductive
hypothesis,
a_1 = a_2 = ... = a_(n-1)
and also
a_2 = ... = a_(n-1) = a_n

so all the member of S_n are equal.
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 14-year-old. 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 L-shaped 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 field-specific, 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 n-1, and consider a set S_n with n members a_1, a_2,...a_n. By the inductive hypothesis, a_1 = a_2 = ... = a_(n-1) and also a_2 = ... = a_(n-1) = a_n so all the member of S_n are equal.
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, 2006-07-20 at 00:05 +0000, Gerry Myerson wrote:
 Quote: In article <1153329277.10454.8.camel@localhost.localdomain>, Jeremy Boden 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 well-ordering. 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 d|a & d|b => 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
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
jamesbev
science forum beginner

Joined: 02 Nov 2005
Posts: 2

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

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 14-year-old. 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 L-shaped 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 field-specific, or prove closed forms for members of a series; these aren't suitable for the audience I've got. Thanks, -- Chris Smith
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 non-algebra 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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 2 of 3 [41 Posts] Goto page:  Previous  1, 2, 3 Next View previous topic :: View next topic
 The time now is Fri Apr 26, 2019 2:07 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Nature of proofs by induction un student Undergraduate 10 Sat Jul 01, 2006 7:59 am That would be really cool Han de Bruijn num-analysis 1 Fri Jun 23, 2006 1:00 pm That would be really cool Han de Bruijn Math 2 Fri Jun 23, 2006 12:34 pm Simple proofs with a "lateral thinking step" Ross Clement (Email addre Math 3 Tue Jun 20, 2006 4:09 pm Proofs by induction and infinity Ross Clement (Email addre Math 9 Fri Jun 09, 2006 9:29 am