BMO Induction: Choosing a Statement Strong Enough to Prove

The Specific Challenge of Induction in BMO

For students preparing for the British Mathematical Olympiad (BMO), induction is often viewed as a mechanical tool. However, the true difficulty lies not in the algebraic manipulation of the step from $k$ to $k + 1$ , but in choosing the statement to prove by induction. A common failure mode is attempting to prove a statement that is too weak, causing the induction step to break because the hypothesis does not provide enough information to reach the conclusion.

This article addresses that specific reasoning gap. Unlike broad preparation guides which cover general problem-solving frameworks, we focus exclusively on the strategic selection of the induction hypothesis. This skill is critical for BMO Round 1 and Round 2 problems where number theory or combinatorial identities require rigorous proof structures. For broader context on writing complete proofs, refer to our guide on BMO Infinite Descent: How to Write a Complete Proof.

Hypothetical Case 1: When the Direct Statement Works

Consider a teaching illustration: prove that for all integers $n \geq 1$ , the sum of the first $n$ odd numbers is $n^{2}$ . Let $S_{n} = 1 + 3 + 5 + \dots + (2 n - 1)$ .

Attempt: We try to prove $P (n) : S_{n} = n^{2}$ .

Base Case: $n = 1$ , $S_{1} = 1 = 1^{2}$ . Holds.
Inductive Step: Assume $S_{k} = k^{2}$ . We want to show $S_{k + 1} = (k + 1)^{2}$ .

$S_{k + 1} = S_{k} + (2 (k + 1) - 1) = k^{2} + 2 k + 1 = (k + 1)^{2}$ .

In this simple case, the direct statement works because the recurrence $S_{k + 1} = S_{k} + (2 k + 1)$ depends only on the immediately preceding term, and the algebraic closure is immediate. However, BMO problems rarely present such clean linear relationships. The skill is recognizing when this pattern breaks.

Hypothetical Case 2: The Strengthened Hypothesis (Worked)

Consider a second teaching illustration. Define a sequence by $a_{1} = 1$ , $a_{2} = 2$ , and $a_{n} = 2 a_{n - 1} + a_{n - 2}$ for $n \geq 3$ . We want to prove that $a_{n}$ is odd for all $n \geq 1$ .

Weak Attempt: Let $P (n)$ be “ $a_{n}$ is odd.”

Base Cases: $a_{1} = 1$ (odd), $a_{2} = 2$ (even). Already fails at $n = 2$ .

We must strengthen. Observe the pattern: $a_{1} = 1$ (odd), $a_{2} = 2$ (even), $a_{3} = 2 (2) + 1 = 5$ (odd), $a_{4} = 2 (5) + 2 = 12$ (even). The sequence alternates parity.

Strengthened Statement: Let $P (n)$ be: “ $a_{n}$ is odd when $n$ is odd, and $a_{n}$ is even when $n$ is even.”

Base Cases: $n = 1$ : $a_{1} = 1$ odd ✓; $n = 2$ : $a_{2} = 2$ even ✓.
Inductive Step: Assume $P (j)$ holds for all $j \leq k$ . Consider $a_{k + 1} = 2 a_{k} + a_{k - 1}$ .

Case analysis on $k + 1$ :

★ Coaching

Preparing for BMO 2026?

Talk to our advisor on WhatsApp — free, no sales pitch. Here is how we help:

Competition registration, handled for you

Free past papers & worked solutions

1-on-1 trial lesson (paid)

Scan the WeChat QR code

Reply within 1 business day

WhatsApp QR code for BMO Pathway Guide advisor

WeChat

If $k + 1$ is odd, then $k$ is even and $k - 1$ is odd. By hypothesis, $a_{k}$ is even and $a_{k - 1}$ is odd. Thus $a_{k + 1} = 2 (even) + (odd) = even + odd = odd$ . ✓
If $k + 1$ is even, then $k$ is odd and $k - 1$ is even. By hypothesis, $a_{k}$ is odd and $a_{k - 1}$ is even. Thus $a_{k + 1} = 2 (odd) + (even) = even + even = even$ . ✓

Key insight: The original goal (“ $a_{n}$ is odd”) was unprovable because it was false. But even when the direct statement is true, the same principle applies: if the recurrence couples terms in a way that parity, sign, or magnitude must be tracked together, the induction hypothesis must carry all relevant information. The strengthened statement $P (n)$ here is not merely a fix for a false claim—it is a template for how to package auxiliary conditions.

Practical Diagnostic Table

Symptom	Likely Cause	Strategic Adjustment
Step $k \to k + 1$ leaves an unproven remainder term.	Hypothesis is too weak; missing auxiliary conditions.	Add a second condition to $P (n)$ (e.g., prove parity and magnitude simultaneously).
Recurrence depends on $a_{k - 1}, a_{k - 2}, \dots$ .	Weak induction only assumes $P (k)$ .	Switch to Strong Induction (assume $\forall j \leq k, P (j)$ ).
Inequality direction flips or becomes loose.	Bound is not tight enough for the next step.	Tighten the inequality constant in the hypothesis.

Targeted Practice Sequence

To build this specific skill, avoid random problem sets. Instead, follow a structured progression:

Identify Dependencies: Take a past paper question and map out which previous terms are needed to calculate the current term. Does it need $n - 1$ only, or $n - 1$ and $n - 2$ ?
Draft Two Statements: Write down the minimal statement required by the problem, and then write a “strengthened” version that includes extra properties (like sign, parity, or bounds).
Test the Gap: Attempt the inductive step for both. Observe exactly where the minimal one fails and how the strengthened one bridges the gap.

For further reading on handling recursive structures, see our article on BMO Infinite Descent: How to Write a Complete Proof. Additionally, understanding the scoring criteria for partial credit when a full induction fails is covered in BMO1 Past Papers Solutions: Requesting Worked Answers and Proof Feedback.

Conclusion: Demonstrating Mastery

The next time you encounter a BMO problem requiring induction, pause before writing the base case. Spend five minutes analyzing the logical dependencies. Your goal is not just to prove the statement given, but to construct a statement that is inductively closed. This meta-skill—choosing the right abstraction—is what separates high-scoring candidates from those who struggle with the final few marks.

Strengthening the Hypothesis

Frequently Asked Questions

What is the difference between weak and strong induction?

Weak induction assumes the statement is true for n=k to prove n=k+1. Strong induction assumes the statement is true for all integers up to k to prove k+1. Use strong induction when the next term depends on multiple previous terms.

How do I know if my induction hypothesis is too weak?

If you cannot algebraically manipulate the expression for P(k+1) to match the form of P(k) without leaving unresolved terms, your hypothesis likely lacks necessary constraints like bounds or parity.

Is strengthening the statement always necessary for BMO?

No, many BMO problems have self-contained recurrences. However, for complex number theory or combinatorics problems, strengthening the hypothesis is a frequent and powerful technique to ensure the induction step closes logically.