Recognition: Two-Step Recurrences Like a_n = f(a_{n-1}, a_{n-2}) Need Strong Induction

You meet a problem that looks innocent enough.

Define a_1 = 1, a_2 = 3, and a_n = 2 a_{n-1} - a_{n-2} for n \geq 3. Prove that a_n = 2n - 1 for every positive integer n.

You open your usual induction template. Base case: check n = 1. Inductive step: assume P(k), prove P(k+1). But the moment you try to derive a_{k+1}, you read the recurrence and see it demands both a_k and a_{k-1}. Your hypothesis gave you one — you need two.

This is the signal. When the recurrence reaches back by two steps, weak induction leaves you short by one case. You need strong induction — the version that hands you the truth of P(1), P(2), \dots, P(k) all at once.

Recognising this instantly is the skill. It saves you from writing a broken proof and noticing the gap only after half a page of algebra.

The recognition rule

Look at the recurrence. Count how many earlier terms appear on the right-hand side.

a_n depends on a_{n-1} only → weak induction is sufficient (carry forward just the last case).
a_n depends on a_{n-1} and a_{n-2} → use strong induction (you need the last two cases).
a_n depends on a_{n-1}, a_{n-2}, \dots, a_{n-m} → use strong induction with m base cases.

The rule is mechanical. The recurrence's depth of reach sets the number of previous cases your step needs, which sets the flavour of induction you pick.

A recurrence of depth $1$ (top) only looks back one step, so weak induction — carrying $P(k)$ to $P(k+1)$ — matches. A recurrence of depth $2$ (bottom) looks back two steps, so the inductive step needs both $P(k)$ and $P(k-1)$; strong induction gives you exactly that.

Why weak induction breaks

Take the example from the top. Suppose you try weak induction to prove a_n = 2n - 1.

Base case (n = 1). a_1 = 1 = 2(1) - 1. \checkmark

Inductive step. Assume P(k): a_k = 2k - 1. Prove P(k+1): a_{k+1} = 2(k+1) - 1 = 2k + 1.

From the recurrence: a_{k+1} = 2 a_k - a_{k-1}. Substitute a_k = 2k - 1. You get a_{k+1} = 2(2k - 1) - a_{k-1} = 4k - 2 - a_{k-1}.

Why you are stuck: to finish, you need to know a_{k-1}. The weak hypothesis said nothing about a_{k-1}; it only gave you a_k. You have walked into a dead end — not because the claim is false, but because the tool is too weak.

You could try to bandage this by assuming a_{k-1} = 2(k-1) - 1 = 2k - 3 anyway, but that is smuggling in strong induction without calling it by name. Better to name it honestly.

The strong-induction fix

Rewrite the proof with the correct tool.

Claim. a_n = 2n - 1 for every positive integer n, where a_1 = 1, a_2 = 3, and a_n = 2 a_{n-1} - a_{n-2} for n \geq 3.

Base cases (n = 1, 2). a_1 = 1 = 2(1) - 1. \checkmark And a_2 = 3 = 2(2) - 1. \checkmark

Why two base cases: the recurrence has depth 2, so the step first applies at n = 3. Both n = 1 and n = 2 must be verified directly because the step cannot reach them.

Inductive step. Let k \geq 2. Assume P(1), P(2), \dots, P(k) all hold: a_j = 2j - 1 for every 1 \leq j \leq k. Show P(k+1): a_{k+1} = 2(k+1) - 1 = 2k + 1.

From the recurrence,

a_{k+1} = 2 a_k - a_{k-1}.

By the strong hypothesis, a_k = 2k - 1 and a_{k-1} = 2(k-1) - 1 = 2k - 3. Substitute:

a_{k+1} = 2(2k - 1) - (2k - 3) = 4k - 2 - 2k + 3 = 2k + 1.

Why it closes: strong induction let you reach into the hypothesis twice — once for a_k and once for a_{k-1} — and both substitutions turned the recurrence into the target formula.

By strong induction, a_n = 2n - 1 for all n \geq 1. \square

The fix was a two-word change in the template: "strong induction" instead of "induction," plus a matching second base case. The algebra was the same; the logical scaffolding changed.

How many base cases?

Match the number of base cases to the depth of the recurrence.

Depth 1: one base case (e.g., n = 1).
Depth 2: two base cases (e.g., n = 1, 2).
Depth m: m base cases (e.g., n = 1, 2, \dots, m).

The reason is direct. The recurrence's first valid index is n_0 + m, where n_0 is the smallest index in the recurrence. Every value of a_n for n < n_0 + m must be given by hand — that is, verified as a base case — because the recurrence cannot derive them.

For the Fibonacci sequence F_n = F_{n-1} + F_{n-2} with F_1 = F_2 = 1, the depth is 2, the recurrence first applies at n = 3, and you need the two base cases F_1, F_2. Any theorem about Fibonacci proved by induction starts with verifying both.

A classic: Fibonacci and the golden ratio bound

Claim. F_n \leq \phi^{n-1} for all n \geq 1, where \phi = \frac{1 + \sqrt{5}}{2} and F_n is the Fibonacci sequence (F_1 = F_2 = 1, F_n = F_{n-1} + F_{n-2} for n \geq 3).

Recognition. The recurrence has depth 2, so strong induction is the tool. Two base cases needed.

Base cases.

n = 1: F_1 = 1 and \phi^0 = 1. 1 \leq 1. \checkmark
n = 2: F_2 = 1 and \phi^1 \approx 1.618. 1 \leq 1.618. \checkmark

Inductive step. Let k \geq 2. Assume F_j \leq \phi^{j-1} for every 1 \leq j \leq k. Then

F_{k+1} = F_k + F_{k-1} \leq \phi^{k-1} + \phi^{k-2} = \phi^{k-2}(\phi + 1).

The golden ratio satisfies \phi^2 = \phi + 1 (that is the defining equation). So

F_{k+1} \leq \phi^{k-2} \cdot \phi^2 = \phi^k.

That is F_{k+1} \leq \phi^{(k+1) - 1}, which is P(k+1). \checkmark

Why the proof rides on depth 2: the step used both F_k \leq \phi^{k-1} and F_{k-1} \leq \phi^{k-2}. Weak induction would have given only one; it would not have closed the algebra.

By strong induction, F_n \leq \phi^{n-1} for all n \geq 1.

This kind of exponential bound on Fibonacci is the gateway to Binet's formula and comes up in JEE Advanced and olympiad problems constantly.

A quick checklist for recognition

Before you start writing an induction proof for a recurrence problem:

Count the depth of the recurrence. How far back does a_n reach? That is your m.
Pick the induction type. Depth 1 → weak is fine. Depth \geq 2 → strong.
Count the base cases. You need m of them (or start the proof at the first n where the recurrence applies directly, and verify all smaller n by hand).
State the hypothesis matching your choice. For weak: "assume P(k)." For strong: "assume P(j) for all j \leq k."
Audit the step. When you substitute from the hypothesis, verify that every term you need is within the hypothesis's reach.

Step 5 is the safety net. If the step demands a_{k-3} and your hypothesis only covers a_k, a_{k-1}, a_{k-2}, you have a depth-4 recurrence and need three base cases, not two.

Other signals that strong induction is the right tool

Depth-\geq 2 recurrences are the most common trigger, but they are not the only one. You also reach for strong induction when:

The object splits into smaller sub-objects. Proving every integer \geq 2 factors into primes uses n = a \cdot b with a, b < n; strong induction covers both a and b at once. Same pattern for splitting polynomials, trees, or numbers in base representations.
The inductive step needs to apply to a value that might be much smaller than k. If your step says "consider k - d for some d that depends on k," you cannot guarantee d = 1; you need the hypothesis to cover every earlier index.
The claim is about existence for every n, and the construction uses several earlier cases. Greedy-style proofs about the Euclidean algorithm, game-theory positions, and competition problems involving "the smallest counterexample" often map cleanly onto strong induction.

In every case, the common thread is: the inductive step reaches back by a variable amount or by more than one step. The moment you see that, strong induction is the default.

The one-line takeaway

Depth of the recurrence = number of previous cases the inductive step needs = number of base cases you must verify. Depth \geq 2 forces strong induction. Read the recurrence, count the depth, pick the tool — in that order, every time.

This recognition rule turns "which induction do I use?" from a judgement call into a mechanical decision. It is the kind of habit that makes JEE-paced proof writing fast and safe.