Dealing with Infinity: Mathematical Induction

“I was happy the day I was born. If I’m happy one day, then I’m always happy the next day.”

This is a quote from one of my favourite high-school math teachers (Brian Fox). It was my first introduction to the concept of mathematical induction and it has stuck with me ever since. If you believe that the truth of the two statements above imply that I have been happy my entire life, then you already understand mathematical induction. If not, then consider this: since I was happy on the day I was born, the second statement implies that I will be happy the day after I was born. Now, since I’m happy the day after I was born, the second statement again implies that I will be happy the day after that (two days after I was born). Continuing in this way, we must conclude that I’ve been happy every day of my life.

This simple recursive procedure is behind the proofs of many of the most important mathematical results in history. It is one of the best ways for mathematicians to deal with infinity. As a first (and probably everyone’s first) example, consider the following claim: if I add up the first $n$ numbers, I will get $\frac{n(n+1)}{2}$ . We can write this a little more mathematically as

$1+2+\dots +n=\frac{n(n+1)}{2}$ .

The first thing you should want to do is check that this seems to work for some small numbers. Let’s pick $n=6$ , for example. In this case, the claim is that $1+2+3+4+5+6=21$ , should be the same as $\frac{6\cdot(6+1)}{2}=\frac{6\cdot 7}{2}=21$ , which is true (so it works for $n=6$ ). That’s a great start, but just because it works for $n=6$ , doesn’t mean it should work for other numbers (see our previous blog post!). So how can we prove that this will work no matter what number we start with? We can use mathematical induction. This is a two step process: we need to show that the claim is true for $n=1$ (i.e. that we are happy the day we are born) and we also need to show that if the claim is true for some (arbitrary) number $k$ , then this will force it to be true for the next number, $k+1$ (i.e. if we are happy one day, then we are always happy the next).

The first part is the easy bit. If $n=1$ , then the left-hand side is just 1 and the right-hand side is $\frac{1\cdot (1+1)}{2}=\frac{1\cdot 1}{2}=1$ , so the claim is true when $n=1$ . Now comes the hard bit: suppose we’ve found a magic number $k$ , for which

$1+2+\dots+k=\frac{k(k+1)}{2}$ .

We want to show that this will force the formula to work for $k+1$ . So, assuming that $1+2+\dots+k=\frac{k(k+1)}{2}$ , consider the sum up to $k+1$ :

$\underbrace{1+2+\dots+ k}_{\text{this is equal to }\frac{k(k+1)}{2}}+(k+1)$

Since we know that the formula works for $k$ , we have (after a bit of grade 10 algebra):

$1+2+\dots +k +(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}=\frac{(k+1)(k+2)}{2}.$

Note that $\frac{(k+1)(k+2)}{2}=\frac{(k+1)\big((k+1)+1\big)}{2}$ which is exactly what the formula says it should be (i.e. make $n=k+1$ on the right-hand side of the formula).

This finishes our proof by induction! We have shown that the formula works for $n=1$ and that if it works for one number, it will always work for the next. So because it works for 1, it must also work for 2. And now because it works for 2, it must also work for 3 and so on. We’ve shown that the formula works for every value of $n$ (even though there’s an infinite number of cases)!

Mathematical induction is great for checking that formulas like this are actually always true, but unfortunately it doesn’t help us come up with the formulas in the first place. You should find this a little frustrating (it happens a lot in maths), but thankfully there is a process for actually determining the formulas (see difference equations).

Share this:

Like this: