Proof by Mathematical Induction

Mathematical induction is a method of proof used to establish that a statement $P(n)$P(n) is true for all positive integers $n \geq n_0$n≥n0​. It is one of the most important proof techniques in Further Mathematics.

---

The Structure of a Proof by Induction

1. Base case: Verify that $P(n_0)$P(n0​) is true (usually $n_0 = 1$n0​=1).
2. Inductive hypothesis: Assume $P(k)$P(k) is true for some integer $k \geq n_0$k≥n0​.
3. Inductive step: Using the assumption that $P(k)$P(k) is true, prove that $P(k+1)$P(k+1) is true.
4. Conclusion: By the principle of mathematical induction, $P(n)$P(n) is true for all $n \geq n_0$n≥n0​.

Key Point: You must state all four parts explicitly to earn full marks.

---

Type 1: Summation Formulae

Prove $\sum_{r=1}^{n} r = \frac{n(n+1)}{2}$∑r=1n​r=2n(n+1)​ for all $n \geq 1$n≥1.

Base case ($n = 1$n=1): LHS = 1. RHS = $\frac{1 \cdot 2}{2} = 1$21⋅2​=1. LHS = RHS ✓

Inductive hypothesis: Assume $\sum_{r=1}^{k} r = \frac{k(k+1)}{2}$∑r=1k​r=2k(k+1)​ for some $k \geq 1$k≥1.

Inductive step: Consider $\sum_{r=1}^{k+1} r$∑r=1k+1​r:

$\sum_{r=1}^{k+1} r = \sum_{r=1}^{k} r + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$∑r=1k+1​r=∑r=1k​r+(k+1)=2k(k+1)​+(k+1)=2k(k+1)+2(k+1)​=2(k+1)(k+2)​