Mathematical Induction: How to Write a Proof

Mathematical induction is a favourite in FSc Part 1, A Level Further Maths and first-year university courses, and it is one of the few topics where the layout of your answer matters as much as the algebra. Once you learn the three-part structure, most induction proofs follow the same pattern. This guide shows you exactly how to write one that earns full marks.

The Idea Behind Induction

Imagine a long line of dominoes. If you can show that:

1. the first domino falls, and
2. whenever any domino falls, the next one falls too,

then every domino in the line will fall. Mathematical induction uses the same logic to prove that a statement \(P(n)\) is true for all natural numbers \(n \geq 1\) (or from some starting value).

The Three Steps of an Induction Proof

1. Base case: Show \(P(1)\) is true (or \(P(n_0)\) if the statement starts at \(n_0\)).
2. Inductive hypothesis: Assume \(P(k)\) is true for some natural number \(k\).
3. Inductive step: Using that assumption, prove \(P(k + 1)\) is true.

Then write a conclusion: by the principle of mathematical induction, \(P(n)\) is true for all \(n \geq 1\).

The inductive step is where most of the work happens. The trick is always to find \(P(k)\) hidden inside \(P(k+1)\) and replace it using your assumption.

Worked Example 1: Sum of the First \(n\) Natural Numbers

Prove that for all \(n \geq 1\):

$$ 1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2} $$

Step 1: Base case (\(n = 1\)).

Left side \(= 1\). Right side \(= \frac{1(1 + 1)}{2} = 1\). Both sides are equal, so \(P(1)\) is true.

Step 2: Inductive hypothesis. Assume \(P(k)\) is true:

$$ 1 + 2 + \cdots + k = \frac{k(k + 1)}{2} $$

Step 3: Inductive step. We must show:

$$ 1 + 2 + \cdots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2} $$

Start with the left side and use the hypothesis:

$$ \underbrace{1 + 2 + \cdots + k}_{= \frac{k(k+1)}{2}} + (k + 1) = \frac{k(k + 1)}{2} + (k + 1) $$

Take \((k + 1)\) as a common factor:

$$ = (k + 1)\left(\frac{k}{2} + 1\right) = (k + 1)\cdot\frac{k + 2}{2} = \frac{(k + 1)(k + 2)}{2} $$

This is the right side of \(P(k + 1)\).

Conclusion: Since \(P(1)\) is true and \(P(k) \Rightarrow P(k + 1)\), the result holds for all \(n \geq 1\) by mathematical induction.

Worked Example 2: Sum of Squares

Prove that for all \(n \geq 1\):

$$ 1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6} $$

Step 1: Base case. For \(n = 1\): left side \(= 1\); right side \(= \frac{1 \cdot 2 \cdot 3}{6} = 1\). True.

Step 2: Hypothesis. Assume

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

Step 3: Inductive step. We need the sum up to \((k + 1)^2\) to equal

$$ \frac{(k + 1)(k + 2)(2k + 3)}{6} $$

Add \((k + 1)^2\) to both sides of the hypothesis:

$$ \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 = \frac{(k + 1)\left[k(2k + 1) + 6(k + 1)\right]}{6} $$

Simplify the bracket:

$$ k(2k + 1) + 6(k + 1) = 2k^2 + k + 6k + 6 = 2k^2 + 7k + 6 $$

Factorise: \(2k^2 + 7k + 6 = (k + 2)(2k + 3)\). Check: \(2k^2 + 3k + 4k + 6 = 2k^2 + 7k + 6\). Correct.

$$ = \frac{(k + 1)(k + 2)(2k + 3)}{6} $$

This is exactly \(P(k + 1)\). Conclusion: the formula is true for all \(n \geq 1\).

Worked Example 3: A Divisibility Proof

Prove that \(5^n - 1\) is divisible by 4 for all \(n \geq 1\).

Step 1: Base case. For \(n = 1\): \(5^1 - 1 = 4\), which is divisible by 4. True.

Step 2: Hypothesis. Assume \(5^k - 1\) is divisible by 4, so

$$ 5^k - 1 = 4m \quad \text{for some integer } m $$

Step 3: Inductive step. Consider \(5^{k+1} - 1\). Rewrite it to bring \(5^k - 1\) into view:

$$ 5^{k+1} - 1 = 5 \cdot 5^k - 1 = 5(5^k - 1) + 5 - 1 = 5(5^k - 1) + 4 $$

Substitute the hypothesis:

$$ = 5(4m) + 4 = 4(5m + 1) $$

Since \(5m + 1\) is an integer, \(5^{k+1} - 1\) is divisible by 4.

Conclusion: by induction, \(5^n - 1\) is divisible by 4 for all \(n \geq 1\).

Common Mistakes

• Skipping the base case. Without it the proof is incomplete, even if the inductive step is perfect.
• Assuming what you need to prove. You assume \(P(k)\), never \(P(k + 1)\).
• Writing the target incorrectly. Replace every \(n\) with \(k + 1\) carefully, e.g. \(2n + 1\) becomes \(2k + 3\).
• Expanding everything. Factor out common terms like \((k + 1)\) early; it keeps the algebra short.
• Missing the conclusion sentence. Examiners expect it.

Tips

• Before starting the inductive step, write down the target expression for \(P(k + 1)\) so you know where you are heading.
• In divisibility proofs, use the "add and subtract" trick to create the expression from your hypothesis.
• If the statement starts at \(n = 2\) or \(n = 4\), use that as your base case.

Key Takeaways

• Induction has three parts: base case, inductive hypothesis and inductive step.
• In the inductive step, find \(P(k)\) inside \(P(k + 1)\) and substitute your assumption.
• Write the target form of \(P(k + 1)\) before you begin simplifying.
• Always finish with a clear conclusion referring to the principle of mathematical induction.

If you need help writing an induction proof for homework or an assignment, send your question to Amathify on WhatsApp or through the "Ask a Question" form. Our experts and PhD scholars will provide a neat, step-by-step proof you can learn from.