explaining induction

mikau · 2007-10-12 05:17:00

I wanted to explain mathematical induction to my dad but i can't think of a good enough example. My dad isn't mathematically challenged by any means, he went about as far as calc II for his degreee in architecture, but that was about 30 years ago and he only remembers about up to highschool level now. He does have a lot of appreciation for math, however, and was fascinated by a documentary explaining the connection between the golden ratio and beauty in people. He also was fascinated when i showed him fractal geometry.

So anyway, i'm looking for an example of induction thats not complicated but also proves something non obvious.

for instance, there is the proof that all counting numbers are greater than zero. Thats a bit too obvious and doesn't show the power of the method.

There is the guassian formula, 1 + 2 + ... + n = n(n+1)/2, but while thats trivial to an active mathematician it still seems a bit much to use as a first example. Don't you think?

Suggestions?

John E. Franklin · 2007-10-12 06:48:29

If you are a kid at a gumball machine, prove using induction, that the number of dimes in your hand will equal the number of gumballs in your mouth very soon. I actually would like to see this one written out because it is so simple, it would show off the very basic assumptions in induction.

mikau · 2007-10-12 07:17:42

bwahaha! Thats a funny problem. But actually, i'm not sure i follow. How is that induction? What is the inductive hypothesis and base case?

Last edited by mikau (2007-10-12 07:19:34)

mikau · 2007-10-12 07:29:39

i guess we could do it this way,

let n be the number of dimes left and a be the original number of dimes. Suppose by induction that the number of gumballs = a - n.

the base case is trivial, where a = n we naturally have a-a = 0 gumballs.

now the inductive step, we drop a dime into the machine, and the number of gumballs increases by 1, and the dimes decrease by 1, thus the relationship
gumballs = a - (n-1) = a - n +1 which is one more than the previous number of gumballs, holds true.

thus when you have exacly zero dimes left (n = 0) you have a - 0 = a gumballs.

I guess that works but that felt REALLY awkward.

Ricky · 2007-10-12 07:41:21

Prove that for every n, 2^(n+1) < 3^n

mikau · 2007-10-12 08:50:19

....what? for n = 1 we have 4 < 3. did you mean 2^(n+1) > 3^n perhaps? wait, that doesn't work for n = 2.

Right? Or do i need more sleep?

Last edited by mikau (2007-10-12 08:57:15)

Ricky · 2007-10-12 09:35:29

Eh, n > 2 is pretty close to every n.

John E. Franklin · 2007-10-12 11:12:05

Thanks a lot mikau. I've been looking for a simple example for myself really. I like that. Thanks.
Now on to Ricky's...

mikau · 2007-10-14 01:57:42

2^(n+1) < 3^n

well that one is pretty easy,
2^(n+2) < 3^(n+1) <->

2^n+1 < (3/2)3^n check!

i think thats a pretty good example i could use. Any more suggestions?

Jai Ganesh · 2007-10-14 02:27:01

Statement: For any integral value of n,
2^(n+1) < 3^n.

For n=1, LHS is 4 and RHS is 3. Hence, LHS>RHS.

By modifying the fist statement, lets test the valadity again.

Statement: For any integral value of n>1, 2^(n+1) < 3^n.

When n=2, LHS becomes 8 and RHS becomes 9. Thus, LHS < RHS.

When n=3, LHS=16 and RHS=27. Again, LHS<RHS.

Let us assume the statement is true for n=k.
Therefore, 2^(k+1)<3^k.

For n=k+1, LHS=2^(k+2).
2^(k+2) can be rewritten as [2^(k+1)]*2.
We already know that 2^(k+1)<3^k.
Hence, it follows that [2^(k+1)]*2<(3^k)*2.
3^k being positive, if a number is less than (3^k)*2, it is also less than (3^k)*3, or 3^(k+1).
{This is anologous to saying, if x is positive, nx>mx if n>m.}
Therefore, 2^(k+2)<3^(k+1).

That is, the statement is true for all k+1 if it is true for k.
Therefore, by induction,
For any integral value of n>1, 2^(n+1) < 3^n.

mikau · 2007-10-14 02:42:10

isn't that what i just said only more formaly?

mikau · 2007-10-15 12:33:39

hey guys, i posted a kind of weird inductive proof in ganesh's inductive proofs thread. i'm wondering if its valid.

Suppose you have something like

suppose by induction that statement 1 is true for n and statement 2 is true for n, ( a base case provided)

suppose statement 1 and statement 2 for n implies statement2 for n+1, and say collectively these imply statement 1 for n + 1, proving both are true by induction and the truth of each statement independantly.

is this sort of 'double hypothesis' valid? or am i using circular reasoning somewhere?

John E. Franklin · 2007-10-15 19:02:28

Sounds cool! Keep thinkin!! But I don't know the rules.
Link to Mikau thingy...
http://www.mathisfunforum.com/viewtopic.php?id=8313

Can you substitute in parenthesis, some actual numerical examples, in your proof
since I am so lazy; it helps me understand.

Last edited by John E. Franklin (2007-10-15 19:06:01)

mikau · 2007-10-16 03:21:25

well in an inductive proof the whole idea is to use generic values, and show it works even for these values. So.. i'm not sure how i can insert actual examples but...

for instance at k = 2, if you have a^2 - b^2, well thats just (a - b)(a+b) which is clearly divisible by (a-b)
and likewise for k = 2 you have ba^2 - ab^2 = ab(a - b). at k = 3, you have the slightly larger factoring (a - b)(a^2 + ab + b^2), and in ba^3 - ab^3 = ab(a^2 - b^2) = ab(a-b)(a+b) which contains a factor of (a - b).

the critical spot is where i said a^(k+1) - b^(k+1) = (a - b)(a^k + b^k) + ba^k - ab^k this i got by adding terms that allowed me to factor out the (a - b) and then subracting them, hence the appearence of + ba^k - ab^k. by adding and subtracting these i added a value of zero and it allowed me to convert it to a sum who's componants were easily divisible by (a-b)

makes sense?

bossk171 · 2007-10-16 06:46:52

My Calc teacher always called induction the "Latter of Thought" The way he said was that if you can prove the first rung of the latter exists, and can assume that an arbitrary rung exists, then by proving that the rung above the arbitrary rung is there, you've proved that the entire latter exists.

It's not really saying more than what already been said in this thread, but I always thought that it gave a really good visualization.

As for the proof that 1 + 2 + ... + n = n(n+1)/2, I'd really like to see that. I've never actually seen a formal proof, instead that's always been presented to me in an intuitive way, starting with a story of Guass's childhood.

Also the second post down here by Dross is a really great FALSE proof by induction.

Last edited by bossk171 (2007-10-16 06:55:05)

mikau · 2007-10-17 00:47:11

bossk, you've never seen the proof that 1 + 2 + ... + n = n(n+1)/2? thats a piece of cake!

try it for 1 or 2, you get 1 and 3 as you'd expect, now suppose by induction that it holds for n, stick in n+1 in place of n in that formula and you get
(n+1)(n+2)/2
= (n^2 + 3n + 2)/2
= (n^2 + n + 2n + 2)/2
= (n^2 + n)/2 + (2n + 2)/2
= n(n + 1)/2 + 2(n+1)/2
= n(n+1)/2 + (n+1)

by our inductive hypothesis, we have that n(n+1)/2 = 1 + 2 + ... + n and so the above sum is therefore 1 + 2 + ... + n + (n+1) and the inductive proof is complete!

bossk171 · 2007-10-17 03:55:57

mikau wrote:

bossk, you've never seen the proof that 1 + 2 + ... + n = n(n+1)/2? thats a piece of cake!

You're right, that's really straight forward.

I've read a few books where they tell a story that goes something like this:

When Guass (the famous mathematician) was just a kid at only eight years of age, the school teacher gave the kids the assignment of summing all the numbers from 1 to 100. The idea was to keep the students busy while the teacher did something else. Guass wrote down his answer within a few minutes of the teacher's assignment, where as all the other students were still summing at the end of the class, and Guass was the only one to get it right. What Guass had noticed (as an eight-year-old!) was that if he took all the natural numbers form 1 to 100 and added them to themselves [img]backwards[/img] you'll get a sum of twice what your looking for much easier to do:

1 + 2 + 3 + 4 + ... + 98 + 99 + 100
100 + 99 + 98 + 97 + ... + 3 + 2 + 1
_________________________________________
101 + 101 + 101 + 101 + ... + 101 + 101 + 101

Then dividing that sum by two, (10100/2 = 5050) Guass got the desired result. Using that story, most of the books launch into a lesson about how easy it is to see that's true for all natural numbers.

I like the proof more now, it's a real great example of how great induction is. Has anyone ever heard it called the ladder of thought before, or is that something exclusive to my calc teacher (he was a bit nutty)?

Also, as you put, the proof of (n(n+1)/2) = 1+2+3+...+n is "a piece of cake" if your dad is brushed up on his high school Algebra, he should have no trouble with it. And recommend the book Coincidences Chaos, and All That Math Jazz by Edward B Burger & Michael Starbird to your dad. Seasoned mathematicians might find it a bit stale, but it had some a lot of neat introductions for people who don't have much experience under their belt (and good sized section on the Golden Ration).

Last edited by bossk171 (2007-10-17 04:41:14)

Ricky · 2007-10-17 04:21:26

You might want to double check your math there, bossk.

bossk171 · 2007-10-17 04:40:02

Ricky wrote:

You might want to double check your math there, bossk.

I do this all the time, I get it conceptually, I get all exited and ahead of my self, drop a few key points, and then make myself look like an idiot. Thanks for pointing it out before too many people see it, it's fixed now.

Last edited by bossk171 (2007-10-17 04:43:01)

John E. Franklin · 2007-10-17 07:35:55

Thanks so much Mikau.
It makes some sense.
I'll tag this: JohnEFranklinMikau

Last edited by John E. Franklin (2007-10-17 07:37:23)

Math Is Fun Forum

#1 2007-10-12 05:17:00

explaining induction

#2 2007-10-12 06:48:29

Re: explaining induction

#3 2007-10-12 07:17:42

Re: explaining induction

#4 2007-10-12 07:29:39

Re: explaining induction

#5 2007-10-12 07:41:21

Re: explaining induction

#6 2007-10-12 08:50:19

Re: explaining induction

#7 2007-10-12 09:35:29

Re: explaining induction

#8 2007-10-12 11:12:05

Re: explaining induction

#9 2007-10-14 01:57:42

Re: explaining induction

#10 2007-10-14 02:27:01

Re: explaining induction

#11 2007-10-14 02:42:10

Re: explaining induction

#12 2007-10-15 12:33:39

Re: explaining induction

#13 2007-10-15 19:02:28

Re: explaining induction

#14 2007-10-16 03:21:25

Re: explaining induction

#15 2007-10-16 06:46:52

Re: explaining induction

#16 2007-10-17 00:47:11

Re: explaining induction

#17 2007-10-17 03:55:57

Re: explaining induction

#18 2007-10-17 04:21:26

Re: explaining induction

#19 2007-10-17 04:40:02

Re: explaining induction

#20 2007-10-17 07:35:55

Re: explaining induction

Board footer