Do you know the sum of the first five positive odd numbers? How about the sum of the first 20 positive odd numbers? The first 100? Wouldn’t it be great if there were a formula for the sum of the first n positive odd numbers so we could easily answer this question? Let’s see if we can find a pattern:
| n | Expression | Sum |
| 1 | 1 | 1 |
| 2 | 1 +3 | 4 |
| 3 | 1 + 3 + 5 | 9 |
| 4 | 1 + 3 + 5 + 7 | 16 |
| 5 | 1 + 3 + 5 + 7 + 9 | 25 |
It certainly appears that the sum of the first n positive odd numbers is n2. Or, if we write this symbolically:
We’ve just shown that this formula is true for the first five values of n, but how do we know it is true for every value of n? We could test our theorem for n = 6, n = 7, n = 8, and so forth. But you can see that this process would take us a very long time to show it for every value of n. Like, forever! Fortunately, there is a better method for proving conjectures of this sort. It is called mathematical induction. Math induction is a very powerful tool in analysis. If you think about it, it allows us to prove an infinite number of theorems. And we can do this in only three steps!
How does math induction work? It depends on a subtle idea: if the theorem is true for one particular value of n (say n= k) and we can use this fact to show that it’s true for the next value of n (that is, n=k+1), then it will be true for every value of n ≥ k. That is, one proof turns into an infinite number of proofs! How is this possible? Because each value of n leads to the next value of n. If it’s true for n=3 then we’ve shown it’s true for n=4. But since it’s true for n=4, we’ve also shown it’s true for n=5. And therefore it’s also true for n=6, and then n=7, etc. Most textbooks that cover math induction use a dominoes analogy—if you knock down the first domino, it knocks down the second, the second knocks down the third and so on.
Here are the three steps in math induction, and you will see that they are quite simple to describe:
Step 1: prove the theorem is true for n=1. This is a really easy step. You just plug in n=1 into the theorem and show that it is true. (Note: on occasion, you will start at a value of n greater than 1. This does not change the validity of the process.)
Step 2: Assume that the theorem is true for n = k. (Note that you aren’t even proving anything in this step. You just write out what the theorem would look like if it were true for n=k.)
Step 3: Use the expression in Step 2 to show that the theorem is true for n=k+1. (You usually do this by applying a little bit of algebra.)
That’s all there is to it! Let’s see how it works on the theorem we proposed above. We restate the theorem here for convenience:
Step 1: Prove for n = 1.
Step 2: Assume for n=k
Step 3: Prove for n = k+1
![1+3+5+ \dots + (2k-1) = k^2 \; \; \text{[line 1]}](http://s0.wp.com/latex.php?latex=1%2B3%2B5%2B+%5Cdots+%2B+%282k-1%29+%3D+k%5E2%C2%A0+%5C%3B+%5C%3B+%5Ctext%7B%5Bline+1%5D%7D+&bg=ffffff&fg=000&s=0 "1+3+5+ \dots + (2k-1) = k^2 \; \; \text{[line 1]}")
![1+3+5+ \dots + (2k-1)+(2k+1) = k^2 + (2k+1) \; \; \text{[line 2]}](http://s0.wp.com/latex.php?latex=1%2B3%2B5%2B+%5Cdots+%2B+%282k-1%29%2B%282k%2B1%29+%3D+k%5E2+%2B+%282k%2B1%29%C2%A0+%5C%3B+%5C%3B+%5Ctext%7B%5Bline+2%5D%7D+&bg=ffffff&fg=000&s=0 "1+3+5+ \dots + (2k-1)+(2k+1) = k^2 + (2k+1) \; \; \text{[line 2]}")
![k^2 + (2k+1) = (k+1)^2 \; \; \text{[line 3]}](http://s0.wp.com/latex.php?latex=k%5E2+%2B+%282k%2B1%29%C2%A0%3D+%28k%2B1%29%5E2+%5C%3B+%5C%3B+%5Ctext%7B%5Bline+3%5D%7D+&bg=ffffff&fg=000&s=0 "k^2 + (2k+1) = (k+1)^2 \; \; \text{[line 3]}")
[This step is a little harder to follow, so I’ve numbered the lines to explain the process.
- Line 1 is simply a repeat of Step 2. I wrote it here for clarity; you don’t need to repeat your work.
- In line 2, I’ve added (2k + 1) to both sides. That’s a valid algebra operation, so if Line 1 is true, Line 2 is also true. Why did I add (2k +1)? Because it’s the next term in the sum on the left side of the equation.
- In Line 3, I’ve simplified the right side of the equation.]
But (k+1)2 is exactly what our theorem says the right side of the equation will be when n = k+1. So the assumption that the theorem is true for n=k led to the conclusion that it is also true for n=k+1. And our proof is complete.