Proof by mathematical induction is the only formal proof technique on the IB Mathematics Analysis & Approaches HL syllabus, and it is one of the highest-leverage topics in the entire course. Every question follows the same four-step skeleton — define the proposition, verify the base case, perform the inductive step, and state the conclusion — yet HL students consistently lose marks for the same handful of avoidable errors: writing "let $n = k$", omitting the conclusion sentence, missing one side of the base case, or fumbling the algebra in factorial and divisibility steps.
This cheatsheet condenses every question type, mark-scheme rubric, and exam-pattern observation from AHL 1.15 into one page you can revise from. If you want the printable PDF version, the full set of notes, the worked tutorials, and the marked-up solutions, scroll to the bottom for the download links and the gated full library.
§1 — The Universal 4-Step Template AHL 1.15
Every induction proof — regardless of type — follows exactly the same four-step skeleton. Master this skeleton first; the only thing that changes between question types is the algebra in Step 3.
Step 1 & 2 — Define and Base Case
Step 1 — State the proposition. Write: "Let $P(n)$ be the proposition that [full formula/statement] for all $n \geq 1$ (or $n \geq n_0$)."
Step 2 — Base case. Substitute $n = n_0$ (usually 1). Compute both LHS and RHS separately and show they are equal. Write: "Since LHS $=$ RHS, $P(1)$ is true." (R1)
Step 3 — Inductive Hypothesis & Inductive Step
Inductive hypothesis. Write: "Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$, i.e. [formula with $k$]." (M1)
Inductive step. Show $P(k+1)$ using the hypothesis. The method depends on question type (see §2–§8). Arrive at the exact form of $P(k+1)$. (M1 + A1 + A1 + A1)
Step 4 — Conclusion (Always Required)
Write in full: "Since $P(1)$ is true, and $P(k)$ true $\Rightarrow$ $P(k+1)$ true for all $k \in \mathbb{Z}^+$, by the principle of mathematical induction $P(n)$ is true for all $n \in \mathbb{Z}^+$." (R1)
IB Mark Scheme Map — Every Induction Question
| Mark | What it rewards | How to earn it | Common loss |
|---|---|---|---|
| R1 | Base case correct | Both sides computed, equal shown | Only one side shown |
| M1 | Inductive hypothesis | "Assume $P(k)$: [formula]" | Writing "let $n=k$" |
| M1 | Setting up $P(k+1)$ | Splitting $\sum_{k+1} = \sum_k + f(k+1)$ | Skipping the split |
| A1 | Applying IH | Substituting IH formula | Wrong substitution |
| A1 | Algebra step | Simplifying correctly | Arithmetic error |
| A1 | Reaching target | Arriving at exact $P(k+1)$ form | Stopping one step early |
| R1 | Conclusion sentence | Full sentence, references both steps | Omitting sentence |
§2 — Sum Formula Proofs AHL 1.15
The most common induction type. Prove $\displaystyle\sum_{r=1}^{n} f(r) = S(n)$.
The Split-and-Substitute Method
The inductive step always follows this pattern:
$$\sum_{r=1}^{k+1} f(r) \;=\; \underbrace{\sum_{r=1}^{k} f(r)}_{\text{apply IH} = S(k)} + \underbrace{f(k+1)}_{\text{next term}} \;=\; S(k) + f(k+1) \;\overset{?}{=}\; S(k+1)$$
The challenge is the algebra: show $S(k) + f(k+1) = S(k+1)$.
Formula reference (must know — not in formula booklet)
Critical algebra tricks
Factorial trick: $\dfrac{1}{(k+1)!} = \dfrac{k+2}{(k+2)!}$ — lets you combine fractions with different factorial denominators.
Polynomial-sum factor trick: after adding $f(k+1)$ to $S(k)$, factor out $(k+1)$ from both terms — the target $S(k+1)$ almost always has $(k+1)$ as a factor:
$$\frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2}+1\right) = \frac{(k+1)(k+2)}{2}$$
§3 — Divisibility Proofs AHL 1.15
Prove that $d \mid f(n)$ for all $n \in \mathbb{Z}^+$.
The three divisibility strategies
Strategy 1 — The Split: Write $f(k+1) = A \cdot f(k) + (\text{multiple of } d)$. Apply IH: $f(k) = dm$, so $A \cdot f(k) = Adm$, and the whole thing $= d(\ldots)$.
Strategy 2 — Add and subtract: $a^{k+1} - b^{k+1} = a \cdot a^k - b \cdot b^k = \underbrace{(a-b)}_{\text{divisor}} \cdot a^k + b\underbrace{(a^k - b^k)}_{\text{IH}}$.
Strategy 3 — Factor out the base (most common): e.g. $25 \cdot 5^{2k} = 17 \cdot 5^{2k} + 8 \cdot 5^{2k}$ — creates the divisor 17 explicitly.
Common IB divisibility claims
- $9^n - 1 \equiv 0 \pmod{8}$
- $5^{2n} - 2^{3n} \equiv 0 \pmod{17}$
- $3^{2n}+7 \equiv 0 \pmod{8}$
- $11^n - 6 \equiv 0 \pmod{5}$
- $2^{n+2}+3^{2n+1} \equiv 0 \pmod{7}$
- $n^3 - n \equiv 0 \pmod{6}$
- $7^n - 4^n - 3^n \equiv 0 \pmod{12}$
The "17 split" from IB 2023 Nov
$5^{2(k+1)} - 2^{3(k+1)} = 25 \cdot 5^{2k} - 8 \cdot 2^{3k} = \mathbf{17} \cdot 5^{2k} + 8\underbrace{(5^{2k} - 2^{3k})}_{\text{IH} = 17s} = 17(5^{2k} + 8s)$ ✓
§4 — Inequality Proofs AHL 1.15
Prove $f(n) > g(n)$ (or $\geq$) for all $n \geq n_0$.
The chain-of-inequalities method
Build a chain: $f(k+1) \;\geq\; [\text{use IH}] \;\geq\; g(k+1)$.
Typical structure:
- Apply IH to replace $f(k)$ with something involving $g(k)$.
- Use a separate algebraic fact to connect to $g(k+1)$.
- Justify each $\geq$ step explicitly.
Example (IB 2025 May): Prove $n > \log_2 n$. Step: $k+1 > 1 + \log_2 k$ (by IH) $\geq \log_2(k+1)$ (by helper result).
§5 — Trigonometric Identity Proofs AHL 1.15
Prove identities of the form $\displaystyle\sum_{r=1}^{n} \mathrm{trig}(r\theta) = \dfrac{\ldots}{\sin\theta}$.
Structure of trig induction
The inductive step: split the sum, apply IH to the $k$-sum, then use a trig identity to collapse the $(k+1)$-th term into the target.
Key identity used in almost every trig induction:
$$2\sin\theta\cos\phi = \sin(\phi+\theta) - \sin(\phi-\theta)$$
or equivalently: $\sin A + \sin B = 2\sin\tfrac{A+B}{2}\cos\tfrac{A-B}{2}$.
De Moivre's theorem proof (always examined)
Use compound-angle formulas in the inductive step:
$$(\cos\theta + i\sin\theta)^{k+1} = \underbrace{(\cos k\theta + i\sin k\theta)}_{\text{IH}}(\cos\theta + i\sin\theta)$$
Expand, apply $\cos(A+B)$ and $\sin(A+B)$, arrive at $\cos(k+1)\theta + i\sin(k+1)\theta$.
§6 — Calculus: $n$-th Derivative Proofs AHL 1.15
Prove $f^{(n)}(x) = [\text{formula}]$ for $n \in \mathbb{Z}^+$.
Derivative-induction method
Base case: differentiate once (use product rule), show it matches the $n=1$ formula. Note: You need two A1 marks in the base case for derivative proofs — one for the derivative itself, one for matching the formula at $n=1$.
Inductive step: differentiate the inductive hypothesis:
$$f^{(k+1)}(x) = \frac{d}{dx}\!\left[f^{(k)}(x)\right] = \frac{d}{dx}\!\left[\text{IH formula}\right]$$
Use the product rule: $\dfrac{d}{dx}[g(x)e^x] = (g'(x) + g(x))e^x$. Simplify to match $f^{(k+1)}$ formula.
§7 — Recurrence Relation Proofs AHL 1.15
Given $u_1$ and $u_{n+1} = f(u_n)$, prove a closed-form formula for $u_n$.
Recurrence-proof method
If asked to conjecture first: compute $u_2, u_3, u_4$ and spot the pattern.
Inductive step: $u_{k+1} = f(u_k) \xrightarrow{\text{sub IH}} f(\text{formula at }k) \xrightarrow{\text{algebra}} \text{formula at }k+1$. The recurrence relation is your starting point — use it immediately, then substitute the IH.
§8 — Combinatorics and Products AHL 1.15
Key combinatorial identity
Pascal's Rule: $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$.
Used in the inductive step of combinatoric sum proofs: $\binom{k+1}{2} + \binom{k+1}{1} = \binom{k+2}{2}$. This is the single key step for the IB 2024 May Q7 type question.
For product proofs like $\displaystyle\prod_{i=1}^{n}\!\left(1 - \dfrac{1}{i+1}\right) = \dfrac{1}{n+1}$, the inductive step is: $\displaystyle\prod_{i=1}^{k+1}(\ldots) = \dfrac{1}{k+1} \cdot \!\left(1 - \dfrac{1}{k+2}\right) = \dfrac{1}{k+1} \cdot \dfrac{k+1}{k+2} = \dfrac{1}{k+2}$.
§9 — Attack Plan by Question Type AHL 1.15
| Type | Recognition signal | First move in inductive step |
|---|---|---|
| Sum | $\sum_{r=1}^{n} f(r) = S(n)$ | Write $f(k+1)$ and $S(k+1)$ on the side |
| Divisibility | "divisible by $d$" | Write $f(k) = dm$, expand $f(k+1)$, create $f(k)$ inside |
| Inequality | "$>$" or "$\geq$" or "$<$" | Set up chain; use IH to bound one side |
| Trig sum | Sum of $\cos/\sin$ = fraction | Split sum, use $2\sin\theta\cos\phi$ identity |
| Derivative | "$n$-th derivative of …" | Base case: differentiate once; step: differentiate IH |
| Recurrence | $u_{n+1} = f(u_n)$ given | Apply recurrence first, then substitute IH |
| Combinatorics | $\sum\binom{r}{j}$ or products | Apply Pascal's rule or cancel factorials |
§10 — IB Exam Patterns (2020–2025) AHL 1.15
| Year | Question type | Marks | Where |
|---|---|---|---|
| 2025 May | Inequality with helper ($n > \log_2 n$) | 7 | P1 Q8 |
| 2024 May TZ1 | Combinatorics sum ($\sum \binom{r}{1}$) | 7 | P1 Q7 |
| 2024 May TZ2 | Calculus ($n$-th derivative of $f(x)$) | 20 | P1 Q12 |
| 2023 May TZ2 | Factorial sum | 7 | P1 Q7 |
| 2023 Nov TZ1 | Divisibility ($5^{2n} - 2^{3n}$, mod 17) | 7 | P1 Q6 |
| 2022 Nov | Complex numbers / induction | 18 | P1 Q12 |
| 2021 Nov | $n$-th derivative of $x^2 e^x$ | 14 | P1 Q11 |
| 2021 May | Inequality / alternating sum | various | P1 |
Top 8 mark-losing mistakes
- "Let $n = k$" instead of writing the full IH formula — loses M1 every time.
- Missing the conclusion sentence — loses R1 every time.
- Base case: only showing one side — loses R1.
- Wrong next term in sum proofs (especially factorial denominators).
- Circular reasoning: using $P(k+1)$ to prove $P(k+1)$.
- Forgetting $m \in \mathbb{Z}$ in divisibility proofs — the conclusion requires this.
- Threshold inequalities: using base case $n=1$ when the claim is for $n \geq 5$.
- Trig proofs: not writing which identity was applied (cost you A1).
Worked Example — IB-Style Divisibility Induction
Question (HL Paper 1 style — 7 marks)
Use mathematical induction to prove that $f(n) = 5^{2n} - 2^{3n}$ is divisible by 17 for all $n \in \mathbb{Z}^+$.
Solution
- Base case ($n = 1$): $f(1) = 5^2 - 2^3 = 25 - 8 = 17 = 17 \times 1$. So $P(1)$ is true. (R1)
- Inductive hypothesis: Assume $P(k)$ is true, i.e. $5^{2k} - 2^{3k} = 17m$ for some $m \in \mathbb{Z}$. (M1)
- Inductive step — set up $f(k+1)$: $f(k+1) = 5^{2(k+1)} - 2^{3(k+1)} = 25 \cdot 5^{2k} - 8 \cdot 2^{3k}$. (M1)
- Create $f(k)$ inside using the "17 split": $25 \cdot 5^{2k} = 17 \cdot 5^{2k} + 8 \cdot 5^{2k}$, so $f(k+1) = 17 \cdot 5^{2k} + 8 \cdot 5^{2k} - 8 \cdot 2^{3k} = 17 \cdot 5^{2k} + 8(5^{2k} - 2^{3k})$. (A1)
- Apply IH and factor out 17: $= 17 \cdot 5^{2k} + 8 \cdot 17m = 17(5^{2k} + 8m)$, where $5^{2k} + 8m \in \mathbb{Z}$. So $f(k+1)$ is divisible by 17. (A1)(A1)
- Conclusion: Since $P(1)$ is true, and $P(k)$ true $\Rightarrow$ $P(k+1)$ true for all $k \in \mathbb{Z}^+$, by the principle of mathematical induction $5^{2n} - 2^{3n}$ is divisible by 17 for all $n \in \mathbb{Z}^+$. (R1)
Examiner's note: the "17 split" — turning $25 = 17 + 8$ — is the only non-routine step. Writing the IH as the algebraic form $5^{2k} - 2^{3k} = 17m$ (rather than "is divisible by 17") is what makes the final factoring possible. This is a 2023 Nov TZ1 paper-1-style question.
Common Student Questions
Why does writing "let $n = k$" lose the M1 mark in induction?
Do I really need to write a conclusion sentence every time?
How do I handle factorial sums like $\displaystyle\sum \dfrac{r}{(r+1)!}$?
What is the right base case for inequalities like $n! \geq 2^n$?
How should I write the inductive hypothesis for divisibility proofs?
Get the printable PDF version
Same cheatsheet, formatted for A4 print — keep it next to your study desk. Free for signed-in users.