What Is Mathematical Induction?

Mathematical induction is a proof method used to prove a statement \(P(n)\) for every integer value from a starting point onward. In IB Math AA HL, the starting point is often \(n=1\), but some questions may start at \(n=0\), \(n=2\), or another specified integer. The essential idea is not to test every value of \(n\). Testing values such as \(n=1\), \(n=2\), and \(n=3\) may suggest a pattern, but it does not prove the pattern for all positive integers. Induction proves an infinite chain of truth using a finite logical structure.

A statement suitable for induction usually depends on a natural number or positive integer. Examples include:

• \(\displaystyle 1+2+\cdots+n=\frac{n(n+1)}{2}\)
• \(\displaystyle \sum_{r=1}^{n}r^2=\frac{n(n+1)(2n+1)}{6}\)
• \(\displaystyle 7^n-1\) is divisible by \(6\)
• \(\displaystyle 2^n\geq n+1\) for \(n\in\mathbb{Z}^{+}\)
• \(\displaystyle \frac{d^n}{dx^n}e^{ax}=a^n e^{ax}\)

Why Induction Matters in IB Mathematics AA HL

IB Mathematics: Analysis and Approaches HL places strong emphasis on reasoning, formal argument, algebraic fluency and communication. Induction fits this purpose because it asks students to justify a general result, not merely compute an answer. A student who understands induction has to control notation, state assumptions precisely, manipulate algebra, and conclude logically. That combination is exactly what makes the topic valuable for higher-level mathematics.

In AA HL, induction connects naturally with several areas of the syllabus. In sequences and series, it proves sum formulae. In divisibility, it proves statements such as \(a^n-b^n\) being divisible by a fixed integer. In calculus, it can prove higher derivative patterns. In complex numbers, it supports results such as De Moivre-style identities. In Paper 3-style investigations, it may appear after a student has found a pattern from earlier parts of a problem.

Visual Diagram: The Induction Chain

The AA HL Induction Template

A strong induction proof is not only about algebra. It must be written in a recognizable logical structure. Students often lose marks because they know the manipulation but fail to state the proof clearly. Use this template whenever the problem asks you to prove a statement for all positive integers.

Formal Principle of Mathematical Induction

The principle of mathematical induction can be written in a compact form. Suppose \(P(n)\) is a statement depending on an integer \(n\). If:

\[ P(1)\text{ is true} \]

and

\[ P(k)\Rightarrow P(k+1)\text{ for every }k\geq 1, \]

then:

\[ P(n)\text{ is true for every }n\in\mathbb{Z}^{+}. \]

Some questions begin at a different value. If the question says prove for \(n\geq 3\), then the base case should be \(n=3\), not \(n=1\). The logic becomes:

\[ P(3)\text{ is true and }P(k)\Rightarrow P(k+1)\text{ for }k\geq 3. \]

Worked Example 1: Sum of the First \(n\) Positive Integers

Prove by induction that:

\[ 1+2+3+\cdots+n=\frac{n(n+1)}{2},\quad n\in\mathbb{Z}^{+}. \]

Solution

Let \(P(n)\) be the statement:

\[ \sum_{r=1}^{n}r=\frac{n(n+1)}{2}. \]

Base case: For \(n=1\), the left-hand side is \(1\), and the right-hand side is:

\[ \frac{1(1+1)}{2}=1. \]

Therefore \(P(1)\) is true.

Induction hypothesis: Assume \(P(k)\) is true for some \(k\in\mathbb{Z}^{+}\). That is:

\[ \sum_{r=1}^{k}r=\frac{k(k+1)}{2}. \]

Induction step: We need to prove \(P(k+1)\):

\[ \sum_{r=1}^{k+1}r=\frac{(k+1)(k+2)}{2}. \]

Starting from the left-hand side:

\[ \sum_{r=1}^{k+1}r = \sum_{r=1}^{k}r+(k+1) = \frac{k(k+1)}{2}+(k+1) \]

Factor and simplify:

\[ \frac{k(k+1)}{2}+(k+1) = (k+1)\left(\frac{k}{2}+1\right) = (k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}. \]

This is exactly the required form for \(P(k+1)\). Since \(P(1)\) is true and \(P(k)\Rightarrow P(k+1)\), the statement is true for all \(n\in\mathbb{Z}^{+}\) by mathematical induction.

Worked Example 2: Sum of Squares

Prove that:

\[ \sum_{r=1}^{n}r^2=\frac{n(n+1)(2n+1)}{6},\quad n\in\mathbb{Z}^{+}. \]

Base case: For \(n=1\):

\[ \sum_{r=1}^{1}r^2=1^2=1, \qquad \frac{1(2)(3)}{6}=1. \]

So \(P(1)\) is true.

Induction hypothesis: Assume that for \(n=k\):

\[ \sum_{r=1}^{k}r^2=\frac{k(k+1)(2k+1)}{6}. \]

Induction step:

\[ \sum_{r=1}^{k+1}r^2 = \sum_{r=1}^{k}r^2+(k+1)^2. \]

Use the induction hypothesis:

\[ \sum_{r=1}^{k+1}r^2 = \frac{k(k+1)(2k+1)}{6}+(k+1)^2. \]

Factor out \(k+1\):

\[ = (k+1)\left(\frac{k(2k+1)}{6}+k+1\right) = (k+1)\left(\frac{2k^2+k+6k+6}{6}\right). \]

Now simplify the quadratic:

\[ = (k+1)\left(\frac{2k^2+7k+6}{6}\right) = (k+1)\left(\frac{(k+2)(2k+3)}{6}\right). \]

Therefore:

\[ \sum_{r=1}^{k+1}r^2 = \frac{(k+1)(k+2)(2k+3)}{6} = \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}. \]

This proves \(P(k+1)\). Therefore, by induction, the formula is true for all positive integers \(n\).

Worked Example 3: Divisibility Proof

Prove that \(7^n-1\) is divisible by \(6\) for all \(n\in\mathbb{Z}^{+}\).

Base case: When \(n=1\):

\[ 7^1-1=6. \]

Since \(6\) is divisible by \(6\), \(P(1)\) is true.

Induction hypothesis: Assume \(P(k)\) is true. Then for some integer \(m\):

\[ 7^k-1=6m. \]

So:

\[ 7^k=6m+1. \]

Induction step: Consider \(7^{k+1}-1\):

\[ 7^{k+1}-1 = 7\cdot 7^k-1 = 7(6m+1)-1 = 42m+6 = 6(7m+1). \]

Since \(7m+1\) is an integer, \(7^{k+1}-1\) is divisible by \(6\). Therefore \(P(k+1)\) is true. By induction, \(7^n-1\) is divisible by \(6\) for all \(n\in\mathbb{Z}^{+}\).

Worked Example 4: Inequality by Induction

Prove that:

\[ 2^n\geq n+1,\quad n\in\mathbb{Z}^{+}. \]

Base case: For \(n=1\):

\[ 2^1=2,\qquad 1+1=2. \]

So \(2^1\geq 2\), and \(P(1)\) is true.

Induction hypothesis: Assume \(2^k\geq k+1\) for some \(k\in\mathbb{Z}^{+}\).

Induction step:

\[ 2^{k+1}=2\cdot 2^k. \]

Using the hypothesis \(2^k\geq k+1\):

\[ 2^{k+1}\geq 2(k+1)=2k+2. \]

Since \(k\geq 1\), we have:

\[ 2k+2\geq k+2. \]

Therefore:

\[ 2^{k+1}\geq k+2=(k+1)+1. \]

Thus \(P(k+1)\) is true. By mathematical induction, \(2^n\geq n+1\) for all \(n\in\mathbb{Z}^{+}\).

Worked Example 5: Geometric Sum

Prove that:

\[ \sum_{r=0}^{n}3^r=\frac{3^{n+1}-1}{2},\quad n\geq 0. \]

Base case: For \(n=0\):

\[ \sum_{r=0}^{0}3^r=1,\qquad \frac{3^{1}-1}{2}=1. \]

So \(P(0)\) is true.

Induction hypothesis: Assume for \(n=k\):

\[ \sum_{r=0}^{k}3^r=\frac{3^{k+1}-1}{2}. \]

Induction step:

\[ \sum_{r=0}^{k+1}3^r = \sum_{r=0}^{k}3^r+3^{k+1} = \frac{3^{k+1}-1}{2}+3^{k+1}. \]

Simplify:

\[ \frac{3^{k+1}-1}{2}+3^{k+1} = \frac{3^{k+1}-1+2\cdot 3^{k+1}}{2} = \frac{3\cdot 3^{k+1}-1}{2} = \frac{3^{k+2}-1}{2}. \]

This is the required result for \(k+1\). Therefore the formula is true for all integers \(n\geq 0\).

Worked Example 6: Higher Derivative Pattern

Prove that:

\[ \frac{d^n}{dx^n}e^{ax}=a^n e^{ax},\quad n\in\mathbb{Z}^{+}. \]

Base case: For \(n=1\):

\[ \frac{d}{dx}e^{ax}=ae^{ax}=a^1e^{ax}. \]

So \(P(1)\) is true.

Induction hypothesis: Assume that:

\[ \frac{d^k}{dx^k}e^{ax}=a^k e^{ax}. \]

Induction step: Differentiate both sides once more:

\[ \frac{d^{k+1}}{dx^{k+1}}e^{ax} = \frac{d}{dx}\left(a^k e^{ax}\right) = a^k\cdot ae^{ax} = a^{k+1}e^{ax}. \]

Therefore \(P(k+1)\) is true. By induction, the formula holds for all positive integers \(n\).

Worked Example 7: De Moivre-Style Induction

A common advanced use of induction is proving a power identity for complex numbers. For example, prove:

\[ (\cos\theta+i\sin\theta)^n=\cos(n\theta)+i\sin(n\theta),\quad n\in\mathbb{Z}^{+}. \]

Base case: For \(n=1\), both sides equal \(\cos\theta+i\sin\theta\), so \(P(1)\) is true.

Induction hypothesis: Assume:

\[ (\cos\theta+i\sin\theta)^k=\cos(k\theta)+i\sin(k\theta). \]

Induction step:

\[ (\cos\theta+i\sin\theta)^{k+1} = (\cos\theta+i\sin\theta)^k(\cos\theta+i\sin\theta). \]

Use the induction hypothesis:

\[ = (\cos(k\theta)+i\sin(k\theta))(\cos\theta+i\sin\theta). \]

Expand:

\[ = \cos(k\theta)\cos\theta-\sin(k\theta)\sin\theta +i\left(\sin(k\theta)\cos\theta+\cos(k\theta)\sin\theta\right). \]

Using the angle addition formulae:

\[ = \cos((k+1)\theta)+i\sin((k+1)\theta). \]

Therefore \(P(k+1)\) is true, and the identity follows by induction.

Common Types of IB AA HL Induction Questions

How to Read an Induction Question

Before starting an induction proof, identify four things: the statement, the starting value, the target form for \(k+1\), and the algebraic bridge from \(P(k)\) to \(P(k+1)\). Many students begin writing immediately and then become stuck because they do not know what the final expression should look like. The target form is obtained by replacing every \(n\) in the original statement with \(k+1\).

For example, if the target statement is:

\[ \sum_{r=1}^{n}r^2=\frac{n(n+1)(2n+1)}{6}, \]

then \(P(k+1)\) should be:

\[ \sum_{r=1}^{k+1}r^2 = \frac{(k+1)(k+2)(2k+3)}{6}. \]

That target expression tells you what your algebra must become. In an exam, write it clearly before doing the manipulation. It gives your working direction and helps avoid random simplification.

Common Mistakes That Cost Marks

Score Guidelines for Induction Proofs

IB mark schemes vary by question, so no fixed mark table can represent every induction problem. However, induction marks usually reward the same proof components. The table below is a practical RevisionTown study guide that helps students understand where credit is usually earned.

IB Mathematics AA HL Assessment Table

IB Mathematics: Analysis and Approaches HL is assessed through external examination papers and an internal mathematical exploration. Induction is most naturally tested as formal proof in external assessment, but the reasoning skills behind induction also help with internal exploration, especially when students identify and justify patterns.

Current and 2029 Update Notes

Students preparing for current sessions should follow their school’s official IB guidance and the current session timetable. The public IB curriculum update also indicates a transition to a refreshed Mathematics: Analysis and Approaches course, launched for first teaching in August 2027 with first assessment in May 2029. For the updated assessment model, IB states that Higher Level Paper 1 and Paper 2 have a reduced number of items so that total marks become \(100\) each, Paper 3 becomes \(50\) marks, and Paper 3 time becomes one hour. This does not change the core study habit for induction: write proof structure cleanly and use precise algebra.

Next IB AA HL Exam Timetable Note

For the May 2026 public examination schedule, the listed Mathematics: Analysis and Approaches HL sessions are:

IB Mathematics Grade Descriptors: What Strong Students Demonstrate

IB mathematics grades are reported from \(1\) to \(7\), with \(7\) as the highest grade. Exact grade boundaries vary by examination session and should not be guessed from a single past session. For induction, the practical target is not a fixed percentage boundary; it is the quality of mathematical reasoning. A high-scoring response communicates a complete argument, uses correct notation, justifies conclusions and handles algebra accurately.

How to Revise Induction Efficiently

The most effective way to revise induction is not to memorize many finished proofs. Instead, memorize the structure and then practise different algebraic bridges. Every induction proof asks the same logical question: if the statement is true at \(k\), how do we force it to become true at \(k+1\)? The details change, but the skeleton remains stable.

Revision Method 1: Write the Target First

Before solving, write both \(P(k)\) and \(P(k+1)\). This helps you see the destination. For a formula:

\[ P(n): \quad F(n)=G(n), \]

you should write:

\[ P(k): \quad F(k)=G(k), \qquad P(k+1): \quad F(k+1)=G(k+1). \]

Most mistakes happen because students manipulate \(P(k)\) without knowing what \(P(k+1)\) should look like.

Revision Method 2: Practise One Type at a Time

Spend one session on sums, one session on divisibility, one session on inequalities, and one session on advanced applications such as derivatives or complex numbers. Mixed practice is useful later, but early revision is more effective when each proof type becomes familiar.

Revision Method 3: Use a Final Sentence Every Time

A complete final sentence is a simple way to protect marks:

\[ \text{Since }P(1)\text{ is true and }P(k)\Rightarrow P(k+1), \text{ the statement is true for all }n\in\mathbb{Z}^{+}. \]

Adapt the starting value and domain when needed.

Induction Practice Questions

1. Prove that \(\displaystyle \sum_{r=1}^{n}r=\frac{n(n+1)}{2}\) for \(n\in\mathbb{Z}^{+}\).
2. Prove that \(\displaystyle \sum_{r=1}^{n}r^3=\left(\frac{n(n+1)}{2}\right)^2\) for \(n\in\mathbb{Z}^{+}\).
3. Prove that \(5^n-1\) is divisible by \(4\) for all \(n\in\mathbb{Z}^{+}\).
4. Prove that \(3^n\geq 2n+1\) for all \(n\in\mathbb{Z}^{+}\).
5. Prove that \(\displaystyle \sum_{r=0}^{n}2^r=2^{n+1}-1\) for all integers \(n\geq0\).
6. Prove that \(\displaystyle \frac{d^n}{dx^n}\sin x=\sin\left(x+\frac{n\pi}{2}\right)\) for all \(n\in\mathbb{Z}^{+}\).
7. Prove that \(11^n-1\) is divisible by \(10\) for all \(n\in\mathbb{Z}^{+}\).
8. Prove that \(n^3+2n\) is divisible by \(3\) for all \(n\in\mathbb{Z}^{+}\).

Quick Answers and Hints

Induction vs Pattern Spotting

Pattern spotting is useful, but it is not proof. For example, checking that:

\[ 1=1,\quad 1+2=3,\quad 1+2+3=6 \]

may suggest the formula \(\frac{n(n+1)}{2}\), but it does not prove it for \(n=1000\), \(n=10^6\), or every positive integer. Mathematical induction turns the observed pattern into a rigorous argument. This distinction is especially important in AA HL because the course values mathematical proof and clear justification.

Teacher Notes for Using This Page

Teachers can use this page as a class introduction, a revision handout, or a self-study resource. A useful classroom sequence is: first, ask students to evaluate a formula for \(n=1,2,3\); second, ask why that is not enough; third, introduce the induction chain diagram; fourth, practise the template on a simple sum; fifth, move into a divisibility or inequality proof. This progression helps students understand induction as logic before they face heavier algebra.

For stronger AA HL students, the most productive extension is to connect induction with proof in other areas. Ask students to prove a derivative pattern, a complex-number identity, or a recurrence relation. These examples show that induction is not a small isolated skill; it is a general method for proving infinite families of statements.

Student Exam Strategy

• Write \(P(n)\) clearly before starting.
• Check the correct starting value from the question.
• Show the base case fully, even when it is simple.
• State the induction hypothesis exactly.
• Write the target \(P(k+1)\) before simplifying.
• Use the hypothesis visibly in the working.
• Factor until the expression matches the target.
• End with a formal conclusion.

Frequently Asked Questions

Conclusion

Mathematical induction is a compact but powerful proof method. For IB Mathematics AA HL, it trains exactly the skills the course values: logical structure, algebraic fluency, pattern recognition, precise notation and clear communication. The key is to avoid treating induction as a memorized paragraph. Instead, understand the chain: prove the first case, assume one arbitrary case, prove the next case, and conclude for all required integers. Once this structure becomes automatic, induction becomes one of the most reliable proof topics in AA HL.