Figure 1.1: The Domino Principle of Mathematical Induction

n = 1 1. Base Step P(1) n = 2 n = k 2. Assume P(k) true P(k) ⇒ P(k+1) n = k+1 3. Deduce P(k+1)

If the first domino falls ($P(1)$ is true) and any falling domino knocks over its successor ($P(k) \implies P(k+1)$), all infinitely many dominos must fall ($P(n)$ is true for all $n \in \mathbb{Z}^+$).

AHL 1.14

Axiomatic Foundation & The Mandatory 4-Step IB Protocol

  • The Principle of Mathematical Induction: Let $P(n)$ be a propositional predicate defined for integers $n \ge n_0$. If:
    1. Base Step: $P(n_0)$ is true.
    2. Inductive Step: For any arbitrary integer $k \ge n_0$, assuming $P(k)$ is true implies that $P(k+1)$ is true ($P(k) \implies P(k+1)$).
    Then $P(n)$ is true for all integers $n \ge n_0$. This axiom is logically equivalent to the Well-Ordering Principle of the positive integers.
  • The Official 4-Step Markscheme Structure:
    • Step 1 — Base Case ($n = n_0$): You must calculate both $\text{LHS}$ and $\text{RHS}$ separately and show equality: $\text{LHS} = \text{RHS}$, hence $P(n_0)$ is true. Never just write $1=1$! $\mathbf{[M1]}$
    • Step 2 — Inductive Hypothesis: Explicitly state: "Assume $P(n)$ is true for $n = k$, where $k \in \mathbb{Z}^+, k \ge n_0$." Write out the mathematical expression for $P(k)$. $\mathbf{[M1]}$
    • Step 3 — Inductive Step ($n = k+1$): Clearly state the target: "Prove $P(k+1)$ is true." Start strictly with $\text{LHS}_{k+1}$, substitute the inductive hypothesis $P(k)$, and perform algebraic manipulation to independently reach $\text{RHS}_{k+1}$. Never equate $\text{LHS}_{k+1} = \text{RHS}_{k+1}$ at the start (circular reasoning forfeits marks!). $\mathbf{[M1][A1]}$
    • Step 4 — The Mandatory Final Conclusion ($R1$ Mark): The final mark in every IB markscheme is an independent reasoning mark ($R1$) awarded ONLY if the conclusion contains all 4 legal phrases:
      "Since the statement is true for $n=1$, and its truth for $n=k$ implies its truth for $n=k+1$, by the principle of mathematical induction the proposition is true for all $n \in \mathbb{Z}^+$."
AHL 1.14

Series Summations & Factorial Sequences

  • Decomposition of Summations: For any series $S_n = \sum_{r=1}^n u_r$, the $(k+1)$-th sum is partitioned as: $$S_{k+1} = \sum_{r=1}^{k+1} u_r = \left(\sum_{r=1}^k u_r\right) + u_{k+1} = S_k + u_{k+1}$$ Substitute the hypothesis formula for $S_k$, then factorize algebraically.
  • The Factorization Golden Rule: NEVER expand polynomials into raw expanded form like $2k^3 + 9k^2 + 13k + 6$. Always look to factor out common linear binomials such as $(k+1)$ or $(k+2)$ immediately.
  • Factorial Series Identities: When proving series involving factorials (e.g., $\sum r \cdot r!$), use the fundamental factorial recurrence $(k+1)! = (k+1) \cdot k!$ and group common factorial brackets: $$(k+1)! + (k+1)(k+1)! = (k+1)![1 + (k+1)] = (k+1)!(k+2) = (k+2)!$$
AHL 1.14

Integer Divisibility Proofs by Induction

  • Formal Algebraic Definition: To state that $f(n)$ is divisible by an integer $M$, define: $$f(k) = M \cdot A \quad \text{for some integer } A \in \mathbb{Z}$$ Isolate the dominant exponential term: $c^k = M \cdot A - g(k)$.
  • The Two Standard Inductive Step Pathways:
    • Method A (Direct Substitution): Express $f(k+1)$ and replace the highest power $c^{k+1} = c \cdot c^k = c(MA - g(k))$. Expand and factor out $M$.
    • Method B (Difference Method): Evaluate $f(k+1) - f(k)$ or $f(k+1) - c \cdot f(k)$. If the difference is demonstrably a multiple of $M$, then: $$f(k+1) = c \cdot f(k) + M \cdot B = c(M \cdot A) + M \cdot B = M(cA + B)$$ Since $cA + B \in \mathbb{Z}$, $f(k+1)$ is divisible by $M$.
AHL 1.14

Matrix Exponentiation, Derivatives & Inequalities

  • Matrix Powers ($M^n$): In Step 3, write $M^{k+1} = M^k \cdot M$ (or $M \cdot M^k$). Substitute the inductive hypothesis matrix for $M^k$, execute standard row-by-column multiplication, and simplify elements to match the target form with $(k+1)$.
  • $n$-th Derivatives: In Step 3, use the definition of higher derivatives: $$\frac{d^{k+1}}{dx^{k+1}} f(x) = \frac{d}{dx}\left[ \frac{d^k}{dx^k} f(x) \right]$$ Substitute the hypothesis expression for the $k$-th derivative and differentiate once more using the Product, Quotient, or Chain Rule.
  • Inequality Proofs & Transitivity: To prove $\text{LHS}_{k+1} > \text{RHS}_{k+1}$: $$\text{LHS}_{k+1} = c \cdot \text{LHS}_k > c \cdot \text{RHS}_k \quad (\text{by hypothesis, where } c > 0)$$ Then prove that $c \cdot \text{RHS}_k \ge \text{RHS}_{k+1}$ by examining the difference $c \cdot \text{RHS}_k - \text{RHS}_{k+1}$ and demonstrating it is non-negative for $k \ge n_0$.

Authentic IB HL Worked Exemplars (Full Markscheme Rubrics)

Exemplar 1 · Paper 1 (6 Marks)

Telescoping Fraction Summation Proof

Prove by mathematical induction that for all $n \in \mathbb{Z}^+$: $$\sum_{r=1}^n \frac{1}{(2r-1)(2r+1)} = \frac{n}{2n+1}$$

Full Markscheme & Method:

  1. Step 1: Base Case ($n = 1$) $$\text{LHS} = \frac{1}{(2(1)-1)(2(1)+1)} = \frac{1}{(1)(3)} = \frac{1}{3} \quad \mathbf{[M1]}$$ $$\text{RHS} = \frac{1}{2(1)+1} = \frac{1}{3}$$ Since $\text{LHS} = \text{RHS}$, the proposition is true for $n = 1$. $\mathbf{[A1]}$
  2. Step 2: Inductive Hypothesis Assume the proposition is true for $n = k$, where $k \in \mathbb{Z}^+$: $$\sum_{r=1}^k \frac{1}{(2r-1)(2r+1)} = \frac{k}{2k+1} \quad \mathbf{[M1]}$$
  3. Step 3: Inductive Step ($n = k+1$) Target to prove: $\sum_{r=1}^{k+1} \frac{1}{(2r-1)(2r+1)} = \frac{k+1}{2(k+1)+1} = \frac{k+1}{2k+3}$. $$\text{LHS}_{k+1} = \sum_{r=1}^k \frac{1}{(2r-1)(2r+1)} + \frac{1}{(2(k+1)-1)(2(k+1)+1)} \quad \mathbf{[M1]}$$ Substitute the inductive hypothesis: $$\text{LHS}_{k+1} = \frac{k}{2k+1} + \frac{1}{(2k+1)(2k+3)}$$ Combine over the common denominator $(2k+1)(2k+3)$: $$= \frac{k(2k+3) + 1}{(2k+1)(2k+3)} = \frac{2k^2 + 3k + 1}{(2k+1)(2k+3)} \quad \mathbf{[M1]}$$ Factor the numerator quadratic $2k^2 + 3k + 1 = (2k+1)(k+1)$: $$= \frac{(2k+1)(k+1)}{(2k+1)(2k+3)} = \frac{k+1}{2k+3} = \text{RHS}_{k+1} \quad \mathbf{[A1]}$$
  4. Step 4: Formal IB Conclusion Since the proposition is true for $n = 1$, and its truth for $n = k$ implies its truth for $n = k+1$, by the principle of mathematical induction the proposition is true for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$
Examiner Advice: Notice how $(2k+1)$ cancelled out neatly! If your numerator does not contain the denominator factor you need to cancel, stop and re-check your algebraic addition before expanding further.
Exemplar 2 · Paper 1 (7 Marks)

Divisibility by 64 Proof

Prove by mathematical induction that $7^{2n} + 16n - 1$ is divisible by $64$ for all $n \in \mathbb{Z}^+$.

Full Markscheme & Method:

  1. Base Step ($n = 1$) For $n = 1$: $$7^{2(1)} + 16(1) - 1 = 49 + 16 - 1 = 64 = 64(1) \quad \mathbf{[M1]}$$ Since $64$ is divisible by $64$, the statement is true for $n = 1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis Assume the statement is true for $n = k \in \mathbb{Z}^+$: $$7^{2k} + 16k - 1 = 64A \quad \text{for some integer } A \in \mathbb{Z} \quad \mathbf{[M1]}$$ Hence: $7^{2k} = 64A - 16k + 1$.
  3. Inductive Step ($n = k+1$) Target expression for $n = k+1$: $$E_{k+1} = 7^{2(k+1)} + 16(k+1) - 1 = 7^{2k+2} + 16k + 16 - 1 = 7^2 \cdot 7^{2k} + 16k + 15 \quad \mathbf{[M1]}$$ $$= 49 \cdot 7^{2k} + 16k + 15$$ Substitute $7^{2k} = 64A - 16k + 1$: $$= 49(64A - 16k + 1) + 16k + 15 \quad \mathbf{[M1]}$$ $$= 49(64A) - 49(16k) + 49 + 16k + 15$$ $$= 49(64A) - 784k + 16k + 64$$ $$= 49(64A) - 768k + 64$$ Notice that $768 = 64 \times 12$: $$= 64(49A - 12k + 1) \quad \mathbf{[A1]}$$ Since $A, k \in \mathbb{Z}$, the expression $49A - 12k + 1$ is an integer. Thus $E_{k+1}$ is divisible by $64$.
  4. Formal Conclusion Since the statement is true for $n = 1$, and truth for $n = k$ implies truth for $n = k+1$, by the principle of mathematical induction $7^{2n} + 16n - 1$ is divisible by $64$ for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$
Exemplar 3 · Paper 1 (6 Marks)

Matrix Exponentiation Induction Proof

Let $M = \begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix}$. Prove by mathematical induction that for all $n \in \mathbb{Z}^+$: $$M^n = \begin{pmatrix} 3^n & n 3^{n-1} \\ 0 & 3^n \end{pmatrix}$$

Full Markscheme & Method:

  1. Base Step ($n = 1$) $$\text{LHS} = M^1 = \begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix} \quad \mathbf{[M1]}$$ $$\text{RHS} = \begin{pmatrix} 3^1 & (1)3^{1-1} \\ 0 & 3^1 \end{pmatrix} = \begin{pmatrix} 3 & 1(3^0) \\ 0 & 3 \end{pmatrix} = \begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix}$$ Since $\text{LHS} = \text{RHS}$, the formula holds for $n = 1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis Assume the formula holds for $n = k \in \mathbb{Z}^+$: $$M^k = \begin{pmatrix} 3^k & k 3^{k-1} \\ 0 & 3^k \end{pmatrix} \quad \mathbf{[M1]}$$
  3. Inductive Step ($n = k+1$) Target to prove: $M^{k+1} = \begin{pmatrix} 3^{k+1} & (k+1)3^k \\ 0 & 3^{k+1} \end{pmatrix}$. $$\text{LHS}_{k+1} = M^k \cdot M = \begin{pmatrix} 3^k & k 3^{k-1} \\ 0 & 3^k \end{pmatrix} \begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix} \quad \mathbf{[M1]}$$ Perform matrix multiplication: $$\text{Row 1, Col 1}: 3^k(3) + (k 3^{k-1})(0) = 3^{k+1}$$ $$\text{Row 1, Col 2}: 3^k(1) + (k 3^{k-1})(3) = 3^k + k 3^k = (k+1)3^k$$ $$\text{Row 2, Col 1}: 0(3) + 3^k(0) = 0$$ $$\text{Row 2, Col 2}: 0(1) + 3^k(3) = 3^{k+1} \quad \mathbf{[A1]}$$ Combining the elements: $$M^{k+1} = \begin{pmatrix} 3^{k+1} & (k+1)3^k \\ 0 & 3^{k+1} \end{pmatrix} = \text{RHS}_{k+1}$$
  4. Formal Conclusion Since the proposition is true for $n = 1$, and assuming truth for $n = k$ implies truth for $n = k+1$, by mathematical induction $M^n = \begin{pmatrix} 3^n & n 3^{n-1} \\ 0 & 3^n \end{pmatrix}$ for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$
Exemplar 4 · Paper 1 (7 Marks)

$n$-th Derivative Calculus Induction

Let $f(x) = x^2 e^x$. Prove by mathematical induction that for all $n \in \mathbb{Z}^+$: $$\frac{d^n}{dx^n}(x^2 e^x) = (x^2 + 2nx + n(n-1))e^x$$

Full Markscheme & Method:

  1. Base Step ($n = 1$) Direct derivative via product rule: $$\frac{d}{dx}(x^2 e^x) = 2x e^x + x^2 e^x = (x^2 + 2x)e^x \quad \mathbf{[M1]}$$ Evaluating formula for $n=1$: $$(x^2 + 2(1)x + 1(1-1))e^x = (x^2 + 2x + 0)e^x = (x^2 + 2x)e^x$$ Since both match, the statement is true for $n=1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis Assume true for $n = k \in \mathbb{Z}^+$: $$\frac{d^k}{dx^k}(x^2 e^x) = (x^2 + 2kx + k(k-1))e^x \quad \mathbf{[M1]}$$
  3. Inductive Step ($n = k+1$) Target to reach: $(x^2 + 2(k+1)x + (k+1)k)e^x$. $$\frac{d^{k+1}}{dx^{k+1}}(x^2 e^x) = \frac{d}{dx}\left[\frac{d^k}{dx^k}(x^2 e^x)\right] = \frac{d}{dx}\left[ (x^2 + 2kx + k(k-1))e^x \right] \quad \mathbf{[M1]}$$ Differentiating using product rule: $$= \frac{d}{dx}(x^2 + 2kx + k^2 - k) \cdot e^x + (x^2 + 2kx + k^2 - k) \cdot \frac{d}{dx}(e^x)$$ $$= (2x + 2k)e^x + (x^2 + 2kx + k^2 - k)e^x \quad \mathbf{[A1]}$$ Factor out $e^x$ and collect powers of $x$: $$= [x^2 + (2kx + 2x) + (k^2 - k + 2k)] e^x$$ $$= [x^2 + 2(k+1)x + (k^2 + k)] e^x$$ Notice that $k^2 + k = k(k+1) = (k+1)((k+1)-1)$: $$= [x^2 + 2(k+1)x + (k+1)k] e^x = \text{RHS}_{k+1} \quad \mathbf{[A1]}$$
  4. Formal Conclusion Since true for $n=1$, and truth for $n=k \implies$ truth for $n=k+1$, by mathematical induction the formula holds for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$
Exemplar 5 · Paper 2 (8 Marks)

Inequality Induction with Shifted Base ($n \ge 4$)

Prove by mathematical induction that $3^n > n^3$ for all integers $n \ge 4$.

Full Markscheme & Method:

  1. Base Step ($n = 4$) Notice the domain starts at $n=4$: $$\text{LHS} = 3^4 = 81 \quad \mathbf{[M1]}$$ $$\text{RHS} = 4^3 = 64$$ Since $81 > 64$, the proposition is true for $n = 4$. $\mathbf{[A1]}$
  2. Inductive Hypothesis Assume the proposition holds for an integer $k \ge 4$: $$3^k > k^3 \quad \mathbf{[M1]}$$
  3. Inductive Step ($n = k+1$) We must prove that $3^{k+1} > (k+1)^3$. $$\text{LHS}_{k+1} = 3^{k+1} = 3 \cdot 3^k > 3k^3 \quad (\text{since } 3^k > k^3 \text{ by hypothesis}) \quad \mathbf{[M1]}$$ To complete the proof by transitivity, we need to show that $3k^3 \ge (k+1)^3$ for all $k \ge 4$. Consider the difference $D(k) = 3k^3 - (k+1)^3$: $$D(k) = 3k^3 - (k^3 + 3k^2 + 3k + 1) = 2k^3 - 3k^2 - 3k - 1 \quad \mathbf{[M1]}$$ Factor out $k^2$ from the leading terms for $k \ge 4$: $$D(k) = k^2(2k - 3) - 3k - 1$$ For $k \ge 4$: $2k - 3 \ge 2(4) - 3 = 5$, and $k^2 \ge 16$: $$D(k) \ge 16(5) - 3(k) - 1 = 79 - 3k$$ Since $k \ge 4$, $3k < 79$ for all reasonable finite tests (or more cleanly: $2k^3 - 3k^2 - 3k - 1 = k^2(k-3) + k(k^2-3) - 1 > 0$ for $k \ge 4$). Specifically at $k=4$: $2(64) - 3(16) - 3(4) - 1 = 128 - 48 - 12 - 1 = 67 > 0$, and for $k > 4$, $D'(k) = 6k^2 - 6k - 3 > 0$. Therefore: $3k^3 > (k+1)^3 \quad \mathbf{[A1]}$. Hence: $$3^{k+1} > 3k^3 > (k+1)^3 \implies 3^{k+1} > (k+1)^3 \quad \mathbf{[A1]}$$
  4. Formal Conclusion Since the proposition is true for $n = 4$, and its truth for $n = k$ implies its truth for $n = k+1$, by mathematical induction $3^n > n^3$ for all integers $n \ge 4$. $\mathbf{[R1]}$
Tier 1: Core Summations & Base Fluency (Questions 1–4)
Exercise 1 Paper 1 · 5 Marks

Prove by mathematical induction that for all $n \in \mathbb{Z}^+$: $$1 + 3 + 5 + \dots + (2n - 1) = n^2$$

View Complete Solution & Markscheme
  1. Base Step ($n=1$): $$\text{LHS} = 2(1)-1 = 1, \quad \text{RHS} = 1^2 = 1 \quad \mathbf{[M1]}$$ Since $\text{LHS} = \text{RHS}$, the proposition is true for $n=1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis: Assume the proposition is true for $n=k \in \mathbb{Z}^+$: $$1 + 3 + 5 + \dots + (2k-1) = k^2 \quad \mathbf{[M1]}$$
  3. Inductive Step ($n=k+1$): $$\text{LHS}_{k+1} = [1 + 3 + \dots + (2k-1)] + (2(k+1)-1) = k^2 + 2k + 1 \quad \mathbf{[M1]}$$ $$= (k+1)^2 = \text{RHS}_{k+1} \quad \mathbf{[A1]}$$
  4. Conclusion: Since the statement is true for $n=1$, and its truth for $n=k$ implies its truth for $n=k+1$, by mathematical induction the statement holds for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$

Final Conclusion: Statement verified for all $n \in \mathbb{Z}^+$.

Exercise 2 Paper 1 · 5 Marks

Prove by mathematical induction that for all $n \in \mathbb{Z}^+$: $$\sum_{r=1}^n 2^{r-1} = 1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1$$

View Complete Solution & Markscheme
  1. Base Step ($n=1$): $$\text{LHS} = 2^{1-1} = 2^0 = 1, \quad \text{RHS} = 2^1 - 1 = 1 \quad \mathbf{[M1]}$$ $\text{LHS} = \text{RHS}$, hence true for $n=1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis: Assume $\sum_{r=1}^k 2^{r-1} = 2^k - 1$ for $k \in \mathbb{Z}^+$. $\mathbf{[M1]}$
  3. Inductive Step ($n=k+1$): $$\sum_{r=1}^{k+1} 2^{r-1} = \left(\sum_{r=1}^k 2^{r-1}\right) + 2^{(k+1)-1} = (2^k - 1) + 2^k \quad \mathbf{[M1]}$$ $$= 2(2^k) - 1 = 2^{k+1} - 1 = \text{RHS}_{k+1} \quad \mathbf{[A1]}$$
  4. Conclusion: Since $P(1)$ is true and $P(k) \implies P(k+1)$, by mathematical induction the proposition holds for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$

Final Conclusion: Verified for all $n \in \mathbb{Z}^+$.

Exercise 3 Paper 1 · 6 Marks

Prove by mathematical induction that for all $n \in \mathbb{Z}^+$: $$\sum_{r=1}^n \frac{1}{r(r+1)} = \frac{n}{n+1}$$

View Complete Solution & Markscheme
  1. Base Step ($n=1$): $$\text{LHS} = \frac{1}{1(1+1)} = \frac{1}{2}, \quad \text{RHS} = \frac{1}{1+1} = \frac{1}{2} \quad \mathbf{[M1]}$$ True for $n=1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis: Assume $\sum_{r=1}^k \frac{1}{r(r+1)} = \frac{k}{k+1}$ for $k \in \mathbb{Z}^+$. $\mathbf{[M1]}$
  3. Inductive Step ($n=k+1$): $$\text{LHS}_{k+1} = \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} = \frac{k(k+2) + 1}{(k+1)(k+2)} \quad \mathbf{[M1]}$$ $$= \frac{k^2+2k+1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2} = \text{RHS}_{k+1} \quad \mathbf{[A1]}$$
  4. Conclusion: Since true for $n=1$ and truth for $n=k \implies$ truth for $n=k+1$, by mathematical induction the identity holds for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$

Final Conclusion: Verified for all $n \in \mathbb{Z}^+$.

Exercise 4 Paper 1 · 6 Marks

Prove by mathematical induction that for all $n \in \mathbb{Z}^+$: $$\sum_{r=1}^n r^2 = \frac{n(n+1)(2n+1)}{6}$$

View Complete Solution & Markscheme
  1. Base Step ($n=1$): $$\text{LHS} = 1^2 = 1, \quad \text{RHS} = \frac{1(1+1)(2(1)+1)}{6} = \frac{1(2)(3)}{6} = 1 \quad \mathbf{[M1]}$$ $\text{LHS} = \text{RHS}$, holds for $n=1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis: Assume $\sum_{r=1}^k r^2 = \frac{k(k+1)(2k+1)}{6}$ for $k \in \mathbb{Z}^+$. $\mathbf{[M1]}$
  3. Inductive Step ($n=k+1$): $$\text{LHS}_{k+1} = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\left[\frac{k(2k+1) + 6(k+1)}{6}\right] \quad \mathbf{[M1]}$$ $$= (k+1)\left[\frac{2k^2 + 7k + 6}{6}\right] = \frac{(k+1)(k+2)(2k+3)}{6} = \text{RHS}_{k+1} \quad \mathbf{[A1]}$$
  4. Conclusion: Since true for $n=1$ and $P(k) \implies P(k+1)$, by mathematical induction the formula holds for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$

Final Conclusion: Verified for all $n \in \mathbb{Z}^+$.

Tier 2: Divisibility & Matrix Powers (Questions 5–8)
Exercise 5 Paper 1 · 6 Marks

Prove by mathematical induction that $n^3 + 2n$ is divisible by $3$ for all $n \in \mathbb{Z}^+$.

View Complete Solution & Markscheme
  1. Base Case ($n=1$): $$1^3 + 2(1) = 3 = 3(1) \quad \mathbf{[M1]}$$ Divisible by $3$, hence true for $n=1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis: Assume $k^3 + 2k = 3M$ for some integer $M \in \mathbb{Z}$. $\mathbf{[M1]}$
  3. Inductive Step ($n=k+1$): $$(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2 = (k^3 + 2k) + 3k^2 + 3k + 3 \quad \mathbf{[M1]}$$ Substitute $k^3 + 2k = 3M$: $$= 3M + 3(k^2 + k + 1) = 3(M + k^2 + k + 1) \quad \mathbf{[A1]}$$ Since $M, k \in \mathbb{Z}$, $M + k^2 + k + 1 \in \mathbb{Z}$. Hence $(k+1)^3 + 2(k+1)$ is divisible by $3$.
  4. Conclusion: Since true for $n=1$ and $P(k) \implies P(k+1)$, by induction $n^3+2n$ is divisible by $3$ for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$

Final Conclusion: Divisible by $3$ for all $n \in \mathbb{Z}^+$.

Exercise 6 Paper 1 · 6 Marks

Prove by mathematical induction that $8^n - 1$ is divisible by $7$ for all $n \in \mathbb{Z}^+$.

View Complete Solution & Markscheme
  1. Base Case ($n=1$): $$8^1 - 1 = 7 = 7(1) \quad \mathbf{[M1]}$$ Divisible by $7$. True for $n=1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis: Assume $8^k - 1 = 7A$ for some $A \in \mathbb{Z}$, so $8^k = 7A + 1$. $\mathbf{[M1]}$
  3. Inductive Step ($n=k+1$): $$8^{k+1} - 1 = 8(8^k) - 1 = 8(7A + 1) - 1 = 56A + 8 - 1 = 56A + 7 \quad \mathbf{[M1]}$$ $$= 7(8A + 1) \quad \mathbf{[A1]}$$ Since $8A + 1 \in \mathbb{Z}$, $8^{k+1} - 1$ is divisible by $7$.
  4. Conclusion: Since true for $n=1$ and truth for $n=k \implies$ truth for $n=k+1$, by mathematical induction $8^n-1$ is divisible by $7$ for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$

Final Conclusion: Divisible by $7$ for all $n \in \mathbb{Z}^+$.

Exercise 7 Paper 1 · 6 Marks

Let $A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$. Prove by mathematical induction that for all $n \in \mathbb{Z}^+$: $$A^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$$

View Complete Solution & Markscheme
  1. Base Step ($n=1$): $$\text{LHS} = A^1 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad \text{RHS} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \quad \mathbf{[M1]}$$ True for $n=1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis: Assume $A^k = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}$ for $k \in \mathbb{Z}^+$. $\mathbf{[M1]}$
  3. Inductive Step ($n=k+1$): $$A^{k+1} = A^k \cdot A = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \quad \mathbf{[M1]}$$ $$= \begin{pmatrix} 1(1) + k(0) & 1(1) + k(1) \\ 0(1) + 1(0) & 0(1) + 1(1) \end{pmatrix} = \begin{pmatrix} 1 & k+1 \\ 0 & 1 \end{pmatrix} = \text{RHS}_{k+1} \quad \mathbf{[A1]}$$
  4. Conclusion: Since true for $n=1$, and truth for $n=k \implies$ truth for $n=k+1$, by mathematical induction $A^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$ for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$

Final Conclusion: Verified for all $n \in \mathbb{Z}^+$.

Exercise 8 Paper 1 · 7 Marks

Prove by mathematical induction that $5^n + 2(11^n)$ is divisible by $3$ for all $n \in \mathbb{Z}^+$.

View Complete Solution & Markscheme
  1. Base Step ($n=1$): $$5^1 + 2(11^1) = 5 + 22 = 27 = 3(9) \quad \mathbf{[M1]}$$ Divisible by $3$. True for $n=1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis: Assume $5^k + 2(11^k) = 3M$, so $5^k = 3M - 2(11^k)$ for some $M \in \mathbb{Z}$. $\mathbf{[M1]}$
  3. Inductive Step ($n=k+1$): $$5^{k+1} + 2(11^{k+1}) = 5(5^k) + 2(11)(11^k) = 5[3M - 2(11^k)] + 22(11^k) \quad \mathbf{[M1]}$$ $$= 15M - 10(11^k) + 22(11^k) = 15M + 12(11^k) = 3[5M + 4(11^k)] \quad \mathbf{[A1]}$$ Since $M, k \in \mathbb{Z}$, $5M + 4(11^k) \in \mathbb{Z}$. Hence divisible by $3$.
  4. Conclusion: Since true for $n=1$ and $P(k) \implies P(k+1)$, the statement holds for all $n \in \mathbb{Z}^+$ by mathematical induction. $\mathbf{[R1]}$

Final Conclusion: Verified for all $n \in \mathbb{Z}^+$.

Tier 3: Inequalities & Advanced Derivatives (Questions 9–10)
Exercise 9 Paper 1 · 7 Marks

Prove by mathematical induction that $n! > 2^n$ for all integers $n \ge 4$.

View Complete Solution & Markscheme
  1. Base Case ($n=4$): $$\text{LHS} = 4! = 24, \quad \text{RHS} = 2^4 = 16 \quad \mathbf{[M1]}$$ Since $24 > 16$, true for $n=4$. $\mathbf{[A1]}$
  2. Inductive Hypothesis: Assume $k! > 2^k$ for an integer $k \ge 4$. $\mathbf{[M1]}$
  3. Inductive Step ($n=k+1$): $$\text{LHS}_{k+1} = (k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k \quad (\text{by hypothesis}) \quad \mathbf{[M1]}$$ Since $k \ge 4$, $k+1 \ge 5 > 2$. Therefore: $(k+1) \cdot 2^k > 2 \cdot 2^k = 2^{k+1} = \text{RHS}_{k+1}$. Hence $(k+1)! > 2^{k+1}$. $\mathbf{[A1]}$
  4. Conclusion: Since true for $n=4$, and $P(k) \implies P(k+1)$, by induction $n! > 2^n$ for all integers $n \ge 4$. $\mathbf{[R1]}$

Final Conclusion: Proven for all integers $n \ge 4$.

Exercise 10 Paper 1 · 7 Marks

Let $f(x) = x e^x$. Prove by mathematical induction that the $n$th derivative is given by: $$\frac{d^n}{dx^n}(x e^x) = (x + n)e^x \quad \text{for all } n \in \mathbb{Z}^+$$

View Complete Solution & Markscheme
  1. Base Case ($n=1$): Using product rule on $x e^x$: $$\frac{d}{dx}(x e^x) = 1 \cdot e^x + x \cdot e^x = (x + 1)e^x \quad \mathbf{[M1]}$$ Formula with $n=1$: $(x + 1)e^x$. True for $n=1$. $\mathbf{[A1]}$
  2. Inductive Hypothesis: Assume $\frac{d^k}{dx^k}(x e^x) = (x + k)e^x$ for $k \in \mathbb{Z}^+$. $\mathbf{[M1]}$
  3. Inductive Step ($n=k+1$): $$\frac{d^{k+1}}{dx^{k+1}}(x e^x) = \frac{d}{dx}\left[\frac{d^k}{dx^k}(x e^x)\right] = \frac{d}{dx}\left[(x + k)e^x\right] \quad \mathbf{[M1]}$$ Apply product rule: $$= 1 \cdot e^x + (x+k)e^x = (x + k + 1)e^x = \text{RHS}_{k+1} \quad \mathbf{[A1]}$$
  4. Conclusion: Since true for $n=1$, and truth for $n=k$ implies truth for $n=k+1$, by mathematical induction $\frac{d^n}{dx^n}(x e^x) = (x + n)e^x$ for all $n \in \mathbb{Z}^+$. $\mathbf{[R1]}$

Final Conclusion: Proven for all $n \in \mathbb{Z}^+$.

Standard Series Sums

Summation Formulas Used in Induction

  • First $n$ natural numbers: $$\sum_{r=1}^n r = \frac{n(n+1)}{2}$$
  • Sum of squares: $$\sum_{r=1}^n r^2 = \frac{n(n+1)(2n+1)}{6}$$
  • Sum of cubes: $$\sum_{r=1}^n r^3 = \frac{n^2(n+1)^2}{4} = \left(\sum_{r=1}^n r\right)^2$$
Template

Full Concluding Sentence Template

  • Required Elements for the Final $R1$ Mark:
    1. Mention $P(1)$ is true (or base case $n_0$).
    2. Mention that assuming $P(k)$ is true implies $P(k+1)$ is true.
    3. Explicitly name "by the principle of mathematical induction".
    4. State the domain: "for all $n \in \mathbb{Z}^+$".
  • Suggested conclusion:
    "Since true for $n=1$, and true for $n=k$ implies true for $n=k+1$, by mathematical induction the statement is true for all $n \in \mathbb{Z}^+$."

Critical IB Examination Pitfalls in Induction

  • Assuming What Needs to Be Proved in Step 3: Writing down $\text{LHS}_{k+1} = \text{RHS}_{k+1}$ at the start of step 3 is circular reasoning. You must start strictly on $\text{LHS}_{k+1}$, manipulate it using the hypothesis, and independently derive $\text{RHS}_{k+1}$.
  • Omitting "LHS = RHS" in the Base Step: Just writing $1=1$ or checking without showing both sides evaluated forfeits the first method mark ($M1$).
  • Forgetting the Concluding Statement: Forgetting the final sentence forfeits the reasoning mark ($R1$). A correct algebraic proof without the concluding sentence loses up to 20% of the question marks.
  • Incorrect Inequality Direction: When proving $A > B$, multiplying or dividing by negative numbers or unjustified assumptions forfeits accuracy marks.

Section A: Diagnostic Check

4 core concept check questions. Immediate feedback and scoring.

Score: 0 / 4

Question 1

In a proof by mathematical induction that $3^{2n} - 1$ is divisible by $8$ for $n \in \mathbb{Z}^+$, what is the base case calculation?

Correct! For $n \in \mathbb{Z}^+$, the base case is $n=1$: $3^{2(1)} - 1 = 9 - 1 = 8 = 8(1)$.

Question 2

When proving $\sum_{r=1}^n r(r!) = (n+1)! - 1$, what is $\text{LHS}_{k+1}$ in terms of the inductive hypothesis $\text{LHS}_k$?

Correct! The sum up to $k+1$ is the sum up to $k$ plus the $(k+1)$th term, which is $(k+1)(k+1)!$.

Question 3

Why does writing $\text{LHS}_{k+1} = \text{RHS}_{k+1}$ at the very beginning of the inductive step forfeit marks on IB exams?

Correct! Starting with the equation assumes its truth before proving it. You must start with one side and derive the other.

Question 4

To prove $2^n > n^3$ for $n \ge 10$, what is the appropriate base step to evaluate?

Correct! Since the domain specified is $n \ge 10$, the base case must be $n = 10$.

Section B: Examination-Style Free Response Questions

Question 5 (Paper 1 Style · 6 marks)

Prove by mathematical induction that for all $n \in \mathbb{Z}^+$: $$1(1!) + 2(2!) + 3(3!) + \dots + n(n!) = (n+1)! - 1$$

Show Full Markscheme

Base Step ($n = 1$): [1 mark]
$\text{LHS} = 1(1!) = 1$; $\text{RHS} = (1+1)! - 1 = 2! - 1 = 2 - 1 = 1$.
$\text{LHS} = \text{RHS}$, statement true for $n = 1$. [M1]

Inductive Hypothesis: [1 mark]
Assume the statement is true for $n = k \in \mathbb{Z}^+$:
$\sum_{r=1}^k r(r!) = (k+1)! - 1$. [M1]

Inductive Step ($n = k+1$): [3 marks]
$\text{LHS}_{k+1} = \sum_{r=1}^k r(r!) + (k+1)(k+1)!$ [M1]
$= [(k+1)! - 1] + (k+1)(k+1)!$ (by hypothesis) [M1]
$= (k+1)![1 + (k+1)] - 1 = (k+1)!(k+2) - 1 = (k+2)! - 1 = ((k+1)+1)! - 1 = \text{RHS}_{k+1}$. [A1]

Concluding Statement: [1 mark]
Since the proposition is true for $n = 1$, and its truth for $n = k$ implies its truth for $n = k+1$, by the principle of mathematical induction the proposition is true for all $n \in \mathbb{Z}^+$. [R1]

Question 6 (Paper 1 Style · 8 marks)

Prove by mathematical induction that $3^{2n+2} - 8n - 9$ is divisible by $64$ for all integers $n \in \mathbb{Z}^+$.

Show Full Markscheme

Base Step ($n = 1$): [2 marks]
$3^{2(1)+2} - 8(1) - 9 = 3^4 - 8 - 9 = 81 - 17 = 64 = 64(1)$. [M1]
Since $64$ is divisible by $64$, the statement is true for $n = 1$. [A1]

Inductive Hypothesis: [1 mark]
Assume true for $n = k \in \mathbb{Z}^+$:
$3^{2k+2} - 8k - 9 = 64A$ for some integer $A \in \mathbb{Z}$, so $3^{2k+2} = 64A + 8k + 9$. [M1]

Inductive Step ($n = k+1$): [4 marks]
Expression for $n = k+1$:
$3^{2(k+1)+2} - 8(k+1) - 9 = 3^{2k+4} - 8k - 8 - 9 = 3^2 \cdot 3^{2k+2} - 8k - 17$ [M1]
$= 9(3^{2k+2}) - 8k - 17$
Substitute $3^{2k+2} = 64A + 8k + 9$: [M1]
$= 9(64A + 8k + 9) - 8k - 17$
$= 9(64A) + 72k + 81 - 8k - 17$
$= 9(64A) + 64k + 64$ [A1]
$= 64(9A + k + 1)$
Since $A, k \in \mathbb{Z}$, $9A + k + 1 \in \mathbb{Z}$. Hence $3^{2(k+1)+2} - 8(k+1) - 9$ is divisible by $64$. [A1]

Concluding Statement: [1 mark]
Since true for $n = 1$, and truth for $n = k$ implies truth for $n = k+1$, by mathematical induction $3^{2n+2} - 8n - 9$ is divisible by $64$ for all $n \in \mathbb{Z}^+$. [R1]