Proof by Mathematical Induction
Knock down the first domino, show each domino knocks down the next, and every domino falls — induction proves infinitely many statements with one finite argument.
The principle of induction
To prove a statement $P(n)$ is true for all integers $n\geq n_0$: (1) Basis — show $P(n_0)$ is true. (2) Assumption — assume $P(k)$ is true for some $k\geq n_0$. (3) Inductive step — use this assumption to show $P(k+1)$ is true. (4) Conclusion — state that since $P(n_0)$ holds and $P(k)\Rightarrow P(k+1)$, $P(n)$ is true for all $n\geq n_0$ by induction.
All four steps must be present to earn full marks, and step 4 (the conclusion) must explicitly mention both the base case and the inductive step — stating only "true by induction" without this justification is a common way to lose marks.
Basis ($n=1$): LHS $=1^2=1$. RHS $=\dfrac{1(2)(3)}{6}=1$. True for $n=1$.
Assumption: assume $\displaystyle\sum_{r=1}^{k}r^2=\frac{k(k+1)(2k+1)}{6}$ for some $k\geq1$.
Inductive step:
$=\dfrac{(k+1)(2k^2+7k+6)}{6}=\dfrac{(k+1)(k+2)(2k+3)}{6}$, which is the required formula with $n=k+1$.
Conclusion: since the statement is true for $n=1$, and true for $n=k+1$ whenever it is true for $n=k$, by induction the statement is true for all positive integers $n$.
Basis ($n=1$): LHS $=1(2)=2$. RHS $=\dfrac{1(2)(3)}{3}=2$. True.
Assumption: assume true for $n=k$: $\displaystyle\sum_{r=1}^{k}r(r+1)=\frac{k(k+1)(k+2)}{3}$.
Inductive step: $\displaystyle\sum_{r=1}^{k+1}r(r+1)=\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)=\frac{(k+1)(k+2)(k+3)}{3}$, matching the formula at $n=k+1$.
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so true for all positive integers $n$ by induction.
A non-series example: sum of an inequality
Basis ($n=5$): $2^5=32$, $5^2=25$. $32>25$ ✓, true.
Assumption: assume $2^k>k^2$ for some $k\geq5$.
Inductive step: $2^{k+1}=2\cdot2^k>2k^2$ (using the assumption). Need to show $2k^2\geq(k+1)^2=k^2+2k+1$, i.e. $k^2-2k-1\geq0$.
For $k\geq5$: $k^2-2k-1=k(k-2)-1\geq5(3)-1=14>0$, so the inequality holds, giving $2^{k+1}>2k^2\geq(k+1)^2$.
Conclusion: true for $n=5$; true for $n=k+1$ whenever true for $n=k$ (for $k\geq5$); so true for all integers $n\geq5$ by induction.
Starting the basis case at $n=1$ when the question specifies a different starting value (e.g. $n\geq5$ above) is a frequent error — always check the required range of $n$ before choosing the base case, and state clearly which value of $n$ the basis step verifies.
Basis ($n=1$): LHS $=1$. RHS $=\dfrac{(1)(1)(2)}{2}=1$. True.
Assumption: assume $\displaystyle\sum_{r=1}^{k}(-1)^{r+1}r^2=\frac{(-1)^{k+1}k(k+1)}{2}$.
Inductive step: $\displaystyle\sum_{r=1}^{k+1}(-1)^{r+1}r^2=\frac{(-1)^{k+1}k(k+1)}{2}+(-1)^{k+2}(k+1)^2$
$=(-1)^{k+2}(k+1)\left[-\dfrac{k}{2}+(k+1)\right]=(-1)^{k+2}(k+1)\cdot\dfrac{k+2}{2}=\dfrac{(-1)^{(k+1)+1}(k+1)(k+2)}{2}$, matching the formula at $n=k+1$.
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so true for all positive integers $n$ by induction.
Spotting a flawed induction proof
A favourite examiner trap is a "proof" where the inductive step is algebraically correct, but the basis case was never actually checked against the claimed formula — or was checked against the wrong thing. Since the inductive step only shows that if the statement holds for $n=k$ then it holds for $n=k+1$, without a genuine, independently verified basis case the whole chain never starts, and the "proof" establishes nothing at all.
The inductive step shown is algebraically valid — if the formula holds for $n=k$, it does follow for $n=k+1$. The flaw is that the basis case was never checked. Testing $n=1$: LHS $=\sum_{r=1}^{1}(2r+1)=3$, but the claimed formula gives RHS $=1^2+2(1)+2=5$. Since $3\neq5$, the formula is false at $n=1$, so the "proof" has no valid starting point — the chain of implications is never triggered, and the conclusion is unjustified.
The correct formula is in fact $\displaystyle\sum_{r=1}^{n}(2r+1)=n^2+2n$ (also easily proved by induction, with a genuine basis case at $n=1$: LHS $=3$, RHS $=1+2=3$ ✓).
Exam-style questions
Question 1 7 marks
Prove by induction that $\displaystyle\sum_{r=1}^{n}r^3=\left[\frac{n(n+1)}{2}\right]^2$ for all positive integers $n$.
Basis ($n=1$): LHS $=1$. RHS $=1^2=1$. True. (B1)
Assumption: assume $\displaystyle\sum_{r=1}^{k}r^3=\left[\frac{k(k+1)}{2}\right]^2$. (M1)
Inductive step: $\displaystyle\sum_{r=1}^{k+1}r^3=\left[\frac{k(k+1)}{2}\right]^2+(k+1)^3=\frac{(k+1)^2\big[k^2+4(k+1)\big]}{4}=\frac{(k+1)^2(k+2)^2}{4}=\left[\frac{(k+1)(k+2)}{2}\right]^2$ (M1, A1, A1)
This matches the formula with $n=k+1$. (A1)
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so true for all positive integers $n$. (B1)
Question 2 6 marks
Prove by induction that $\displaystyle\sum_{r=1}^{n}(4r-1)=n(2n+1)$ for all positive integers $n$.
Basis ($n=1$): LHS $=\displaystyle\sum_{r=1}^{1}(4r-1)=3$. RHS $=1(3)=3$. True. (B1)
Assumption: assume $\displaystyle\sum_{r=1}^{k}(4r-1)=k(2k+1)$. (M1)
Inductive step: $\displaystyle\sum_{r=1}^{k+1}(4r-1)=k(2k+1)+\big(4(k+1)-1\big)=2k^2+5k+3=(k+1)(2k+3)$, matching the formula at $n=k+1$. (M1, A1, A1)
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so true for all positive integers $n$. (B1)
Question 3 6 marks
Prove by induction that $\displaystyle\sum_{r=1}^{n}r\cdot2^r=(n-1)2^{n+1}+2$ for all positive integers $n$.
Basis ($n=1$): LHS $=1\cdot2^1=2$. RHS $=(0)2^2+2=2$. True. (B1)
Assumption: assume $\displaystyle\sum_{r=1}^{k}r\cdot2^r=(k-1)2^{k+1}+2$. (M1)
Inductive step: $\displaystyle\sum_{r=1}^{k+1}r\cdot2^r=(k-1)2^{k+1}+2+(k+1)2^{k+1}=2^{k+1}\big[(k-1)+(k+1)\big]+2=2^{k+1}(2k)+2=k\cdot2^{k+2}+2$ (M1, A1)
$=\big((k+1)-1\big)2^{(k+1)+1}+2$, matching the formula at $n=k+1$. (A1)
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so true for all positive integers $n$. (B1)