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)​

This is the formula with $n = k + 1$n=k+1. ✓

Conclusion: By mathematical induction, the result holds for all $n \geq 1$n≥1.

---

Type 2: Divisibility

Prove $6^n - 1$6n−1 is divisible by 5 for all $n \geq 1$n≥1.

Base case ($n = 1$n=1): $6^1 - 1 = 5$61−1=5, which is divisible by 5 ✓

Inductive hypothesis: Assume $6^k - 1 = 5m$6k−1=5m for some integer $m$m (i.e., $6^k = 5m + 1$6k=5m+1).

Inductive step: Consider $6^{k+1} - 1$6k+1−1:

$6^{k+1} - 1 = 6 \cdot 6^k - 1 = 6(5m + 1) - 1 = 30m + 6 - 1 = 30m + 5 = 5(6m + 1)$6k+1−1=6⋅6k−1=6(5m+1)−1=30m+6−1=30m+5=5(6m+1)

This is divisible by 5 ✓

Conclusion: By mathematical induction, $6^n - 1$6n−1 is divisible by 5 for all $n \geq 1$n≥1.

---

Type 3: Matrix Powers

Prove $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$(10​11​)n=(10​n1​) for all $n \geq 1$n≥1.

Base case ($n = 1$n=1): $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^1 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$(10​11​)1=(10​11​) ✓

Inductive hypothesis: Assume $A^k = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}$Ak=(10​k1​).

Inductive step: