Author 
Message 
Lee Rudolph science forum Guru
Joined: 28 Apr 2005
Posts: 566

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



Chris Smith <cdsmith@twu.net> writes:
Quote:  Catarina Dias <mcldias@gmail.com> wrote:
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.

And in that phrasing it is, of course, (minimally) witty to someone
familiar with the Englishlanguage idiom "that's a horse of a different
color"; whereas the version with women is just one of arbitrarily many
bland rephrasings (unless, indeed, its "`suggestive'"ness is to be
taken as sexual, in which case its blandness is replaced with pointless
obnoxiousness; but I don't suppose Catarina Dias means "suggestive" in
that sense).
Quote:  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.

Lee Rudolph 

Back to top 


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

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



Jeremy Boden wrote:
Quote:  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.

Yes, it looks like you are misunderstanding.
Quote:  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]

No you can't. d divides a and b, not the other way around.
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 


Virgil science forum Guru
Joined: 24 Mar 2005
Posts: 5536

Posted: Thu Jul 20, 2006 7:33 pm Post subject:
Re: "Cool" inductive proofs



In article <MPG.1f294b5f168f22009896a9@news.altopia.net>,
Chris Smith <cdsmith@twu.net> wrote:
Quote:  jamesbev <jamesbev@gmail.com> wrote:
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.

IIRC, the original in Euclid merely proves directly that there a prime
larger than any given prime, and avoids any direct suggestion of
infinitely many of primes. 

Back to top 


Lee Rudolph science forum Guru
Joined: 28 Apr 2005
Posts: 566

Posted: Thu Jul 20, 2006 8:16 pm Post subject:
Re: "Cool" inductive proofs



Chris Smith <cdsmith@twu.net> writes:
Quote:  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.

THEOREM. For every positive integer n, there exists a set X(n) of n
integers no two of which have a common divisor greater than 1.
PROOF BY INDUCTION. For the base case, let X(1) = {1}. Given
X(n), let the elements of X(n+1) be the elements x_1,...,x_n of
X(n) and the integer x_{n+1} = 1+(x_1)(x_2)...(x_n). To complete
the proof we have to confirm only that for i=1,...,n, x_{n+1} and
x_i have no common divisor greater than 1; by construction, any
common divisor of x_{n+1} and x_i is a divisor of 1, so we're ok.
QED
That there is no finite upper bound on the number of elements in a
set of prime integers is a corollary of the Theorem, but the proof
requires knowing a few more things about primes.
Lee Rudolph 

Back to top 


Bill Dubuque science forum Guru Wannabe
Joined: 04 May 2005
Posts: 236

Posted: Thu Jul 20, 2006 9:08 pm Post subject:
Re: "Cool" inductive proofs



Gerry Myerson <gerry@maths.mq.edi.ai.i2u4email> wrote:
Quote:  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"):

Theorem 1.2 (pp. 1415)
Quote:  "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."

The inductive step is (a,b) = (ab,b), (m,n) := m Z + n Z
which is quite simple and quite standard. See below for a proof
that serves to better emphasize the true essence of the matter.
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.

SIMPLER a Z + b Z is a set of integers closed under subtraction
so every member c is a multiple of the smallest positive member d,
since, otherwise, c mod d would be a positive member less than d.
Alternatively: if c were the smallest member>0 not divisible by d
then c  d would be a smaller one. Here we've replaced division
(= repeated subtraction) by its inductive step (= subtraction),
i.e. c mod d = c  n d arises from c by repeatedly subtracting d.
The first proof works for every domain with a Division Algorithm.
In algebraic language, it shows that a Euclidean domain is a PID,
since nonzero ideals are generated by a member of minimal value.
Key is the recognition of the innate idealtheoretic structure,
as is the case for many number theoretic proofs, e.g. see [13].
Number theory is a treasure hunt with ideals hidden everywhere.
Bill Dubuque
[1] http://google.com/groups?threadm=y8zvf17cjph.fsf%40nestle.csail.mit.edu
[2] http://google.com/groups?threadm=y8z4r1lsrov.fsf%40nestle.ai.mit.edu
[2] http://google.com/groups?selm=y8ziss6kia5.fsf%40nestle.ai.mit.edu 

Back to top 


Bill Dubuque science forum Guru Wannabe
Joined: 04 May 2005
Posts: 236

Posted: Thu Jul 20, 2006 9:32 pm Post subject:
Re: "Cool" inductive proofs



lrudolph@panix.com (Lee Rudolph) wrote:
Quote:  Chris Smith <cdsmith@twu.net> writes:
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 arithmetic.
THEOREM. For every positive integer n, there exists a set X(n) of n
integers no two of which have a common divisor greater than 1.
PROOF BY INDUCTION. For the base case, let X(1) = {1}. Given
X(n), let the elements of X(n+1) be the elements x_1,...,x_n of
X(n) and the integer x_{n+1} = 1+(x_1)(x_2)...(x_n). To complete
the proof we have to confirm only that for i=1,...,n, x_{n+1} and
x_i have no common divisor greater than 1; by construction, any
common divisor of x_{n+1} and x_i is a divisor of 1, so we're ok.
QED
That there is no finite upper bound on the number of elements in a
set of prime integers is a corollary of the Theorem, but the proof
requires knowing a few more things about primes.

SIMPLER n > n*(n+1) increases number of paircoprime factors
Recently this was credited to Filip Saidak but it's very old.
For various ringtheoretic generalizations see my prior post
http://google.com/groups?selm=y8zbr8kv5vl.fsf__%40nestle.csail.mit.edu
Bill Dubuque 

Back to top 


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

Posted: Thu Jul 20, 2006 9:44 pm Post subject:
Re: "Cool" inductive proofs



Robert Israel wrote:
Quote:  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).

Actually, I am not sure that that changes the final answer. Note that
the lion prefers to eat (rule 1) and can be prevented from eating by
application of rule 5. So it seems that if he gets through the sleep
he will eat. That is to say facing starvation tomorrow does not
prevent him from eating today.
(The rules cannot have a flaw, they are the rules! Of course it is
possible that the rules as stated are not what would have lead to a
more interesting/better etc problem.)
I already made the rules more verbose, because the original formulation
 as I heard it in high school  allowed many similar objections
stemming from real life which did not fit the simplified mathematical
model. Maybe this is not a bad thing after all. It gives the
opportunity for the teacher to talk about modelling and how to turn
real life problems into equations and the gotchas.
Quote:  Under the circumstances, would the lion want to prolong the inevitable?

Yes I guess we need a rule 0. stating the lions want to survive as long
as they can. I grant that does not follow from being intelligent.. :)
Quote:  Also, the lion would have to worry about whether another lion will
drop dead of starvation during the night.

That is interesting, I wonder whether you considered this in your
solution. It seems that what could happen is that the lions wait until
it becomes clear who is starving most. The lion who would starve first
could decide to eat the meat, while the others may decide to wait.
With this twist though the problem may not be as good for 14 olds.
Matyas 

Back to top 


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

Posted: Thu Jul 20, 2006 11:52 pm Post subject:
Re: "Cool" inductive proofs



In article <1153431846.877596.287950@s13g2000cwa.googlegroups.com>,
<msustik@gmail.com> wrote:
Quote:  Robert Israel wrote:
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).
Actually, I am not sure that that changes the final answer. Note that
the lion prefers to eat (rule 1) and can be prevented from eating by
application of rule 5. So it seems that if he gets through the sleep
he will eat. That is to say facing starvation tomorrow does not
prevent him from eating today.
(The rules cannot have a flaw, they are the rules! Of course it is
possible that the rules as stated are not what would have lead to a
more interesting/better etc problem.)
I already made the rules more verbose, because the original formulation
 as I heard it in high school  allowed many similar objections
stemming from real life which did not fit the simplified mathematical
model. Maybe this is not a bad thing after all. It gives the
opportunity for the teacher to talk about modelling and how to turn
real life problems into equations and the gotchas.
Under the circumstances, would the lion want to prolong the inevitable?
Yes I guess we need a rule 0. stating the lions want to survive as long
as they can. I grant that does not follow from being intelligent.. :)
Also, the lion would have to worry about whether another lion will
drop dead of starvation during the night.
That is interesting, I wonder whether you considered this in your
solution. It seems that what could happen is that the lions wait until
it becomes clear who is starving most. The lion who would starve first
could decide to eat the meat, while the others may decide to wait.
With this twist though the problem may not be as good for 14 olds.

Things get complicated if the lions have to deal with several food items,
so let's suppose that
1) If one lion eats on a given day, no lions will die of starvation that
day. The lion that ate will be asleep the next day, and if not eaten
will be awake the following day. However, if no lions eat, exactly one
lion will die of starvation, becoming available as a food item the
next day.
2) Any food item that is available on a given day and is not eaten
will spoil, and thus will not be available the next day.
Thus on any given day, until the lions all die out, there will always be
exactly one available food item (either a piece of meat, or a dead lion,
or a sleeping lion). The state of the system can be described as
(n_a, n_s) consisting of the number n_a of awake lions and the number
n_s of sleeping lions. Here's how the state will change from one day
to the next.
(0,0) or (0,1) > (0,0), since there's no awake lion.
(1,0) or (1,1) > (0,1): the awake lion would rather eat than starve.
From (2,0) or (2,1), if a lion eats, the state goes to (1,1). But
then that lion that ate would be eaten while sleeping the next day. Since
the lion's top priority is not to be eaten, it will not eat.
Thus (2,0) > (1,0), and (2,1) > (2,0), with no eating.
.... and then by induction:
If n_a is odd, a lion will eat. Thus a lion that is sleeping with n_a odd
will be eaten. If n_a is even, no lion will eat, and a lion that is
sleeping will survive.
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 


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

Posted: Fri Jul 21, 2006 2:52 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.
...

1. A classic theorem is the pigeon hole theorem. It is usually not
proved, but instead just declared obvious (along with the commutativity
of addition of integers etc.), but if you want to prove it rigorously,
then you would use induction.
Look at the axioms of set theory and it becomes appearent that
induction is in almost every proof of interest.
2. The next one is harder. I suggest to tackle it after the Euclidean
algorithm is studied.
I denote by (a, b) the greatest common divisor of the a and b
(positive) integers.
Set a_n = 2^n  1. Prove that (a_n, a_m) = a_{(n, m)} (Note a_n is a
with an n subscript.)
3. Even harder problem for those in class who paid attention to the
previous problem and aspire to be geniuses: Prove that (F_n, F_m) =
F_{(n, m)}, where F_n denotes the nth Fibonacci number.
The above two can be proved by appealing to the Eucledean algorithm and
not to mention induction, but it is cleaner to formulate the proof with
explicitly showing the induction (than hiding it in the E. alg.).
4. This is really hard: Assume that f maps naturals to naturals and
f(f(n)) < f(n+1).
What is f? Or: Prove that it is...
5. So you have geniuses in your class, yes? Take this! Modify the
above to have the following condition for f:N>N
"For every n there is an i >=2 such that f^i(n) < f(n + 1)."
Here f^i denotes the i applications of f, so f^2(n) = f(f(n)), f^3(n) =
f(f(f(n))) etc.
Guess what, this definition should be given recursively if concerned
about rigor, and recursive definitions are almost the same as
inductions!!
Enjoy.
Matyas 

Back to top 


w.taylor@math.canterbury. science forum beginner
Joined: 17 Sep 2005
Posts: 30

Posted: Fri Jul 21, 2006 5:40 am Post subject:
Re: "Cool" inductive proofs



Gerry Myerson wrote:
Quote:  In a roundrobin tournament, if there's any cycle (that is,
any case where a beats b, b beats c, ..., y beats z, and z beats a),
then there's a cycle involving just 3 entrants.

A similar one:
In a roundrobin tournament,
IF the players cannot be partitioned so that everyone in A
beats everyone in B,
THEN there is a Hamiltonian cycle,
(cycle of wins including all players).
Bill
We must respect the other fellow's religion, but in the way that
we assent that his wife is beautiful and his children smart. 

Back to top 


dmmcmah@gmail.com science forum beginner
Joined: 10 Apr 2006
Posts: 7

Posted: Fri Jul 21, 2006 5:49 am Post subject:
Re: "Cool" inductive proofs



While I admire your suggestion to challenge the kids, I agree with the
first post that proofs of closed form expressions of series are a bit
sophisticated for 14 year olds. In fact that is probably a bit
sophisticated for many college students.
David McMahon
http://www.quantumphysicshelp.com/
William Elliot wrote:
Quote:  On Tue, 18 Jul 2006, Chris Smith wrote:
I am looking for examples of inductive proofs that:
1. Are simple enough to be understood by an average 14yearold.
1. Are simple enough to provoke an average 14 year old to think.
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.
1 + 2 + 3 +..+ n1 + n = n(n + 1)/2
3. Involve minimal or no algebraic manipulation.
3. Involve exercising simple algebraic notions.
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.
Then make the audience suitable for the problems.
Instead of talking down to our youth, of continuing their expectation that
it all comes easy, provoke them to think, stimulate them to learn,
inspire them to enjoy and use their mental skills. 


Back to top 


Google


Back to top 



The time now is Fri Apr 19, 2019 6:15 pm  All times are GMT

