FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
"Cool" inductive proofs
Post new topic   Reply to topic 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

PostPosted: Wed Jul 19, 2006 4:38 pm    Post subject: Re: "Cool" inductive proofs Reply with quote

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
Back to top
Arturo Magidin
science forum Guru


Joined: 25 Mar 2005
Posts: 1838

PostPosted: Wed Jul 19, 2006 4:52 pm    Post subject: Re: "Cool" inductive proofs Reply with quote

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
Back to top
Jeremy Boden
science forum Guru Wannabe


Joined: 28 Apr 2005
Posts: 144

PostPosted: Wed Jul 19, 2006 5:14 pm    Post subject: Re: "Cool" inductive proofs Reply with quote

On Wed, 2006-07-19 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 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
Back to top
Yiftach Barnea
science forum beginner


Joined: 19 Jul 2006
Posts: 1

PostPosted: Wed Jul 19, 2006 6:22 pm    Post subject: Re: "Cool" inductive proofs Reply with quote

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

PostPosted: Thu Jul 20, 2006 12:05 am    Post subject: Re: "Cool" inductive proofs Reply with quote

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)
Back to top
msustik@gmail.com
science forum beginner


Joined: 20 Jul 2006
Posts: 4

PostPosted: Thu Jul 20, 2006 3:10 am    Post subject: Re: "Cool" inductive proofs Reply with quote

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
Back to top
Robert B. Israel
science forum Guru


Joined: 24 Mar 2005
Posts: 2151

PostPosted: Thu Jul 20, 2006 4:33 am    Post subject: Re: "Cool" inductive proofs Reply with quote

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 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
Back to top
vinay.sri48@gmail.com
science forum beginner


Joined: 20 Jul 2006
Posts: 2

PostPosted: Thu Jul 20, 2006 8:48 am    Post subject: Re: "Cool" inductive proofs Reply with quote

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.
Back to top
vinay.sri48@gmail.com
science forum beginner


Joined: 20 Jul 2006
Posts: 2

PostPosted: Thu Jul 20, 2006 8:50 am    Post subject: Re: "Cool" inductive proofs Reply with quote

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
Back to top
Andrew Taylor
science forum beginner


Joined: 31 May 2005
Posts: 9

PostPosted: Thu Jul 20, 2006 10:14 am    Post subject: Re: "Cool" inductive proofs Reply with quote

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.
Back to top
Catarina Dias
science forum beginner


Joined: 18 Jun 2006
Posts: 4

PostPosted: Thu Jul 20, 2006 11:14 am    Post subject: Re: "Cool" inductive proofs Reply with quote

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.
Back to top
Jeremy Boden
science forum Guru Wannabe


Joined: 28 Apr 2005
Posts: 144

PostPosted: Thu Jul 20, 2006 11:17 am    Post subject: Re: "Cool" inductive proofs Reply with quote

On Thu, 2006-07-20 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 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
Back to top
Chris Smith
science forum beginner


Joined: 02 Apr 2005
Posts: 11

PostPosted: Thu Jul 20, 2006 2:31 pm    Post subject: Re: "Cool" inductive proofs Reply with quote

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

PostPosted: Thu Jul 20, 2006 2:49 pm    Post subject: Re: "Cool" inductive proofs Reply with 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.



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
Back to top
Chris Smith
science forum beginner


Joined: 02 Apr 2005
Posts: 11

PostPosted: Thu Jul 20, 2006 3:12 pm    Post subject: Re: "Cool" inductive proofs Reply with quote

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
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 2 of 3 [41 Posts] Goto page:  Previous  1, 2, 3 Next
View previous topic :: View next topic
The time now is Sat Oct 21, 2017 11:03 pm | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0343s ][ Queries: 16 (0.0036s) ][ GZIP on - Debug on ]