Discrete Math › Section E · Sequences › Topic E.5

Proof by induction

Checking a formula for a few values of n is evidence, not proof. Mathematical induction turns two finite checks, a starting case and a single general step, into a proof for infinitely many values of n at once.

From patterns to proofs

The earlier topics of this section found closed formulas by spotting patterns, fitting polynomials and unrolling recurrences. The circle-regions sequence in "Describing sequences and sums" showed why that is not enough: 1, 2, 4, 8, 16 looked like powers of 2 until the next term was 31. To be sure a formula holds for every \(n\), we need an argument that covers all \(n\) at once. Picture an endless row of dominoes. If the first one falls, and every domino that falls knocks over the next, then every domino falls. Induction is that picture made precise.

The principle of induction

Let \(P(n)\) be a statement about the integer \(n\), such as "\(n^3 + 2n\) is divisible by 3". To prove \(P(n)\) for all \(n \ge n_0\), prove two things. The base case: \(P(n_0)\) is true. The inductive step: for every \(k \ge n_0\), if \(P(k)\) is true then \(P(k + 1)\) is true. In the step, the assumption that \(P(k)\) holds is called the inductive hypothesis. You are not assuming what you want to prove; you are proving an implication, one that works for an arbitrary \(k\). The base case starts the chain and the step carries it on forever.

Writing an induction proof

A clear proof follows the same pattern every time. First, state \(P(n)\) and the range of \(n\). Second, check the base case by direct calculation. Third, fix an arbitrary \(k \ge n_0\) and write down the inductive hypothesis \(P(k)\) in full. Fourth, write down \(P(k + 1)\), the target, and work from one side of it towards the other, using the hypothesis at some point. Fifth, conclude: by induction, \(P(n)\) holds for all \(n \ge n_0\). The usual skill is spotting the \(k\) case hiding inside the \(k + 1\) case.

Worked example: the sum of the squares

The topic "Polynomial sequences" fitted \(1^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}\). Prove it for all \(n \ge 1\). 1. Base case \(n = 1\): the left side is 1 and the right side is \(\frac{1 \cdot 2 \cdot 3}{6} = 1\). 2. Hypothesis: \(1^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}\) for some \(k \ge 1\). 3. Add the next term, \((k + 1)^2\), to both sides and take out the factor \(k + 1\):

\frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{(k+1)(2k^2 + 7k + 6)}{6}

4. Since \(2k^2 + 7k + 6 = (k + 2)(2k + 3)\), this is exactly the formula with \(k + 1\) in place of \(n\). By induction the formula holds for all \(n \ge 1\).

Worked example: a divisibility proof

Prove that \(n^3 + 2n\) is divisible by 3 for every \(n \ge 0\). 1. Base case: \(0^3 + 0 = 0\), and 0 is divisible by 3. 2. Hypothesis: \(k^3 + 2k = 3m\) for some integer \(m\). 3. Expand the next case:

(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2.

4. Regroup to expose the hypothesis: this equals

(k^3 + 2k) + 3(k^2 + k + 1) = 3m + 3(k^2 + k + 1),

which is 3 times an integer. 5. So the statement passes from \(k\) to \(k + 1\), and by induction it holds for all \(n \ge 0\).

Worked example: an inequality with a later start

Prove \(n! > 2^n\) for all \(n \ge 4\). The claim fails for \(n = 0\) to 3 (for instance \(3! = 6 < 8\)), so the base case must be 4. 1. Base case: \(4! = 24 > 16 = 2^4\). 2. Hypothesis: \(k! > 2^k\) for some \(k \ge 4\). 3. Using the hypothesis,

(k + 1)! = (k + 1) \cdot k! > (k + 1) \cdot 2^k.

4. Since \(k + 1 \ge 5 > 2\), this is greater than \(2 \cdot 2^k = 2^{k+1}\). 5. So \((k + 1)! > 2^{k+1}\), and the inequality holds for all \(n \ge 4\). Inequality steps usually need one extra estimate like step 4.

Proving a recurrence's closed formula

Induction is the natural way to confirm a guess from unrolling. In "Exponential sequences and solving recurrences", \(a_n = 2a_{n-1} + 1\) with \(a_0 = 0\) was unrolled to the guess \(a_n = 2^n - 1\). Base case: \(2^0 - 1 = 0 = a_0\). Step: if \(a_k = 2^k - 1\), then

a_{k+1} = 2a_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 1.

That completes the proof. Recurrence and induction fit together naturally: the recurrence builds term \(k + 1\) from term \(k\), and the inductive step follows the same route.

Why induction is valid

Induction rests on the well-ordering principle: every non-empty set of natural numbers has a smallest element. Suppose the base case and the inductive step are both proved, yet \(P(n)\) fails for some \(n \ge n_0\). The failures form a non-empty set, so there is a smallest failure \(m\). It cannot be \(n_0\), since the base case holds, so \(m - 1 \ge n_0\) and \(P(m - 1)\) is true because \(m\) was the smallest failure. Then the inductive step forces \(P(m)\) to be true, a contradiction. So there are no failures at all.

Induction in computing: loop invariants

Programmers use induction to show that loops do what they claim. Consider: set \(s = 0\); then for \(i = 1\) to \(n\), add \(2i - 1\) to \(s\). The invariant is that after \(i\) passes, \(s = i^2\). Base: after 0 passes, \(s = 0 = 0^2\). Step: if \(s = i^2\) after \(i\) passes, the next pass adds \(2(i + 1) - 1\), and \(i^2 + 2i + 1 = (i + 1)^2\). So when the loop ends, \(s = n^2\): the sum of the first \(n\) odd numbers is \(n^2\). The base case is the state before the loop, and the step is one pass through it.

Common mistakes to avoid

First, skipping the base case. The claim "\(n + 1 < n\)" has a valid-looking step, since \(k + 1 < k\) implies \(k + 2 < k + 1\), yet it is false for every \(n\). Second, assuming \(P(k + 1)\) and working backwards to something true, which proves nothing. Third, a step that secretly fails for small \(k\). The fake proof that all horses are the same colour splits \(k + 1\) horses into two overlapping groups of \(k\), but when \(k + 1 = 2\) the groups share no horse, so the step from 1 to 2 breaks. Fourth, starting at the wrong base case.

Key takeaways

To prove \(P(n)\) for all \(n \ge n_0\), prove the base case \(P(n_0)\) and the inductive step "\(P(k)\) implies \(P(k + 1)\)" for an arbitrary \(k \ge n_0\). In the step, locate the \(k\) case inside the \(k + 1\) case, then apply the hypothesis. Induction proves sum formulas, divisibility facts, inequalities, closed formulas for recurrences, and loop invariants. It is valid because of the well-ordering principle, and it fails if the base case is missing or the step breaks for some \(k\).

Flashcards

Flashcard

Base case

Prove P(n₀) directly

The first domino falls.

Test your understanding

Question 1 of 5

In the inductive step of a proof that P(n) holds for all n ≥ 1, what may you assume?

Question 2 of 5

You want to prove n! > 2ⁿ by induction. Which base case should the proof use?

Question 3 of 5

To prove 1 + 3 + … + (2n − 1) = n², which expression must the step show equals (k + 1)²?

Question 4 of 5

The fake proof that all horses are the same colour splits k + 1 horses into two overlapping groups of k. Where does it fail?

Question 5 of 5

To prove that 5ⁿ − 1 is divisible by 4, which rewriting of 5ᵏ⁺¹ − 1 lets you use the hypothesis?

← Previous topicNext topic →