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

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
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 wrote: 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.

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.
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
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 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. 14-15)

 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) = (a-b,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 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.

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 ideal-theoretic structure,
as is the case for many number theoretic proofs, e.g. see [1-3].
Number theory is a treasure hunt with ideals hidden everywhere.

--Bill Dubuque

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 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 pair-coprime factors

Recently this was credited to Filip Saidak but it's very old.
For various ring-theoretic generalizations see my prior post

--Bill Dubuque
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.)

- 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
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

<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
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 14-year-old. ...

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 n-th 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
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 round-robin 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 round-robin 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.
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 14-year-old. 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 +..+ n-1 + 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 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. 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.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 3 of 3 [41 Posts] Goto page:  Previous  1, 2, 3 View previous topic :: View next topic
 The time now is Thu Feb 21, 2019 5:36 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