What is the point of induction?

[The Student]

The fact that I gave you two examples explaining this, and this is all you question, is not encouraging.

Why are you in this class, anyway?

Sorry, but I was so lost that I was just happy to know that I knew enough that I could ask a question about something. Know that I keep referring to things that everyone has wrote.

I am told that I eventually have to take it if I decide to go further than a degree in Engineering Physics which I almost certainly think I will. I am addicted to math like it is a drug - I really enjoy it, and I think even the most theoretical part of math can be used in practical use. Also, there is something so powerful that I gain from math and math logic therefore I feel it is necessary for me to develop nanotechnology for synthetic biotechnology purposes.

[The Student]

.

I have been staring at these examples for days now, and unfortunately most of them are the same ones that my professor gave in his notes. Let me try to explain what I think is going on here in my own words from start to finish.

One person says to another who doesn't know about induction: Let me start by showing you the structure of the process that we will follow when it comes to proving a proposition by way of induction.

For every element in L, a natural number N can represent it. First, we need to show that 1 is an element of L thus having the properties of a natural number N. If this is true, then we any natural number k is also an element of L only if k+1 is an element of L. If this all satisfies, then L=N.

A way we can use induction is to show the proposition that Lk = N and L(k+1) = N. First, we have to prove that 1 is actually an element of L.
L(1) = 1
Now we have to show that L(k+1) = N
L(k+1) = k+1

Now we know that L=N.

I am starting to feel like I getting some of it. What do you think of my example?

[tkhunny]

Reaons for studying this material...

Fair enough. Those seem like good reasons.

You will have to step it up a little. Just a hair more into abstraction will help.

[The Student]

NO NO NO

In the second step, we are NOT trying to prove that k is a member of L. In the first step, we proved 1 is a member of L, so L is not the empty set. There is at least one member of L, namely 1, and we HOPE to prove that there are an infinite number of members, but at this point we do not know if there is one, more than one but less than an infinite number, an infinite number but not all the natural numbers, or what. We just know that one or more numbers are members of L. We choose an ARBITRARY one of those numbers in L and call it k. Because it is arbitrary we cannot ascribe any numeric value to it. But because it is in L we KNOW that it is a natural number and that it has all the antecedent properties PLUS property Q. Furthermore we know that (k + 1) is a natural number and has all the antecedent properties, but we do NOT know whether it has property Q. That is what we must prove.


Let's go back to the example I started in my previous post and do the second step.

Suppose we want to prove the following property of the natural numbers:

[TEX]For\ every\ natural\ number\ x, (x + 4)^2 < 2^{(x + 4)}.[/TEX]

We started with:

[TEX](A)\ Let\ L = the\ set\ of\ all\ natural\ numbers\ x\ such\ that\ (x + 4)^2 < 2^{(x + 4)}[/TEX]

We ended the first step with:

[TEX](C)\ 1 \in L.[/TEX]

On to the second step

[TEX](D) Let\ k\ be\ an\ arbitrary\ member\ of\ L.[/TEX] We know that there must be at least one member of L from step 1.

[TEX](E)\ k\ is\ a\ natural\ number \ge 1.[/TEX]

The line above follows from lines D and A and the antecedent property that all natural numbers are greater than or equal to 1 (according to the the more usual definition of the natural numbers).

[TEX]k^2 \ge 1^2 = 1.[/TEX] Antecedent property of natural numbers.

[TEX]8k > 2k.[/TEX] Antecedent property of natural numbers.

[TEX]16 > 9.[/TEX] Antecedent property of natural numbers.

[TEX]So\ (k + 4)^2 = k^2 + 8k + 16 \ge 1 + 8k + 16 > 8k + 16 > 2k + 9.[/TEX]

[TEX]Or\ (2k + 9) < (k + 4)^2.[/TEX]

[TEX]So\ (k + 4)^2 + (2k + 9) < (k + 4)^2 + (k + 4)^2.[/TEX]

[TEX]Or\ k^2 + 8k + 16 + 2k + 9 < 2(k + 4)^2.[/TEX]

[TEX]Or\ k^2 + 10k + 25 < 2(k + 4)^2.[/TEX]

[TEX]\ Or\ (k + 5)^2 < 2(k + 4)^2.[/TEX]

[TEX](F)\ Or\ [(k + 1) + 4]^2 < 2(k + 4)^2.[/TEX]

[TEX](k + 4)^2 < 2^{(k + 4)}.[/TEX] This follows from lines D and A. Notice that k has been substituted for x in the definition of property Q.

[TEX]So\ 2(k + 4)^2 < 2(2^{(k + 4)}).[/TEX] Antecedent property.

[TEX]Or\ 2(k + 4)^2 < 2^{(k + 5)}.[/TEX] Antecedent property.

[TEX](G)\ Or\ 2(k + 4)^2 < 2^{[(k + 1)+4]}.[/TEX] Antecedent property.

[TEX](H)\ So\ [(k + 1) + 4]^2 < 2^{[(k + 1) + 4]}.[/TEX]

Line H follows from lines F and G. It is the critical part of the proof. We have just shown that (k + 1) has property Q. Notice that (k + 1) has been substituted for x in the definition of property Q.

[TEX](J)\ And\ (k + 1)\ is\ a\ natural\ number.[/TEX]

The line above represents an antecedent property of k, which is a natural number by line E: the succesor of a natural number is also a natural number

[TEX](R) So\ (k + 1) \in L.[/TEX] This follows from lines H, J, and A.

[TEX]So\ L = the\ set\ of\ all\ natural\ numbers.[/TEX] This follows from lines C, D, and R.

[TEX]THUS,\ for\ any\ natural\ number\ x, (x + 4)^2 < 2^{(x+4)}.[/TEX]

I'll bet that was not an example your teacher gave.

Ohhhh, I really think I got it this time (I spent all day looking at everything you have typed) - lol.

Just to clarify, couldn't we combine steps 1 and 2 (step 1 being the proof that 1 is an element of L; and step 2 proving that k is an element of L) by showing an equation like: k*1=k and then go on to show something like step H) from above? Or do we have to stick to the same equation to show all 3 steps?

[The Student]

This last question of yours is very subtle (at least it is for me because I know very little mathematics; I studied European languages and history in college.) I do not know the answer; this is my intuition speaking.

As you undoubtedly know, there are frequently a number of different ways to prove a theorem. There are I believe hundreds of different proofs for the Pythagorean Theorem. My intuition tells me that that you cannot collapse the two steps of a proof by mathematical induction into one step UNLESS there is a way to prove the theorem some other way. Once you get comfortable with proofs by mathematical induction, it is frequently the easiest proof, and sometimes it is the only proof. So as a PRACTICAL matter, I'd not worry about trying to collapse steps 1 and 2. Step 1 is usually very easy, but step 2 all by itself can get very hard. If step 2 by itself is hard, steps 1 and 2 combined will probably drive you nuts, particularly because I believe it is sometimes impossible. Stick with the two step process.

The reason I asked that question was to see if I was thinking in the right direction. Your response was the response that I was hoping for.

In step 2, you do NOT prove that k has property Q and so is a member of set L. That is entirely backwards. k is a an arbitrarily chosen member of L. So, by the definition of L, k is a natural number with property Q. You do not have to prove those things. I keep stressing that L is not empty. Due to step 1, we know that L has at least one member, and we hope to prove it has infinitely many so it is not an unwarranted assumption to say that there is a natural number to be chosen as k. There is at least one such number.

So then why do even have to show k in an equation? Why not just skip to showing k+1?

What we prove in step 2 is that (k + 1) is a natural number with property Q. Proving that (k + 1) is a natural number is trivial. k is a natural number so (k + 1) is a natural number by one of the primitive defining properties of the natural numbers. There is nothing to prove. The whole trick is proving that (k + 1) has property Q. This can require great ingenuity and creativity.

Now here is where I expect I was unclear. In the final proof step that (k + 1) has property Q, you will end up with a statement that looks exactly like the general definition of property Q except (k + 1) is substituted for every x.

What may have confused you is that I said that the proof of step 2 will also contain a statement that looks exactly like the general definition of property Q except that k is substituted for every x. That statement follows from the fact that k is a member of L. The statement is necessary (at least it is necessary in every inductive proof I have ever seen) to prove that (k + 1) has property Q. The reason for this is that the properties for which proof by mathematical induction is suitable are inherited properties, meaning (k + 1) has the property Q BECAUSE k has the property Q.

If you have followed this, then I hope you now understand the basic concept of a proof by mathematical induction. At the risk of causing further confusion, I'd like to say just a bit about the extension of the method. We proved that 5^2 < 2^5, 6^2 < 2^6, etc for ever. This looks like a proposition that x^2 < x^n for every natural number x. But THAT proposition is false. 3^2 = 9 > 8 = 2^3. What is true is that x^2 < x^n for every natural number x > 4. BUT WE DID THE PROOF BY INDUCTION, which starts at 1. We played a little trick. The proposition that we proved was
(x + 4)^2 < 2^(x + 4). Starting with x = 1, that makes (x + 1) start at 5. This kind of trick GREATLY extends the range of application of proofs by mathematical induction, which becomes a very powerful tool, one that was well worth your while struggling to get your mind around. If ANYTHING is still hazy on the basic idea of proof by mathematical induction (which by the way is a deductive proof), please feel free to ask. If I cannot answer it, some of the very good mathematicians here can. The only skill I have is that I remember what gave me trouble and how I eventully found my way clear.

[mmm4444bot]

I got it

That's great! I'm closing this thread now.

If you'd like to continue discussing alterations to the inductive method or different reasons why the expression k+1 represents the next k, please feel free to start a new thread on the Odds & Ends board.

Cheers ~ Mark