Mathematical Induction and Proof by Induction

The idea (the domino chain). Induction proves a statement $P(n)$ for every positive integer $n$ using a chain reaction: if the first domino falls (base case), and each domino knocks over the next (inductive step), then all dominoes fall. The trick is that you never check infinitely many cases — you check one, then prove the "knock-over" rule once.

The four steps you must write out:

Step 1 — Base case. Verify $P(n)$ is true for the smallest value, usually $n = 1$ (use the start value the question states). Show both sides equal.

Step 2 — Assumption (inductive hypothesis). Write the exact sentence: "Assume the result is true for $n = k$," and write down what that gives you. This is the fact you are allowed to use.

Step 3 — Inductive step. Prove the result holds for $n = k+1$, using the $n=k$ assumption. This is the only step with real algebra. Aim to manipulate the $n=k+1$ expression until it matches the target form with $k$ replaced by $k+1$.

Step 4 — Conclusion. Write the exact sentence: "Therefore, by the principle of mathematical induction, the result is true for all positive integers $n$."

Cambridge tip. The base case and conclusion sentences are "free" marks — they need no thinking, only memory. Write them first (top and bottom of your answer), then fill in the algebra of step 3. That way you can never forget them under time pressure.

Summation proofs. The statement is $\displaystyle\sum_{r=1}^{n} (\text{term}) = (\text{formula in } n)$. The key move in step 3:

$\sum_{r=1}^{k+1} (\text{term}) = \underbrace{\sum_{r=1}^{k} (\text{term})}_{\text{use the }n=k\text{ assumption}} + (\text{the }(k+1)\text{th term})$

Replace the sum-to-$k$ by the assumed formula, add the new term, then factorise to reach the target formula with $n=k+1$. For example, to prove $\sum_{r=1}^{n} r = \tfrac{1}{2}n(n+1)$, step 3 gives $\tfrac{1}{2}k(k+1) + (k+1) = (k+1)\big(\tfrac{1}{2}k + 1\big) = \tfrac{1}{2}(k+1)(k+2)$ — exactly the formula with $n=k+1$.

Divisibility proofs. The statement is "$f(n)$ is divisible by $d$" (e.g. $3^{2n} - 1$ divisible by $8$, or $n^3 + 2n$ divisible by $3$). Two reliable techniques:

• The $f(k+1) - f(k)$ method. Compute $f(k+1) - f(k)$ and show it is a multiple of $d$. Then $f(k+1) = f(k) + (\text{multiple of } d)$. Since $f(k)$ is a multiple of $d$ by assumption, so is $f(k+1)$.
• The direct multiple method. Use the assumption as $f(k) = d\,m$ for some integer $m$ (so $3^{2k} = 8m + 1$, say). Substitute into $f(k+1)$ and factor out $d$ explicitly, leaving an integer.

Worked sketch (divisibility). Prove $3^{2n} - 1$ is divisible by $8$. Assume $3^{2k} - 1 = 8m$, i.e. $3^{2k} = 8m+1$. Then $3^{2(k+1)} - 1 = 9\cdot 3^{2k} - 1 = 9(8m+1) - 1 = 72m + 8 = 8(9m+1),$ a multiple of $8$.

Cambridge tip. For divisibility, always end step 3 with the result written as $d \times (\text{an integer})$ — e.g. $8(9m+1)$. Examiners want to see the factor of $d$ pulled out explicitly; "it's divisible" without the factored form does not score the final mark.

Matrix-power proofs. The statement is $\mathbf{M}^n = (\text{a matrix with entries in } n)$. The inductive step uses $\mathbf{M}^{k+1} = \mathbf{M}^{k}\,\mathbf{M}$ (or $\mathbf{M}\,\mathbf{M}^{k}$):

$\mathbf{M}^{k+1} = \mathbf{M}^{k}\,\mathbf{M} = (\text{assumed form in } k)\times \mathbf{M}.$

Carry out the $2\times 2$ multiplication, simplify each entry, and check it matches the target form with $k$ replaced by $k+1$. For example, if $\mathbf{M} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$, the claim is $\mathbf{M}^{n} = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$, and $\mathbf{M}^{k+1} = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & k+1 \\ 0 & 1 \end{pmatrix}.$

$n$th-derivative proofs. The statement gives a formula for $\dfrac{d^n y}{dx^n}$. The inductive step differentiates the assumed $n=k$ derivative once more to obtain the $(k+1)$th derivative:

$\frac{d^{k+1}y}{dx^{k+1}} = \frac{d}{dx}\!\left(\frac{d^{k}y}{dx^{k}}\right) = \frac{d}{dx}(\text{assumed form in } k).$

For example, for $y = x e^{x}$ the claim is $\dfrac{d^n y}{dx^n} = (x+n)e^{x}$; differentiating $(x+k)e^x$ by the product rule gives $e^x + (x+k)e^x = (x + k + 1)e^x$ — the form with $n=k+1$.

Cambridge tip. Matrix multiplication is non-commutative, so write $\mathbf{M}^{k+1} = \mathbf{M}^{k}\mathbf{M}$ in the order you intend and keep it consistent. For derivative proofs, name the rule you use (product/chain rule) — it makes the method mark unambiguous.

Sequence / recurrence proofs. A sequence is defined by a recurrence such as $u_{n+1} = 2u_n + 1$ with $u_1 = 1$, and you are asked to prove a closed form, e.g. $u_n = 2^n - 1$. In step 3 you use both the assumption ($u_k = 2^k - 1$) and the recurrence: $u_{k+1} = 2u_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1,$ which is the closed form with $n = k+1$. The recurrence is the bridge from $u_k$ to $u_{k+1}$ — without it you cannot make the inductive step.

Conjecture-then-prove. Some questions ask you to find the result first. Compute the first few cases, spot the pattern, state your conjecture clearly as a formula in $n$, then prove it by induction. The marks split: a few for a correct conjecture, the rest for the proof.

The conclusion discipline (where marks vanish). Examiner reports return to this every series: candidates do flawless algebra in step 3 and then either (i) forget the $n=k$ assumption statement, or (ii) stop without the conclusion. Both cost a mark every time. Train yourself to write, verbatim:

"Therefore, by the principle of mathematical induction, the result is true for all positive integers $n$."

A good closing sentence also names why the induction completes: "the result is true for $n=1$, and true for $n=k+1$ whenever it is true for $n=k$; hence by induction…".

Cambridge tip. If the question gives a recurrence, your step 3 must invoke it — a recurrence proof that never writes "$u_{k+1} = \ldots$ (using the recurrence)" is incomplete and will be capped.