Proof by Induction

Proof by mathematical induction

Proof by induction proves that a statement is true for all positive integers n. It works like dominoes: if the first one falls, and each falling domino knocks over the next, then all of them fall.

The four steps

1. Base case: show the statement is true for the first value (usually n = 1).

2. Assumption: assume the statement is true for n = k (the inductive hypothesis).

3. Inductive step: using the assumption, prove the statement is then true for n = k + 1.

4. Conclusion: state that since it's true for n = 1, and true for k+1 whenever true for k, it is true for all positive integers n by induction.

The conclusion must be written out fully — it's often worth a mark.

What can be proved

• Summation formulas, e.g. Σr = n(n+1)/2.
• Divisibility results, e.g. "n³ − n is divisible by 6".
• Matrix results, e.g. finding a general expression for Aⁿ.

Example structure (summation)

To prove Σ(r=1 to n) r = n(n+1)/2:

• Base (n=1): LHS = 1; RHS = 1(2)/2 = 1 ✓.
• Assume true for n = k: Σ(r=1 to k) r = k(k+1)/2.
• Step (n=k+1): Σ(r=1 to k+1) r = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 = the formula with n = k+1 ✓.
• Conclude by induction.

Divisibility technique

Show f(k+1) can be written as a multiple of the divisor plus (or built from) f(k). Often: consider f(k+1) − f(k) or f(k+1) − m·f(k) so the assumed divisibility of f(k) is used.

Worked example (outline)

Prove 2ⁿ > n for all n ≥ 1.

• Base n=1: 2 > 1 ✓.
• Assume 2ᵏ > k. Then 2^(k+1) = 2·2ᵏ > 2k ≥ k + 1 (for k ≥ 1). So true for k+1.
• By induction, 2ⁿ > n for all n ≥ 1. ✓

Common mistakes

• Forgetting the base case or the full conclusion.
• Not actually using the assumption (n=k) in the inductive step.
• Circular reasoning — assuming what you're trying to prove for n = k+1.

Exam tips

• Lay out all four steps clearly and label them.
• In the inductive step, substitute the assumption and manipulate to reach the (k+1) form.
• Always finish with the standard conclusion sentence.

Key facts to remember

• Induction proves a statement for all positive integers: base case → assume n = k → prove n = k+1 → conclude.
• Used for summation, divisibility and matrix results.
• Must use the assumption in the inductive step and write the full conclusion.