Induction is a powerful method for proving statements of the form “for all natural number \(n\), so and so is true". It may feel like dark magic the first time you see it. Let’s look at an example which will help us formulate the principle of mathematical induction.
Suppose you want to compute the sum \(1+2+\dots+n\) up to some natural number \(n\). Then you discover a curious pattern:
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \(1+2+\dots+n\) | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 |
| \(\frac{n(n+1)}{2}\) | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 |
We may guess at this point \(1+2+\dots+n = \frac{n(n+1)}{2}\). How can we prove it? One way is to attack the problem step by step.
When \(n=1\), the sum is just \(1\) and \(\frac{1\times(1+2)}{2}=1\). So far so good.
When \(n=2\), the sum is \(1+2 = 3\) and \(\frac{2\times(2+1)}{2}=3\). We can also see this in another way. As we already noted, \(1 = \frac{1\times(1+1)}{2}\). This means \[1+2 = \frac{1\times (1+1)}{2} + 2 = \frac{1\times2+2\times2}{2} = \frac{(1+2)\times 2}{2} = \frac{2\times(2+1)}{2}.\]
When \(n=3\), we have already proved that \(1 + 2 = \frac{2\times(2+1)}{2}\), so \[1+2+3 = \frac{2\times (2+1)}{2} + 3 = \frac{2\times3+2\times3}{2} = \frac{(2+2)\times 3}{2} = \frac{3\times(3+1)}{2}.\]
When \(n=4\), we have already proved that \(1 + 2 + 3 = \frac{3\times(3+1)}{2}\), so \[1+2+3+4 = \frac{3\times (3+1)}{2} + 4 = \frac{3\times4+2\times4}{2} = \frac{(3+2)\times 4}{2} = \frac{4\times(4+1)}{2}.\]
When \(n=5\), we have already proved that \(1 + 2 + 3 + 4 = \frac{4\times(4+1)}{2}\), so ...
It starts getting a bit boring, but hopefully you get the point. Important takeaways from the example above:
The truth of the next case depends ONLY on the previous case.
We know what we need to prove IS true for the first case, that is \(n=1\).
Any natural number is FINITE. By repeating the same procedure starting from \(n=1\), we can eventually reach any given natural number.
Thus, the formula is true for all natural numbers.
A diagram summarizing the idea: \[\text{true for } n=1 \implies \text{true for } n=2 \implies \text{true for } n=3 \implies \text{true for } n=4 \implies \dots\]
This is the mechanism behind induction. Formally, we can state the principle of mathematical induction as follows. Suppose we have a series of statements enumerated by the natural numbers: 1st statement, 2nd statement, 3rd statement and so on. Suppose that
the 1st statement is true (the base case is true);
whenever the \(n\)th statement is true, the \((n+1)\)th statement is also true (the induction step is valid assuming the induction hypothesis).
Then the statement is true for all natural numbers. Let us revisit the example and prove it formally now using the principle of mathematical induction.
Show that if \(1+2+\dots+n = \frac{n(n+1)}{2}\), then \(1+2+\dots+(n+1) = \frac{(n+1)((n+1)+1)}{2}\).
Show that \(1+2+\dots+n = \frac{n(n+1)}{2}\) for every natural number \(n\).
Show that if \(1+2^1+2^2+\dots+2^{10} = 2^{11} - 1\), then \(1+2^1+2^2+\dots+2^{11} = 2^{12} - 1\).
Show that \(1+2^1+2^2+\dots+2^n = 2^{n+1} - 1\) for every natural number \(n\).
What is wrong with the following proof that “all rulers have the same length" using induction?
Base case: suppose that we have one ruler, then clearly it clearly has the same length as itself.
Assume that any \(n\) rulers have the same length for the induction hypothesis. If we have \(n+1\) rulers, the first \(n\) ruler have the same length by the induction hypothesis, and the last \(n\) rulers have the same length also by induction hypothesis. The last ruler has the same length as the middle \(n-1\) rulers, so it also has the same length as the first ruler. This means all \(n+1\) rulers have the same length.
By the principle of mathematical induction, all rulers have the same length.
Given a series of statements enumerated by the natural numbers, the strong induction principle says the following. Suppose that
The 1st statement is true (the base case).
Whenever all statements up to and including the \(n\)th statement is true, the \((n+1)\)th statement is also true (induction step).
Then the statement is true for all natural numbers. Show that the strong induction principle works.
Prove that each natural number \(n\geq 2\) can be uniquely written as a product of prime factors. More precisely, there are prime numbers \(p_1,\dots,p_s\) such that \(n = p_1\dots p_s\). Moreover, if \(n = q_1\dots q_l\) where \(q_1,\dots,q_l\), then \(s=l\) and after reordering we have \(q_1 = p_1,\dots,q_s=p_s\). This is the fundamental theorem of arithmetic.
The AM-GM inequality asserts that the arithmetic mean of nonnegative numbers is always at least their geometric mean. That is, if \(a_1,\dots,a_n\geq 0\), then \[\frac{a_1+\dots+a_n}{n}\geq \sqrt[n]{a_1\dots a_n}.\] Prove this inequality.
There are many proofs of this fact and quite a few of them are by induction. In fact, one of the most creative uses of induction can be found in Cauchy’s proof of the AM-GM inequality in Cours d’analyse.
Show that if \(1+3+5+7+...+97+99=50^2\), then \(1+3+5+7+...+97+99+101=51^2\).