Mathematical induction
Master mathematical induction for Year 12 Specialist Mathematics in Queensland (QCAA, Unit 3). Induction is the rigorous way to prove a statement is true for every positive integer, working through a base case, an assumption at ‘n equals k’ and an inductive step to ‘n equals k plus 1’.
You will learn the four stages of an induction proof and apply them to summation formulae, divisibility results, inequalities and De Moivre’s theorem — the proof technique that underpins much of the Unit 3 and Unit 4 work that follows.
Theory
Mathematical induction is the method used in Year 12 Specialist Mathematics (QCAA, Queensland, Unit 3) to prove a statement \(P(n)\) is true for every positive integer \(n\). You verify a base case, assume the statement at \(n=k\), then prove it follows at \(n=k+1\). This page shows the four stages applied to summation formulae, divisibility results and inequalities.
Mathematical induction proves that a statement \(P(n)\) holds for every positive integer \(n\) without checking infinitely many cases. Think of a row of dominoes: knock over the first, and make sure each one topples the next, and the whole row falls.
Every induction proof has four stages. The base case (or initial statement) shows \(P(1)\) is true. The inductive assumption (hypothesis) supposes \(P(k)\) is true for some positive integer \(k\). The inductive step uses that assumption to prove \(P(k+1)\) must also be true. The conclusion then states \(P(n)\) is true for all \(n\ge 1\).
Sigma notation \(\sum_{r=1}^{n} f(r)\) is the compact way to write a sum: it means \(f(1)+f(2)+\cdots+f(n)\). Induction is the standard tool for proving a closed form for such a sum, for example \(\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}\).
The method proves three main kinds of result in this course: summation formulae (closed forms for a sum), divisibility results (an expression is always a multiple of a fixed integer), and inequalities. It also proves De Moivre's theorem for positive integer powers.
The principle of mathematical induction: if \(P(1)\) is true, and \(P(k)\Rightarrow P(k+1)\) for every \(k\ge 1\), then \(P(n)\) is true for all positive integers \(n\).
Standard summation results proved by induction:
De Moivre's theorem (proved by induction for positive integers \(n\)):
How to run an induction proof
- Base case: substitute \(n=1\) into both sides (or the expression) and show \(P(1)\) is true.
- Assume: write the inductive assumption — suppose \(P(k)\) is true for some positive integer \(k\).
- Inductive step: starting from the \(n=k+1\) expression, substitute the assumption and simplify until you reach the \(P(k+1)\) form.
- Conclude: since \(P(1)\) holds and \(P(k)\Rightarrow P(k+1)\), state that \(P(n)\) is true for all \(n\ge 1\).
Base case \(n=1\): check both sides are equal.
| \(\text{LHS}\) | \(=\) | \(\sum_{r=1}^{1} r = 1\) |
| \(\text{RHS}\) | \(=\) | \(\dfrac{1(1+1)}{2}\) |
| \(=\) | \(1 \quad\checkmark\) |
Assume \(n=k\): suppose the formula holds for \(k\).
| \(\sum_{r=1}^{k} r\) | \(=\) | \(\dfrac{k(k+1)}{2}\) |
Inductive step \(n=k+1\): add the next term \((k+1)\) and simplify.
| \(\sum_{r=1}^{k+1} r\) | \(=\) | \(\dfrac{k(k+1)}{2}+(k+1)\) |
| \(=\) | \(\dfrac{k(k+1)+2(k+1)}{2}\) | |
| \(=\) | \(\dfrac{(k+1)(k+2)}{2}\) |
This is the formula with \(k+1\) in place of \(n\), so \(P(k)\Rightarrow P(k+1)\); with the base case, it holds for all \(n\ge 1\).
Base case \(n=1\): evaluate the expression.
| \(5^{1}-1\) | \(=\) | \(4\) |
| \(=\) | \(4\times 1 \quad\checkmark\) |
Assume \(n=k\): suppose \(4\) divides \(5^{k}-1\), i.e. \(5^{k}-1=4m\) for an integer \(m\).
| \(5^{k}-1\) | \(=\) | \(4m\) |
| \(5^{k}\) | \(=\) | \(4m+1\) |
Inductive step \(n=k+1\): build \(5^{k+1}-1\) from the assumption.
| \(5^{k+1}-1\) | \(=\) | \(5\cdot 5^{k}-1\) |
| \(=\) | \(5(4m+1)-1\) | |
| \(=\) | \(20m+4\) | |
| \(=\) | \(4(5m+1)\) |
\(4(5m+1)\) is a multiple of \(4\), so \(P(k)\Rightarrow P(k+1)\); with the base case, \(5^{n}-1\) is divisible by \(4\) for all \(n\ge 1\).
Base case \(n=1\): the two sides match.
| \(z^{1}\) | \(=\) | \(\cos\theta+i\sin\theta\) |
| \(\cos(1\theta)+i\sin(1\theta)\) | \(=\) | \(\cos\theta+i\sin\theta \quad\checkmark\) |
Assume \(n=k\): suppose \(z^{k}=\cos k\theta+i\sin k\theta\).
| \(z^{k}\) | \(=\) | \(\cos k\theta+i\sin k\theta\) |
Inductive step \(n=k+1\): multiply the assumption by \(z\) and use the compound-angle identities.
| \(z^{k+1}\) | \(=\) | \(z^{k}\cdot z\) |
| \(=\) | \((\cos k\theta+i\sin k\theta)(\cos\theta+i\sin\theta)\) | |
| \(=\) | \((\cos k\theta\cos\theta-\sin k\theta\sin\theta)\) | |
| \(+\) | \(i(\sin k\theta\cos\theta+\cos k\theta\sin\theta)\) | |
| \(=\) | \(\cos(k+1)\theta+i\sin(k+1)\theta\) |
This is the result at \(n=k+1\), so \(P(k)\Rightarrow P(k+1)\); with the base case, De Moivre's theorem holds for all \(n\ge 1\).
Base case \(n=1\): compare the two sides.
| \(2^{1}\) | \(=\) | \(2\) |
| \(n+1\) | \(=\) | \(1+1=2\) |
| \(2\) | \(\ge\) | \(2 \quad\checkmark\) |
Assume \(n=k\): suppose \(2^{k}\ge k+1\).
| \(2^{k}\) | \(\ge\) | \(k+1\) |
Inductive step \(n=k+1\): double the assumption, then compare.
| \(2^{k+1}\) | \(=\) | \(2\cdot 2^{k}\) |
| \(\ge\) | \(2(k+1)\) | |
| \(=\) | \((k+1)+(k+1)\) | |
| \(\ge\) | \((k+1)+1\) |
The last line uses \(k+1\ge 1\); so \(2^{k+1}\ge (k+1)+1\), giving \(P(k)\Rightarrow P(k+1)\). With the base case, \(2^{n}\ge n+1\) for all \(n\ge 1\).
Common pitfalls
Frequently asked questions
What are the four steps of proof by mathematical induction?
Base case (show \(P(1)\) is true), inductive assumption (assume \(P(k)\) is true for some \(k\)), inductive step (prove \(P(k+1)\) follows), and conclusion (\(P(n)\) is true for all \(n\ge 1\)).
What is the inductive assumption (inductive hypothesis)?
It is the supposition that the statement \(P(k)\) is true for some positive integer \(k\). You then use it to prove \(P(k+1)\).
Why do we only assume \(P(k)\) and not \(P(n)\) for all \(n\)?
Assuming \(P(n)\) for all \(n\) assumes the very thing you are trying to prove, which is circular. Induction only supposes one case, \(P(k)\), and shows it forces the next.
What does sigma notation mean?
The sum \(\sum_{r=1}^{n} f(r)\) means \(f(1)+f(2)+\cdots+f(n)\): substitute \(r=1,2,\dots,n\) and add the terms.
How do you prove a divisibility result by induction?
Show the base case is a multiple of the divisor, assume \(P(k)\) as "expression \(=d\times m\)", then rewrite the \(n=k+1\) expression using that assumption until it factorises as \(d\times(\text{integer})\).
How is De Moivre's theorem proved by induction?
The base case \(n=1\) is immediate; assuming \((\cos\theta+i\sin\theta)^{k}=\cos k\theta+i\sin k\theta\), multiply by \((\cos\theta+i\sin\theta)\) and use the compound-angle identities to reach the \(k+1\) case.