I'll start with a review. Please ask a question ANYWHERE I have been unclear.
For right now, we are defining the natural numbers as 1, 2, 3, ....
A DEFINING property of the natural numbers is if k is a natural number, then (k + 1) is a natural number.
We are also going to assume as theorems all the BASIC facts of arithmetic. (Someone, probably Bourbaki, has proved them so we do not have to.)
A proof by mathematical induction involves PROVING that a specific property P is true for all of natural numbers. We are going to do the proof first by the old-fashioned way and then by the more modern way.
In a proof by mathematical induction, whether modern or old-fashioned, we cannot say that any natural number has property P until we have proved it (otherwise we would have a circular argument.)
Every such proof involves 2 steps. The first is to prove that 1, which IS a natural number by definition, has property P, which I have been stating in terms of an unknown natural number x. The way that we prove that 1 has property P is to show that the statement of property P is true when every x in the statement is replaced by 1. If the statement of property P is an equation, this means showing that the right-hand and left-hand sides of the equation have the same numeric value when 1 replaces x.
Why do we prove that 1 has property P when 1 is defined as a natural number? Because at the beginning of the proof, we have not proved that any natural number has property P, and obviously if 1 does not have property P, then it is false that all natural numbers have property P.
Enough generality.
The specific example of a property that we intend to prove is:
\(\displaystyle For\ every\ natural\ number\ x, \displaystyle \sum_{i=1}^x2^i = 2^{(x + 1)} - 2.\)
First step of the proof is:
\(\displaystyle \displaystyle \sum_{i=1}^12^i = 2^1 = 2.\) We evaluated the left-hand side of the equation for the case where x = 1.
\(\displaystyle 2^{(1+1)} - 2 = 2^2 - 2 = 4 - 2 = 2.\) We evaluated the right-hand side of the equation for the case where x = 1.
\(\displaystyle 2 = 2.\)
\(\displaystyle THUS\ \displaystyle \sum_{i=1}^12^i = 2^{(1+1)} - 2.\) The statement of the property is true when 1 replaces every x.
Notice that we proved this part of the statement using arithmetic. We were able to use the basic arithmetical properties of any specific numbers used in the GENERAL statement of property P (if there are any). in this example, that number is 2, and we used the basic arithmetical fact that 2^2 = 4. In addition, we were able to use the basic arithmetical facts about 1, such as 1 + 1 = 2, because this step in the proof is about 1 specifically. Note there is nothing circular. We did not assume that 1 has property P. We proved it.
This is the simple step so if you have any shred of confusion, we need to get rid of it before proceeding.
OK if you think about it, we actually proved two things:
\(\displaystyle 1\ has\ property\ P.\)
\(\displaystyle Consequently, there\ are\ one\ or\ more\ natural\ numbers\ with\ property\ P.\)
But we only proved that one number, namely 1, has property P. Where does the "or more" come from? If I tell you that I have one or more dollar bills in my wallet and we find that I have exactly one bill in my wallet when we look, I told the truth. "One or more" does not mean "more than one."
OK. We are now ready for step 2 of the proof. We arbitrarily choose one of the natural numbers, call it k, that has property P. We know that there is at least one to choose, namely 1, but we are hoping that there are more than one. But we cannot use any specific numeric fact about k. For example, we cannot say that k^2 = k. It is true that 1^2 = 1, but we are not limiting our choice to 1. Moreover, we do not know what specific number we are choosing. It may be 1 or it may not be. So there is no special numeric property that we can use about k. Here is what we can use:
Any of the basic arithmetic facts about EVERY natural number.
1 has property P (we just proved that).
If any specific number (say 2) comes up in the course of the proof, any arithmetical facts about that specific number.
k, which is a natural number and so is greater than or equal to 1, also has property P.
This last one is what drives people nuts. They say you have not yet proved that k has property P. Yes we have. We proved that there are one or more natural numbers with property P. And we chose k from among THOSE numbers. So it automatically has property P. We are not trying to prove that k has property P. It has that property by definition. We are going to prove that (k + 1) has property P. If you are with me to here, let's go to step 2 in our example. Here we go.
\(\displaystyle \displaystyle \sum_{i=1}^{(k+1)}2^i = 2^1 + ... 2^{(k+1)} = \left(\sum_{i=1}^k2^i\right) + 2^{(k+1)} = 2^{(k+1)} - 2 + 2^{(k+1)} = 2 * \left(2^{(k+1)}\right) - 2 = 2^{[(k+1)+1]} - 2.\)
\(\displaystyle In\ short, \displaystyle \sum_{i=1}^{(k+1)}2^i = 2^{[(k+1)+1]} - 2.\)
The statement of the property is true when (k + 1) replaces every x, which means that we have PROVED that (k+1) has property P.
Did you follow that? Any questions at all? I'll be gone for about 6 hours so you may not get a quick follow up.