Proof by Induction

Proof by Induction: Learning Outcomes

Prove results using mathematical induction.

Establish simple identities such as:
- the sum of the first \(n\) natural numbers;
- the sum of a finite geometric series.
Establish factorisation results such as: 3 is a factor of \(4^{n}-1\).
Prove inequalities such as:
- \(n! > 2^{n}\), \quad \(2^{n} \ge n^{2}\) for \(n \ge 4\);
- \((1+x)^{n} \ge 1+nx,\quad x > -1.\)
Prove De Moivre’s Theorem by induction for \(n \in \mathbb{N}\): \[ (\cos\theta + i\sin\theta)^{n} = \cos(n\theta) + i\sin(n\theta). \]

Mathematical Induction — Three Proofs

1. Formula for the sum of a series

Prove by induction that \[ 1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6},\qquad n\in\mathbb{N}. \]

Show solution Hide solution

Base case \(n=1\). \(1^2=1=\dfrac{1\cdot2\cdot3}{6}\).

Inductive hypothesis. Assume \(\displaystyle 1^2+\cdots+k^2=\frac{k(k+1)(2k+1)}{6}\).

Inductive step. \[ \begin{aligned} 1^2+\cdots+k^2+(k+1)^2 &=\frac{k(k+1)(2k+1)}{6}+(k+1)^2\\ &=\frac{(k+1)\big(2k^2+7k+6\big)}{6}\\ &=\frac{(k+1)(k+2)(2k+3)}{6}\\ &=\frac{(k+1)\big((k+1)+1\big)\big(2(k+1)+1\big)}{6}. \end{aligned} \] Hence true for \(k+1\).

Conclusion. True for all \(n\in\mathbb{N}\).

2. Divisibility proofs

Prove by induction that \(5^n-4n+15\) is divisible by \(16\), for all \(n\in\mathbb{N}\).

Show solution Hide solution

Base case \(n=1\). \(5-4+15=16\) is divisible by \(16\).

Inductive hypothesis. \(5^k-4k+15=16m\) for some \(m\in\mathbb{Z}\).

Inductive step. \[ \begin{aligned} 5^{k+1}-4(k+1)+15 &=5\cdot5^k-4k-4+15\\ &=5(5^k-4k+15)+16k-64\\ &=5\cdot16m+16k-64\\ &=16(5m+k-4), \end{aligned} \] a multiple of \(16\). Therefore true for \(k+1\).

Conclusion. \(16\mid(5^n-4n+15)\) for all \(n\in\mathbb{N}\).

3. Inequality proofs

Prove by induction that \(2^n>2n+1\) for all \(n\ge3\).

Show solution Hide solution

Base case \(n=3\). \(2^3=8>7=2\cdot3+1\).

Inductive hypothesis. Assume \(2^k>2k+1\) for some \(k\ge3\).

Inductive step. \[ 2^{k+1}=2\cdot 2^k > 2(2k+1)=4k+2 \ge 2k+3=2(k+1)+1, \] since \(k\ge3\Rightarrow 4k+2-(2k+3)=2k-1\ge5\).

Conclusion. \(2^n>2n+1\) for all \(n\ge3\).

4. De Moivre’s Theorem

Prove by induction that, for all \(n\in\mathbb{N}\) and \(\theta\in\mathbb{R}\), \[ \big(\cos\theta+i\sin\theta\big)^{n} =\cos(n\theta)+i\sin(n\theta). \]

Show solution Hide solution

Base case (\(n=1\)). \(\big(\cos\theta+i\sin\theta\big)^1=\cos\theta+i\sin\theta\), which equals \(\cos(1\theta)+i\sin(1\theta)\). True.

Inductive hypothesis. Assume that for some \(k\in\mathbb{N}\), \[ \big(\cos\theta+i\sin\theta\big)^{k} =\cos(k\theta)+i\sin(k\theta). \]

Inductive step. Then \[ \begin{aligned} \big(\cos\theta+i\sin\theta\big)^{k+1} &=\big(\cos\theta+i\sin\theta\big)\big(\cos(k\theta)+i\sin(k\theta)\big)\\ &=\underbrace{\cos\theta\cos(k\theta)-\sin\theta\sin(k\theta)}_{\text{real part}} +\,i\,\underbrace{\big(\sin\theta\cos(k\theta)+\cos\theta\sin(k\theta)\big)}_{\text{imag part}}\\[2mm] &=\cos\!\big((k+1)\theta\big)+i\sin\!\big((k+1)\theta\big), \end{aligned} \] by the angle–addition formulae \(\cos(A+B)=\cos A\cos B-\sin A\sin B\) and \(\sin(A+B)=\sin A\cos B+\cos A\sin B\).

Conclusion. By mathematical induction, \(\big(\cos\theta+i\sin\theta\big)^{n}=\cos(n\theta)+i\sin(n\theta)\) for all \(n\in\mathbb{N}\).

Remark. The result extends to all integers \(n\in\mathbb{Z}\) using \(\big(\cos\theta+i\sin\theta\big)^{-n} =\big(\cos\theta-i\sin\theta\big)^{n} =\cos(n\theta)-i\sin(n\theta)\).

2024 (Deferred) — Prove the sum of the first \(n\) natural numbers

Prove by induction that \[ 1+2+3+\cdots+n=\frac{n(n+1)}{2}. \]

Base case (\(n=1\)). LHS \(=1\). RHS \(=\dfrac{1(1+1)}{2}=1\). ✓

Inductive step. Assume true for \(n=k\): \[ 1+2+\cdots+k=\frac{k(k+1)}{2}. \] Then for \(n=k+1\), \[ 1+2+\cdots+k+(k+1)=\frac{k(k+1)}{2}+(k+1) =(k+1)\Big(\frac{k}{2}+1\Big) =\frac{(k+1)(k+2)}{2}. \] This is the required formula with \(n=k+1\).

Conclusion. By mathematical induction, the result holds for all \(n\in\mathbb N\).

2023 (Deferred) — Divisibility of \(13^n-1\) by \(12\)

Prove by induction that \(13^n-1\) is divisible by \(12\) for all \(n\in\mathbb N\).

Base case (\(n=1\)). \(13^1-1=12\), divisible by \(12\). ✓

Inductive step. Suppose \(13^k-1=12m\) for some integer \(m\). Then \[ 13^{k+1}-1=13(13^k)-1=13(12m+1)-1=156m+12=12(13m+1), \] which is divisible by \(12\).

Conclusion. Hence \(12\mid(13^n-1)\) for all \(n\in\mathbb N\).

2022 (Deferred) — Powers of an odd number are odd

Assume \(t\) is a positive odd number. Prove by induction that \(t^n\) is odd for all \(n\in\mathbb N\).

Base case (\(n=1\)). \(t^1=t\) is odd. ✓

Inductive step. Assume \(t^k\) is odd. Write \(t=2r+1\) and \(t^k=2s+1\) for integers \(r,s\). Then \[ t^{k+1}=t^k\cdot t=(2s+1)(2r+1)=4rs+2r+2s+1=2(2rs+r+s)+1, \] an odd number.

Conclusion. Therefore \(t^n\) is odd for all \(n\in\mathbb N\).

2021 — Divisibility of \(2^{3n-1}+3\) by \(7\)

Prove using induction that \(2^{3n-1}+3\) is divisible by \(7\) for all \(n\in\mathbb N\).

Base case (\(n=1\)). \(2^{2}+3=4+3=7\), divisible by \(7\). ✓

Inductive step. Suppose \(a_k=2^{3k-1}+3\) is divisible by \(7\). Then \[ a_{k+1}=2^{3(k+1)-1}+3=2^{3k+2}+3=8\cdot2^{3k-1}+3 =8(a_k-3)+3=8a_k-21. \] If \(7\mid a_k\) then \(7\mid 8a_k\) and \(7\mid 21\), hence \(7\mid(8a_k-21)=a_{k+1}\).

Conclusion. By induction, \(7\mid(2^{3n-1}+3)\) for all \(n\in\mathbb N\).

2020 — Sum of the first \(n\) squares

Prove by induction that \[ 1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}. \]

Base case (\(n=1\)). LHS \(=1\). RHS \(=\dfrac{1\cdot2\cdot3}{6}=1\). ✓

Inductive step. Assume \[ 1^2+\cdots+k^2=\frac{k(k+1)(2k+1)}{6}. \] Then \[ 1^2+\cdots+k^2+(k+1)^2 =\frac{k(k+1)(2k+1)}{6}+(k+1)^2 =\frac{(k+1)\big(k(2k+1)+6(k+1)\big)}{6} \] \[ =\frac{(k+1)\big(2k^2+k+6k+6\big)}{6} =\frac{(k+1)\big(2k^2+7k+6\big)}{6} =\frac{(k+1)(k+2)(2k+3)}{6} =\frac{(k+1)\big((k+1)+1\big)\big(2(k+1)+1\big)}{6}. \]

Conclusion. The result holds for all \(n\in\mathbb N\).

2018 — De Moivre’s Theorem (inductive form)

Prove, using induction, that for \(n\in\mathbb N\), \[ (\cos\theta+i\sin\theta)^n=\cos(n\theta)+i\sin(n\theta). \]

Base case (\(n=1\)). Trivial equality. ✓

Inductive step. Assume true for \(n=k\). Then \[ (\cos\theta+i\sin\theta)^{k+1} =(\cos\theta+i\sin\theta)^k(\cos\theta+i\sin\theta) \] \[ =\big(\cos(k\theta)+i\sin(k\theta)\big)(\cos\theta+i\sin\theta) \] \[ =\big(\cos k\theta\cos\theta-\sin k\theta\sin\theta\big) + i\big(\sin k\theta\cos\theta+\cos k\theta\sin\theta\big) \] \[ =\cos\big((k+1)\theta\big)+i\sin\big((k+1)\theta\big), \] by the angle-addition formulae.

Conclusion. Hence the identity holds for all \(n\in\mathbb N\).

2016 — Divisibility of \(8^n-1\) by \(7\)

Prove by induction that \(8^n-1\) is divisible by \(7\) for all \(n\in\mathbb N\).

Base case (\(n=1\)). \(8-1=7\), divisible by \(7\). ✓

Inductive step. Suppose \(8^k-1=7m\). Then \[ 8^{k+1}-1=8\cdot8^k-1=8(7m+1)-1=56m+7=7(8m+1), \] divisible by \(7\).

Conclusion. Therefore \(7\mid(8^n-1)\) for all \(n\in\mathbb N\).

2014 — Sum of the first \(n\) natural numbers

Prove by induction that \[ 1+2+\cdots+n=\frac{n(n+1)}{2}. \]

Base case (\(n=1\)). Holds: \(1=\frac{1\cdot2}{2}\).

Inductive step. Assume \(1+\cdots+k=\dfrac{k(k+1)}{2}\). Then \[ 1+\cdots+k+(k+1)=\frac{k(k+1)}{2}+(k+1) =\frac{(k+1)(k+2)}{2}. \]

Conclusion. True for all \(n\in\mathbb N\).

2014 (Sample) — Sum of the first \(n\) natural numbers

Prove by induction that \[ 1+2+\cdots+n=\frac{n(n+1)}{2}. \]

Base case. \(n=1\) gives \(1=1\).

Inductive step. Same algebra as the 2014 card above yields \(\dfrac{(k+1)(k+2)}{2}\).

Conclusion. Result follows for all \(n\).

2013 (Sample) — Sigma form of the sum

Prove by induction that \[ \sum_{r=1}^{n} r=\frac{n(n+1)}{2}. \]

Base case. \(n=1:\ \sum_{r=1}^1 r=1=\frac{1\cdot2}{2}\).

Inductive step. Assume \(\sum_{r=1}^{k} r=\dfrac{k(k+1)}{2}\). Then \[ \sum_{r=1}^{k+1} r=\Big(\sum_{r=1}^{k} r\Big)+(k+1) =\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}. \]

Conclusion. Hence the formula holds for all \(n\in\mathbb N\).