Mathematical Induction

Mathematical induction – often, just induction – is one of the simplest and yet most challenging concepts to master. It is also one of the most rewarding proof techniques. Induction allows us to prove a property for natural numbers, for which we have a hunch but we need solid proof. For example, we believe that the sum of the first $n$ numbers is $n(n+1)/2$. In fact, every time we try for a different $n$, our hunch turns out to be true:

\[\begin{split}n=3,\ \ 1+2+3 = 6 &= \frac{3(3+1)}{2}=\frac{12}{2} \\ \\ n=4,\ \ 1+2+3+4 = 10 &= \frac{4(4+1)}{2}=\frac{20}{2} \\ \\ n=5,\ \ 1+2+3+4+5 = 15 &= \frac{5(5+1)}{2}=\frac{30}{2}\end{split}\]

There is a story that when Gauss was 10 years old, he derived the sum formula

\[1+2+\ldots+n = \frac{n(n+1)}{2}\]

with a simple observation. When he was asked by a teacher to calculate the sum for $n=10$, he noticed that

\[\begin{split}1+2+3+4+5&+6+7+8+9+10 = \\ \\ (1+10) + (2+9) + (3&+8) + (4+7) + (5+6) = \\ \\ 11 + 11 &+ 11 + 11 + 11 = \\ \\ 5\cdot 11 & = \frac{10}{2}\cdot (10+1)= \\ \\ \frac{n}{2}&\cdot (n+1)\end{split}\]

But deriving a formula is not the same as proving it. We can claim that the formula $1+2+\ldots+n = n(n+1)/2$ works for $n=3$ or 4 or 5 or even 10, but that doesn’t mean that it works for every natural number. We need a more rigorous tool to prove this property. The rigor, in this case, comes from the axiomatic foundation of natural numbers.

In 1889, Giuseppe Peano, an Italian mathematician, put together a few fundamental statements about natural numbers. These statements, known as Peano’s Axioms, are the building blocks of the natural numbers set $\mathbb{N}$. An axiom is a statement that we accept as true. Peano stated five axioms. The last one is the rigorous tool we need to prove $1+2+\ldots+n = n(n+1)/2$. It is worth, however, to review all five axioms first.

Before stating his axioms, Peano defined a successor function, i.e., a function that takes a natural number as input and returns the next successive natural number:

\[S(n) = n+1\]

Using the successor function, we can write:

\[\begin{split}1 &= S(0) \\ 2 &= S(S(0)) \\ 3 &= S(S(S(0)))\\ &\vdots\end{split}\]

Peano’s Axioms

There are 9 axioms that Peano stated about natural numbers. We are interested in the following X:

$0$ is a natural number.
For every natural number $x$, its successor $S(x)$ is also a natural number.
If a set $K$ contains $0$, and if for every natural number $n$ being in $K$ implies that $S(n)$ is also in $K$, then $K$ contains every natural number.

The last axiom is the basis for mathematical induction. Let’s demonstrate it with the summation formula $1+2+\ldots+n = n(n+1)/2$. We want to show that the formula works for every natural number. So far, we have shown that it works for $n=3, 4, 5$ and $10$.

We start by defining a set $K$ to contain the natural numbers that we have shown to work with the formula: $\{3, 4, 5, 10\} \subset K$. We can show that $0$ also belongs to $K$, because $0=0\cdot(0+1)/2$. Thus, set $K$ fulfills the first condition of the induction axiom, i.e., $0 \in K$.

The next step is to assume that a natural number $n$ is in $K$ and then prove that $n+1$ is also in $K$. If we do, then we prove (based on Peano’s axiom) that all natural numbers are in set $K$; or in other words $K=\mathbb{N}$. And why is this important? Because $K$ is the set with the numbers for which the sum formula works. And if $K=\mathbb{N}$, then the formula works for every natural number, which is the proof we wanted!

Looking at the subset of $K$ above, and knowing that the formula works for $10$, our challenge is to show that it also works for 11. Because the formula works up to 10, we can write the sum up to 11 as follow:

\[\begin{split}\underbrace{1+2+3+4+5+6+7+8+9+10}_{\dfrac{10(10+1)}{2}} + 11 = \\ \frac{10(10+1)}{2}+11 = \\ \\ \frac{10(10+1)}{2}+\frac{2(11)}{2} = \\ \\ \frac{10(11)+2(11)}{2} =\\ \\ \frac{(10+2)(11)}{2} = \\ \\ \frac{(11)(11+1)}{2}\end{split}\]

So $11\in K$ as well, based on the fact that $10\in K$.

Let’s assume then that random number $k\in K$, therefore:

\[1+2+\ldots + k = \frac{k(k+1)}{2}\]

Next we examine if and how we can show that $k+1$ is in $K$. If — and for now, that’s a big if — this is true, if $k+1$ is indeed in K, we expect that

\[1+2+\dots + k +(k+1) = \frac{(k+1)(k+2)}{2}\]

Our objective now is to start from the left side of the expression above and see if we can arrive to the right side. When we observe the left side:

\[1+2+\dots + k +(k+1)\]

we notice that it contains the expression from the case for $k$. And since we assumed that the case is true, we can substitute $1+2+\ldots + k$ with $\frac{k(k+1)}{2}$. The substitution give us:

\[\begin{split}1+2+\dots + k +(k+1) =\\ \\ \frac{k(k+1)}{2} + k+1) = \\ \\ \frac{k(k+1)+2(k+1)}{2} = \\ \\ \frac{(k+1)(k+2)}{2}\end{split}\]

And so, we have shown that

\[1+2+\dots + k +(k+1) = \frac{(k+1)(k+2)}{2}\]

and therefore $k+1\in K$. Or, in other words, every natural number belongs to $K$ and thus $K=\mathbb{N}$.

The “price of admission” to set $K$ is for a natural number $k$ to satisfy the formula $1+2+\ldots + k = k(k+1)/2$. And since we showed that all natural numbers are in $K$, we have proved that the formula works for any natural number.

A template for induction proofs

Induction problems ask us to prove a property that may be of the form

\[L(n) = R(n)\]

In the example above, $L(n)= 1+2+\ldots+n$ and $R(n)=n(n+1)/2$.

Given a problem in the form $L(n)=R(n)$, the induction proof can be done in three steps.

Step 1

Show that $L(n)=R(n)$ holds for $n=1$. (Yes, Peano says to show for $n=0$ but $1$ is just as good).

Step 2

Assume that $L(n)=R(n)$ holds for $n=k$, i.e., $L(k)=R(k)$ is true.

Step 3

Start with $L(k+1)$ and show that it equals $R(k+1)$. You will notice that the expression $L(k+1)$ always contains $L(k)$. And since you just assumed that $L(k)=R(k)$ in Step 2, you can write

\[\begin{split}L(k+1) &= L(k) + \Lambda(k+1) \\ &= R(k) + \rho(k+1)\end{split}\]

Where $\Lambda(k+1)$ and $\rho(k+1)$ are expressions involving $k+1$.

From here, the problem is reduced to simple (usually) derivations to show that $R(k) + \rho(k+1) = R(k+1)$. Showing that, completes the proof.

Examples

The summation formula

Prove that

\[1+2+\ldots + n = \frac{n(n+1)}{2}\]

We worked this formula above to demonstrate the inductive method. We repeat the proof here in a more formal manner.

Step 1

For this step, first we need to identify the expressions $L(n)$ and $R(n)$. In this case, it’s fairly easy:

\[\begin{split}L(n) &= 1+2+\ldots + n \\ \\ R(n) &= \frac{n(n+1)}{2}\end{split}\]

Next we have to test if $L(n)=R(n)$ for a specific value of $n$. Peano said to use $n=0$ but we prefer to test for $n=1$.

\[\begin{split}L(1)&=1 \\ \\ R(1)&=\frac{1(1+1)}{2}=1\end{split}\]

So, $L(1)=R(1)$.

Step 2

This is a simple and quick step. We only have to state that for an arbitrary $n=k$ the expression $L(k)=R(k)$ is true; in other words:

\[1+2+\ldots +k = \frac{k(k+1)}{2}\]

Step 3

Here we use the next number up from the previous step. In Step 2 we looked at $n=k$. The next number up is $k+1$. The question we must answer in this step now is if $L(k+1)$ equals $R(k+1)$.

\[L(k+1) = 1+2+\ldots +k + (k+1)\]

Notice that $L(k+1)=L(k)+k+1$. Step 2 empowers us to replace $L(k)$ with $R(k)$, therefore

\[\begin{split}L(k+1) &= \underbrace{1+2+\ldots +k}_{=L(k)=R(k)} + (k+1) \\ \\ &= R(k)+(k+1) \\ \\ &= \frac{k(k+1)}{2} + (k+1)\\ \\ &= \frac{(k+1)(k+2)}{2} \\ \\ &= R(k+1)\end{split}\]

We just proved that given $L(k)=R(k)$ the equation holds for the successor of $k$ as well, $L(k+1)=R(k+1)$, and thefore the original expression

\[1+2+\ldots + n = \frac{n(n+1)}{2}\]

is true for every natural number.

The stamps problems

Show that any postage amount greater than $0.17 can be formed with $0.03 and $0.10 stamps. For example, $0.22 worth of postage comprises one $0.10 stamp and four $0.03 stamps.

Step 1

Problems like this one do not have a readily available expression of the form $L(n)=R(n)$. We have to derive the formula by restating the problem. Basically, the problem says that any number greater than 17 can be written as the sum of multiples of 3 and multiples of 10:

\[ \begin{align}\begin{aligned}n&=3a+10b\\n&\geq 18\end{aligned}\end{align} \]

Here $L(n)=n$ but what about $R(n)$? The right side of the question does not contain $n$. Or does it? We can always write $3b+10b=3a+10b+0n$, and this will be our $R(n)$. So the problem is restated as follows:

\[\underbrace{n}_{L(n)} = \underbrace{3a+10b+0n}_{R(n)}\]

Now that we have established $L(n)$ and $R(n)$ we have to test that they hold true. We cannot test for $n=1$ because the problem states that the property applies only to numbers $n\geq 18$. So we should try for $L(18)=R(18)$, in other words, can we write 18 as a sum of multiples of 3 and 10? Indeed we can:

\[ \begin{align}\begin{aligned}18 =3a+10b\\\text{when}\ a=6, b=0\end{aligned}\end{align} \]

Step 2

This is the easiest step of the proof. We assume that the property holds for an arbitrary integer $k$, i.e., $L(k)=R(k)$.

Step 3

Can we now prove that the property works for $S(k)$, by working our way from $L(k+1)$ to $R(k+1)$. Just remember that for this problem, $R$ simply means a sum of multiples of 3 and 10.

\[ \begin{align}\begin{aligned}L(k+1) &= k+1\ \ \ \ (\text{and from step 2,}\ k=3a+10b)\\ &=3a+10b+1\ \ \ \ (\text{rewrite}\ 1=10-9)\\ &=3a+10b+10-9\\ &=3(a-3)+10(b+1)\ \ \ \ (\text{substituting}\ a'=a-3,\ b'=b+1)\\ &=3a'+10b'\end{aligned}\end{align} \]

What the expression above says is that $k+1$ is also a sum of multiples of 3 and 10, and therefore $L(k+1)=R(k+1)$.

A checklist

Write the left and right side expressions, clearly. In some cases these expressions may not be immediately clear. For example, in the problem where we try to prove that any postage value can be obtained with $0.05 and $0.04 stamps, the actual deliverable is the proof that every number greater than 11 can be written as the sum of multiples of 4 and multiples of 5. Mathematically that means $n=4x+5y$, for $n\geq 12$. Here $L(n)=n$ and $R(n)=4x+5y$. In the problem where we try to prove that $6^n-1$ is always divisible by 5, $L(n) =6^n-1$ and $R(n)=5q$.
Check if $L(1)=R(1)$ (for some problems you may have to check for another specific value; for example if the property you are trying to prove is limited to values $n\geq 16$, you shall check for $L(16)=R(16)$).
Assume that $L(k)=R(k)$ for some natural number $k$.
Start with $L(k+1)$ and see if you can get to $R(k+1)$, remembering that in all likelihood $L(k+1) = L(k) + \Lambda(k+1)$, where $\Lambda(k+1)$ is some expression for the $(k+1)$-th term of $L$. If so, the problem becomes an exercise in showing that $L(k)+\Lambda(k+1)=R(k+1)$.