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.

## Bookmarks