13.2 Proof by induction

“Induction” is a method of proving something. Once again, let’s start with an example.

Consider the sum $\sum _{i=1}^n\frac{1}{i(i+1)}$ . In other words, $\frac{1}{1\times 2}+\frac{1}{2\times 3}+\frac{1}{3\times 4}+...+\frac{1}{n(n+1)}$ . This is neither arithmetic nor geometric, so none of our established tricks will work on it. How can we find the sum of such a series?

Students are often surprised to hear that mathematicians typically begin such problems by looking for a pattern . What does this series do for the first few terms?

• 1 term: $\frac{1}{1\times 2}=\frac{1}{2}$
• 2 terms: $\frac{1}{1\times 2}+\frac{1}{2\times 3}=\frac{1}{2}+\frac{1}{6}=\frac{2}{3}$
• 3 terms: $\frac{1}{1\times 2}+\frac{1}{2\times 3}+\frac{1}{3\times 4}=\frac{2}{3}+\frac{1}{\text{12}}=\frac{3}{4}$

At this point, you might already suspect the pattern. ½, ⅔, ¾...could it be that the next term will be 4/5? Let’s find out.

• 4 terms: $\frac{1}{1\times 2}+\frac{1}{2\times 3}+\frac{1}{3\times 4}+\frac{1}{4\times 5}=\frac{3}{4}+\frac{1}{\text{20}}=\frac{4}{5}$

It seems to work. The next term will probably be $\frac{5}{6}$ , and then $\frac{6}{7}$ , and so on. Stop for a moment and make sure you see the pattern. Then, see if you can express that pattern using mathematical notation instead of words. (Try this yourself before you keep reading!)

The pattern can be expressed like this:

$\frac{1}{1\times 2}+\frac{1}{2\times 3}+\frac{1}{3\times 4}+...+\frac{1}{n(n+1)}=\frac{n}{n+1}$

Stop for a moment and make sure you know where we are. What we have done is figured out a pattern to the answers, and shown that the pattern works for $n=1$ , $n=2$ , $n=3$ , and $n=4$ . Based on this pattern, we expect that if we added up $\frac{1}{1\times 2}+\frac{1}{2\times 3}+\frac{1}{3\times 4}+...+\frac{1}{\text{100}\times \text{101}}$ , we would get $\frac{\text{100}}{\text{101}}$ .

But we have not yet proven anything . Maybe the pattern breaks down for $n=5$ . Or maybe it works for all the n-values from 1 to 1000, and then suddenly stops working. We cannot possibly test all the values in the world, one by one.

This is where the proof by induction comes in. It gives us a way to prove that such a pattern will continue to hold forever.

An inductive proof, in general, consists of two steps. The first step is to show that the pattern holds when $n=1$ . The second step is to show that, whenever this pattern holds for some particular $n$ , it will also hold for the next $n$ . If it holds for $n=5$ , then it must hold for $n=6$ . If it works for $n=99$ , then it must also work for $n=100$ . Once we have proven that, in general, then we will have shown that it works for all $n$ values.

The algebra here all comes from our unit on rational expressions: you may want to take a moment to make sure you can follow it. But don’t let the algebra distract you from the main point, which is what we proved in the second step. We proved that the formula works for $n+1$ . But in the middle of that proof, we assumed that it works for the previous term, $n$ . In doing so, we proved that if it works for 1, it must also work for 2; if it works for 2, it must also work for 3; and so on. This amounts, then, to a proof that the pattern holds forever.