Mathematical Induction — Structure & Review
A line of dominoes only falls if (a) the first one is pushed and (b) every domino knocks over the next. Mathematical induction is exactly this argument, formalised. In Ext 1 you used it for sums; in Ext 2 you'll use it on inequalities and divisibility. This lesson nails the three-step structure so your proofs lose zero marks on form.
From your Ext 1 work: to prove $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ for all $n \geq 1$. Before reading on — what are the three named steps of an induction proof, and which one is the part that students most often skip or fumble? Write your answer below.
Every induction question rewards two habits: state $P(n)$ clearly at the start, then write the inductive step as a single logical chain that begins with the IH and ends at $P(k+1)$. Skipping either of these costs structural marks regardless of how clever the algebra is.
The state-and-chain strategy: (1) name the proposition $P(n)$ explicitly, (2) prove $P(1)$ by direct evaluation, (3) assume $P(k)$ holds (the IH), (4) derive $P(k+1)$ in a chain that uses the IH at least once.
Base: $P(1)$ · IH: assume $P(k)$ · Step: $P(k) \Rightarrow P(k+1)$
Key facts
- The three steps: base case, inductive hypothesis (IH), inductive step
- The conclusion line: "Hence by induction, $P(n)$ is true for all $n \geq n_0$"
- The IH is assumed, not proved — it is the premise of the step
Concepts
- Why both the base case AND the inductive step are required (dominoes analogy)
- Why the IH must be used somewhere in the inductive step
- Why the form of $P(n)$ must be stated before any algebra begins
Skills
- Write a fully structured proof for a sum identity by induction
- Identify and correct the common structural errors in a draft proof
- Apply the template: state, base, assume, show, conclude
Every HSC induction proof follows the same skeleton. Memorise this and your structural marks become automatic.
- State. "Let $P(n)$ be the statement [identity, inequality, or divisibility claim] for $n \geq n_0$."
- Base. "When $n = n_0$: LHS $= \dots$, RHS $= \dots$. So $P(n_0)$ is true."
- Assume. "Assume $P(k)$ is true for some integer $k \geq n_0$, i.e. [write the IH explicitly]."
- Show. "Required to show $P(k+1)$, i.e. [write the goal explicitly]. LHS for $n = k+1$ $= \dots = $ (use IH) $\dots = $ RHS for $n = k+1$. So $P(k+1)$ is true."
- Conclude. "Hence by the principle of mathematical induction, $P(n)$ is true for all $n \geq n_0$."
Diagnosing the hook: The student wrote "Assume $P(k)$ is true. Then $P(k+1)$ is true." The two missing pieces are:
- No base case — the dominoes are never pushed.
- No inductive step worked out — the leap from $P(k)$ to $P(k+1)$ is asserted, not demonstrated using the IH.
Five lines: State, Base, Assume, Show, Conclude · Always name $P(n)$ explicitly at the start · Base case = direct substitution; the IH is what you assume · The step must use the IH visibly; end with the conclusion line
Pause — copy the five-line template (State, Base, Assume, Show, Conclude) and the requirement to name $P(n)$ explicitly at the start into your book.
Quick check: Which of the following is the correct order of the steps in a standard induction proof?
We just saw the five-line induction template: State $P(n)$, verify base case, assume $P(k)$, show $P(k+1)$, conclude. That raises a question: what exactly is the inductive hypothesis — and what are students commonly wrong about? This card answers it → the IH is assumed for one arbitrary $k$, never re-proved, and $P(k+1)$ must be derived from it (never assumed).
A surprising number of induction proofs lose marks because the student treats the IH as something to be checked rather than something to be assumed. The IH is your only ammunition in the inductive step.
The IH is: a temporary assumption, made for one arbitrary value $k$, used as a fact inside the step. It is what the dominoes-knock-each-other-down line of reasoning relies on.
The IH is not: the conclusion (that comes from the principle), and not a check on $P(k)$ via fresh calculation. You do not re-verify $P(k)$; you take it as given.
The IH is assumed, never re-proved · The IH applies for one arbitrary $k \geq n_0$, not for all $n$ · The step uses the IH to derive $P(k+1)$ from $P(k)$ · Never write "Assume $P(k+1)$" — that has nothing to prove
Pause — copy the three IH rules: assumed not proved, applies to one arbitrary $k$, and the step derives $P(k+1)$ from $P(k)$ — never write "Assume $P(k+1)$" — into your book.
Did you get this? True or false: in a proof by induction, the inductive hypothesis $P(k)$ is a temporary assumption that you use to derive $P(k+1)$ — you do not need to re-verify $P(k)$ inside the step.
Worked examples · 3 in a row, reveal as you go
Prove by induction that $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ for all integers $n \geq 1$.
Prove by induction that $1^2 + 2^2 + 3^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$ for all integers $n \geq 1$.
A student submits the following proof. Identify every structural error, then rewrite the proof correctly.
Claim: $1 + 3 + 5 + \dots + (2n-1) = n^2$.
"Assume true for $n=k$. Then $1+3+\dots+(2k+1) = (k+1)^2$. So it's true."
Fill the gap: In the inductive step of $\sum_{i=1}^n i = \tfrac{n(n+1)}{2}$, after writing LHS for $n = k+1$ as (sum to $k$) + $(k+1)$, we substitute the IH and get $\dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+)}{2}$.
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: the sentence "Assume the statement holds for all $n$" is a correct way to state the inductive hypothesis.
Activities · practice with the ideas
Prove by induction that $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ for all $n \geq 1$. Use the full five-line template.
Prove by induction that $1^3 + 2^3 + \dots + n^3 = \left[\dfrac{n(n+1)}{2}\right]^2$ for all $n \geq 1$.
Identify all the structural errors in this proof, then rewrite it correctly: "We want $\sum_{i=1}^n (2i-1) = n^2$. For $n=k$, $\sum (2i-1) = k^2$. Adding $2k+1$ gives $(k+1)^2$. Done."
Prove by induction that $1 \cdot 2 + 2 \cdot 3 + \dots + n(n+1) = \dfrac{n(n+1)(n+2)}{3}$ for all $n \geq 1$.
Why does a proof by induction need both a base case AND an inductive step? Give a one-sentence reason for each using the dominoes analogy, then explain what fails if one is missing.
Odd one out: Three of these are correct components of a proof by induction. Which one is NOT?
Earlier you listed the three steps of induction and identified which step students most often fumble.
The three steps are the base case, the inductive hypothesis (assume $P(k)$), and the inductive step (show $P(k+1)$). The most fumbled element isn't a step at all — it's the conclusion line. Many students stop after the algebra of the step and forget to write "Hence by induction, $P(n)$ is true for all $n \geq n_0$", costing the structural mark even when the work is correct.
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. Prove by induction that $2 + 4 + 6 + \dots + 2n = n(n+1)$ for all $n \geq 1$. (3 marks)
Q2. Prove by induction that $\sum_{i=1}^{n} i(i+1) = \dfrac{n(n+1)(n+2)}{3}$ for all $n \geq 1$. (3 marks)
Q3. A student submits the following proof of $\sum_{i=1}^n i = \tfrac{n(n+1)}{2}$: "Assume $\sum_{i=1}^k i = \tfrac{k(k+1)}{2}$. Then $\sum_{i=1}^{k+1} i = \tfrac{(k+1)(k+2)}{2}$. Hence true." Identify every structural omission and rewrite the proof in correct form. (3 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. $P(n)$: $\sum i = \tfrac{n(n+1)}{2}$. Base $n=1$: LHS $=1$, RHS $=1$ ✓. Assume IH: $\sum_{i=1}^k i = \tfrac{k(k+1)}{2}$. Show: $\sum_{i=1}^{k+1} i = \tfrac{k(k+1)}{2} + (k+1) = \tfrac{(k+1)(k+2)}{2}$ ✓. Hence by induction true for all $n \geq 1$.
2. Base $n=1$: LHS $= 1$, RHS $= [\tfrac{1\cdot 2}{2}]^2 = 1$ ✓. Assume $\sum_{i=1}^k i^3 = [\tfrac{k(k+1)}{2}]^2$. Step: $\sum_{i=1}^{k+1} i^3 = [\tfrac{k(k+1)}{2}]^2 + (k+1)^3 = \tfrac{k^2(k+1)^2 + 4(k+1)^3}{4} = \tfrac{(k+1)^2(k^2 + 4k + 4)}{4} = \tfrac{(k+1)^2(k+2)^2}{4} = [\tfrac{(k+1)(k+2)}{2}]^2$ ✓.
3. Errors: no statement of $P(n)$; no base case; IH not labelled as IH; the step is asserted, not derived; no conclusion line. Correct rewrite follows the five-line template.
4. Base $n=1$: LHS $= 1\cdot 2 = 2$, RHS $= \tfrac{1\cdot 2\cdot 3}{3} = 2$ ✓. Assume IH. Step: $\sum_{i=1}^{k+1} i(i+1) = \tfrac{k(k+1)(k+2)}{3} + (k+1)(k+2) = \tfrac{(k+1)(k+2)[k + 3]}{3} = \tfrac{(k+1)(k+2)(k+3)}{3}$ ✓.
5. Base case = push first domino (without it, no dominoes ever fall). Step = each domino knocks the next (without it, even pushing the first only knocks one). Missing base: chain is never started. Missing step: the property may hold for $n=1$ but doesn't propagate.
Q1 (3 marks): State $P(n)$ [1]. Base $n=1$: LHS $=2$, RHS $= 1\cdot 2 = 2$ ✓ [1]. Assume IH; step: $\sum_{i=1}^{k+1} 2i = k(k+1) + 2(k+1) = (k+1)(k+2)$ ✓; conclude [1].
Q2 (3 marks): State $P(n)$ + base $n=1$ ✓ [1]. Assume IH; step: $\tfrac{k(k+1)(k+2)}{3} + (k+1)(k+2) = \tfrac{(k+1)(k+2)(k+3)}{3}$ [1]. Conclusion line [1].
Q3 (3 marks): Identify 4 omissions: no $P(n)$, no base, IH unlabelled, no conclusion [1]. Rewrite with full five-line template [1]. Step uses IH visibly + conclusion line [1].
Five timed questions on sum identities and proof structure. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering induction-structure questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.