Recognition: When a_{n+1} Depends on All of a_1, a_2, ..., a_n, Use Strong Induction Immediately

A two-step recurrence like a_{n+1} = 2 a_n - a_{n-1} forces strong induction because it reaches back by two. But there is a more extreme version of this pattern that students miss all the time:

a_1 is given, and for n \geq 1, a_{n+1} depends on all of a_1, a_2, \dots, a_n.

When the recurrence reaches back to every previous term, ordinary induction is hopeless. You cannot carry forward just P(k); you need the truth of P(j) for every j \leq k at once, because the recurrence itself demands all those values. Strong induction is the only reasonable tool.

Recognising this in the problem statement — not three pages into the failed attempt — is the skill.

The signal

The recurrence has one of these shapes:

a_{n+1} = a_1 + a_2 + \dots + a_n
a_{n+1} = a_1 \cdot a_2 \cdots a_n + 1
a_{n+1} = \max(a_1, a_2, \dots, a_n)
a_{n+1} = f(a_1, a_2, \dots, a_n) where f is any function of all prior terms

The common feature: the right-hand side indexes over 1 \leq j \leq n, not just over a fixed small window near n. That "all prior" quantifier is the red flag.

When you see it, say to yourself: strong induction. Do not bother trying weak induction first; the weakness of the hypothesis will show up the moment you try to substitute into the step.

When the recurrence's right-hand side sums, multiplies, or otherwise combines *every* prior term, the inductive step needs access to every $P(j)$ for $j \leq k$. This is strong induction by definition. Weak induction, which carries only $P(k)$ forward, is structurally inadequate.

Why weak induction fails here

The weak hypothesis is: "P(k) is true." That is one fact about one index.

But the recurrence a_{k+1} = a_1 + a_2 + \dots + a_k demands that you compute the sum of k values. If your hypothesis only tells you about a_k — not about a_1, \dots, a_{k-1} — you cannot evaluate the right-hand side. You have a formula you cannot plug numbers into.

This is not a subtle issue. It is an immediate structural block that you hit on the first line of the step. Weak induction simply does not give you enough hypothesis to even write down a_{k+1}.

Strong induction, on the other hand, gives you: "P(j) is true for every 1 \leq j \leq k." That is k facts, one per earlier index. Now you can evaluate the right-hand side: substitute each a_j by whatever P(j) says it equals, sum them, and you have a_{k+1}.

The worked pattern

Claim. Let a_1 = 1 and a_{n+1} = a_1 + a_2 + \dots + a_n for n \geq 1. Prove a_n = 2^{n-2} for n \geq 2, with a_1 = 1.

Quick sanity check. a_2 = a_1 = 1 = 2^0 = 2^{2-2}. \checkmark. a_3 = a_1 + a_2 = 2 = 2^1 = 2^{3-2}. \checkmark. a_4 = a_1 + a_2 + a_3 = 4 = 2^2 = 2^{4-2}. \checkmark. The pattern is real.

Choice of tool. The recurrence for a_{n+1} sums all prior terms, so strong induction is the right choice.

Base cases. a_1 = 1 is given. a_2 = a_1 = 1 = 2^0 = 2^{2-2}. So P(1) and P(2) both hold.

Why two base cases here: the formula has a slightly different form at n = 1 (a_1 = 1, not 2^{-1}), so the formula starts at n = 2. We verify the boundary explicitly.

Inductive step. Let k \geq 2. Assume P(j) holds for every 2 \leq j \leq k, i.e. a_j = 2^{j-2} for 2 \leq j \leq k. Also a_1 = 1. Show a_{k+1} = 2^{k-1}.

From the recurrence:

a_{k+1} = a_1 + a_2 + a_3 + \dots + a_k = 1 + 2^0 + 2^1 + \dots + 2^{k-2}.

Why this line is where strong induction pays off: we substituted each a_j — for every j from 2 to k — using the hypothesis. The weak hypothesis would have given only a_k, leaving the other k-2 terms unknown.

Now simplify:

= 1 + (2^0 + 2^1 + \dots + 2^{k-2}) = 1 + (2^{k-1} - 1) = 2^{k-1}.

Why the geometric-sum identity: 2^0 + 2^1 + \dots + 2^{k-2} = 2^{k-1} - 1 is the standard closed form for a sum of powers of 2.

So a_{k+1} = 2^{k-1} = 2^{(k+1) - 2}, which is P(k+1). \checkmark

By strong induction, a_n = 2^{n-2} for all n \geq 2. \square

The step could not be written without the full strong hypothesis. That is the point.

The template

For any recurrence where a_{n+1} depends on a_1, \dots, a_n:

State the claim explicitly. What does P(n) say about a_n?
Pick strong induction. Do not try weak first.
Verify all small cases that the recurrence cannot reach. If the recurrence first applies at n = n_0, verify P(1), \dots, P(n_0) directly.
In the step, substitute each prior a_j using the strong hypothesis, then simplify the resulting expression to match P(k+1).

Step 4 is usually the interesting algebra. Because the recurrence sums or products over all prior terms, the substitution produces a sum or product over formulas, and you need a closed-form identity (geometric series, telescoping, a combinatorial identity) to collapse it.

Greedy picks: $a_{n+1}$ as one more than the max

Claim. Let a_1 = 1 and a_{n+1} = 1 + \max(a_1, a_2, \dots, a_n) for n \geq 1. Prove a_n = n for all n \geq 1.

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

Inductive step. Let k \geq 1. Assume a_j = j for every 1 \leq j \leq k. Then

a_{k+1} = 1 + \max(a_1, a_2, \dots, a_k) = 1 + \max(1, 2, \dots, k) = 1 + k = k + 1.

Why strong induction: computing \max(a_1, \dots, a_k) requires knowing every a_j, not just a_k. The strong hypothesis gives all of them; weak would have given only a_k = k, not enough to evaluate the max.

That is P(k+1). \checkmark

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

The "max of all prior terms" kind of recurrence looks simple but is structurally strong-induction-shaped. The pattern is the same every time.

A compact mental model

When the recurrence reaches back by m steps (fixed window), use strong induction with m base cases.

When the recurrence reaches back by n steps (growing window, i.e., all prior terms), use strong induction with one base case — but the hypothesis covers every prior index, and the inductive step substitutes across all of them.

The difference between "depth 2" and "depth all" is:

Depth 2: two base cases, and in the step, you substitute twice (for a_k and a_{k-1}).
Depth all: one (or a few) base cases, and in the step, you substitute into a sum/product/max over every prior index.

Both flavours need strong induction. The second is more extreme because the strong hypothesis works harder in the step.

Signals in competition problems

Indian olympiad and JEE Advanced problems love this pattern because it tests whether the student recognises structural strong-induction signals. Some watch-outs:

"a_{n+1} equals the sum of the first n terms" — classical sum-over-all-prior recurrence. Answer is usually a geometric or doubling sequence.
"a_{n+1} divides a_1 \cdot a_2 \cdots a_n + 1" — Euclid-style problems about coprimality. Needs strong induction because the hypothesis must control every a_j.
"Every a_{n+1} is at least (or at most) some function of all prior a_j" — optimisation-style problems, extremely common in INMO.
Tree or graph problems. "Every tree on n nodes has exactly n - 1 edges" — splitting a tree into subtrees uses strong induction because the subtrees can have any size \leq n - 1.

The meta-rule: if the inductive step needs to reason about any earlier case, not just the immediate previous one, you want the strong hypothesis.

Quick recognition questions

Ask yourself three things when you meet a recurrence:

Where does the right-hand side of a_{n+1} = \dots pull its inputs from? If the inputs are "all a_j for j \leq n," you need strong induction.
Is there a fixed-depth window (like a_{n-1}, a_{n-2}), or does the window grow with n? Fixed depth means strong induction with a matching count of base cases; growing window means strong induction full stop.
Can I write the step without substituting for some a_j that is not a_k? If no, strong induction is the tool.

Two of those three questions can be answered by glancing at the recurrence's form. You should be able to identify strong-induction problems in seconds.

The one-line takeaway

When the recurrence defining a_{n+1} touches every prior a_j (a sum, product, max, or min over all 1 \leq j \leq n), strong induction is the only viable tool. Weak induction runs into a wall on the first line of the step, because its hypothesis covers only one index. Recognise the "all prior" quantifier in the recurrence and switch to strong induction before you start writing.

This recognition move prevents the most embarrassing failure in induction: writing half a proof with the wrong hypothesis and realising the substitution never lands. Read the recurrence, spot the reach, pick the tool.