Mathematical induction

How do you prove a statement for every natural number \(n\) when there are infinitely many of them? You cannot check each one. Mathematical induction solves this with a two-step argument that works like a row of dominoes: show that the first domino falls, and show that each falling domino knocks over the next. Then every domino falls. Induction is the standard tool for statements about sums, divisibility, inequalities, recursive definitions and algorithms, and it is the first proof technique that is genuinely about the structure of the natural numbers rather than about logic alone.

The principle

Principle of mathematical induction. Let \(P(n)\) be a statement about natural numbers \(n\). Suppose that

• (base case) \(P(1)\) is true, and

• (inductive step) for every \(k \ge 1\), if \(P(k)\) is true then \(P(k + 1)\) is true.

Then \(P(n)\) is true for every natural number \(n\).

Why should we believe this? The base case gives \(P(1)\). The inductive step with \(k = 1\) turns \(P(1)\) into \(P(2)\). With \(k = 2\) it turns \(P(2)\) into \(P(3)\), and so on. Any particular \(n\) is reached after finitely many steps. In the formal development of the natural numbers, due to Giuseppe Peano in 1889 and Richard Dedekind a year earlier, induction is one of the axioms; it expresses the idea that every natural number can be reached from 1 by repeatedly adding 1. In lesson 8 we will see that it is equivalent to the well-ordering principle, which says that every non-empty set of natural numbers has a smallest element.

In the inductive step the assumption that \(P(k)\) is true is called the inductive hypothesis. It is not circular. We are not assuming the statement we want to prove, which is '\(P(n)\) for all \(n\)'. We are proving a conditional, '\(P(k) \implies P(k+1)\)', for an arbitrary \(k\), and a direct proof of a conditional always assumes its hypothesis.

A first example: summing integers

Theorem. For every natural number \(n\), \(1 + 2 + \dots + n = \frac{n(n + 1)}{2}\).

Proof. Let \(P(n)\) be the statement \(1 + 2 + \dots + n = \frac{n(n + 1)}{2}\). We use induction on \(n\).

Base case. For \(n = 1\) the left side is 1 and the right side is \(\frac{1 \cdot 2}{2} = 1\). So \(P(1)\) is true.

Inductive step. Let \(k \ge 1\) and suppose \(P(k)\) is true, that is, \(1 + 2 + \dots + k = \frac{k(k + 1)}{2}\). We must show \(P(k + 1)\), that is, \(1 + 2 + \dots + (k + 1) = \frac{(k + 1)(k + 2)}{2}\). Starting from the left side and using the inductive hypothesis,

\[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}.\]

So \(P(k + 1)\) is true. By induction, \(P(n)\) holds for every natural number \(n\). \(\blacksquare\)

Every induction proof should have these visible parts: a clear statement of \(P(n)\), a labeled base case, a labeled inductive step that states the inductive hypothesis and the goal \(P(k + 1)\), a computation that uses the hypothesis, and a concluding sentence. Writing out the goal before you start the computation is the single most helpful habit, because it tells you exactly what expression you are aiming for.

There is a famous story that the young Carl Friedrich Gauss summed the numbers from 1 to 100 in seconds by pairing them: \(1 + 100\), \(2 + 99\), and so on, fifty pairs each summing to 101, giving 5050. Gauss's trick explains where the formula comes from; induction proves it. Both are worth knowing.

Sums of other forms

The same pattern proves many summation formulas. Here is one where the algebra in the inductive step needs more care.

Induction proves a formula you already have; it does not tell you where the formula comes from. You can often guess a formula by computing small cases, as the code at the end of this lesson does, and then confirm the guess with induction.

Divisibility

Induction also proves divisibility statements. The trick in the inductive step is to rewrite the expression for \(k + 1\) so that the expression for \(k\) appears inside it.

Theorem. For every \(n \ge 1\), \(5 \mid 6^n - 1\).

Proof. Base case: \(6^1 - 1 = 5\), which is divisible by 5. Inductive step: suppose \(5 \mid 6^k - 1\), so \(6^k - 1 = 5m\) for some integer \(m\). Then \(6^{k+1} - 1 = 6 \cdot 6^k - 1 = 6(6^k - 1) + 6 - 1 = 6 \cdot 5m + 5 = 5(6m + 1)\). So \(5 \mid 6^{k+1} - 1\). By induction the statement holds for all \(n \ge 1\). \(\blacksquare\)

The key move was writing \(6 \cdot 6^k - 1\) as \(6(6^k - 1) + 5\), which uses the inductive hypothesis directly. The same idea shows \((a - 1) \mid a^n - 1\) for every integer \(a\), although that also follows directly from the factorization \(a^n - 1 = (a - 1)(a^{n-1} + \dots + a + 1)\).

Starting somewhere other than 1

Some statements are true only from some point on. Induction works with any starting value \(n_0\): prove \(P(n_0)\), and prove \(P(k) \implies P(k + 1)\) for every \(k \ge n_0\). Then \(P(n)\) holds for all \(n \ge n_0\).

Theorem. For every integer \(n \ge 5\), \(2^n > n^2\).

Proof. Base case: \(2^5 = 32 > 25 = 5^2\). Inductive step: let \(k \ge 5\) and suppose \(2^k > k^2\). Then \(2^{k+1} = 2 \cdot 2^k > 2k^2\). We want \(2k^2 \ge (k + 1)^2 = k^2 + 2k + 1\), which is equivalent to \(k^2 - 2k - 1 \ge 0\), that is \((k - 1)^2 \ge 2\). This holds for \(k \ge 3\), and in particular for \(k \ge 5\). So \(2^{k+1} > 2k^2 \ge (k + 1)^2\). By induction, \(2^n > n^2\) for all \(n \ge 5\). \(\blacksquare\)

The statement fails for \(n = 2, 3, 4\): \(2^4 = 16 = 4^2\), not greater. That is why the base case is 5. Inequality proofs by induction usually have this shape: use the hypothesis to get a bound, then prove a separate, simpler inequality to finish.

Recursively defined sequences

Induction is the natural tool for sequences defined by a rule that gives each term from earlier ones. Define \(a_1 = 1\) and \(a_{n+1} = 2a_n + 1\). The first terms are 1, 3, 7, 15, 31, which suggests \(a_n = 2^n - 1\). Proof: the base case is \(a_1 = 1 = 2^1 - 1\). If \(a_k = 2^k - 1\), then \(a_{k+1} = 2(2^k - 1) + 1 = 2^{k+1} - 1\). This is the number of moves needed to solve the Tower of Hanoi puzzle with \(n\) discs: to move \(n + 1\) discs you move the top \(n\) aside, move the largest disc, and move the \(n\) discs back on top, so the move counts satisfy exactly this recursion.

What goes wrong

Both parts of an induction proof are essential. Without the base case the dominoes never start: the statement '\(n + 1 < n\)' has a valid inductive step (if \(k + 1 < k\) then \(k + 2 < k + 1\)), but it is false for every \(n\). Without a valid inductive step for every \(k\), the chain breaks. Here is a classic faulty proof that shows how subtle a break can be.

'Claim': all horses are the same color. 'Proof' by induction on the number \(n\) of horses in a group. Base case: one horse is the same color as itself. Inductive step: suppose any group of \(k\) horses is all one color, and take a group of \(k + 1\) horses. Remove one horse; the remaining \(k\) are one color. Put it back and remove a different horse; again the remaining \(k\) are one color. The two groups overlap, so all \(k + 1\) horses are the same color.

The error is in the inductive step for \(k = 1\). With two horses, removing one leaves horse A, and removing the other leaves horse B. The two groups of size 1 do not overlap, so nothing connects their colors. The step \(P(1) \implies P(2)\) fails, and the whole chain collapses. The lesson: check that your inductive step works for the smallest values of \(k\), not just for large ones.

Guessing and checking formulas

The code below computes the sums \(1^3 + 2^3 + \dots + n^3\) for small \(n\), compares them with the squares of the triangular numbers \(n(n+1)/2\), and finds that they agree, suggesting the beautiful identity \(1^3 + \dots + n^3 = (1 + \dots + n)^2\). It then checks the base case and the inductive step algebraically for many values of \(k\), the way you would check your algebra before writing it up. A computer check of finitely many \(k\) is not a proof, but it catches algebra mistakes quickly.

def tri(n):
    return n * (n + 1) // 2

print(" n  sum of cubes  triangle^2")
for n in range(1, 9):
    s = sum(i ** 3 for i in range(1, n + 1))
    print(f"{n:2d}  {s:11d}  {tri(n) ** 2:10d}")

# check the inductive step: tri(k)^2 + (k+1)^3 should equal tri(k+1)^2
print("step holds for k = 1..10000:", all(tri(k) ** 2 + (k + 1) ** 3 == tri(k + 1) ** 2 for k in range(1, 10001)))

# 2^n > n^2: find where it starts holding for good
print("n with 2^n <= n^2:", [n for n in range(1, 50) if 2 ** n <= n * n])

# Tower of Hanoi: recursion a(n+1) = 2a(n) + 1 against the closed form
a = [None, 1]
for n in range(1, 12):
    a.append(2 * a[n] + 1)
print("a_n == 2^n - 1 for n = 1..12:", all(a[n] == 2 ** n - 1 for n in range(1, 13)))

 n  sum of cubes  triangle^2
 1            1           1
 2            9           9
 3           36          36
 4          100         100
 5          225         225
 6          441         441
 7          784         784
 8         1296        1296
step holds for k = 1..10000: True
n with 2^n <= n^2: [2, 3, 4]
a_n == 2^n - 1 for n = 1..12: True

The identity for sums of cubes makes a good practice problem. In the inductive step you need \((\frac{k(k+1)}{2})^2 + (k + 1)^3 = (\frac{(k+1)(k+2)}{2})^2\); factor \((k + 1)^2/4\) out of the left side.