A common question after learning induction: "Which induction do I use — weak or strong?" Students sometimes guess randomly, sometimes use strong induction defensively because it "never hurts." Both habits waste time. There is a clear recognition signal that tells you which variant to start with, and it is visible the moment you read the problem statement.

If the problem is "prove for all n \geq 1" and n appears on both sides of an equation or inequality, weak induction is the default. Reach for strong induction only when the recursive structure explicitly looks back more than one step.

This article explains the signal, contrasts weak and strong induction, and shows what to look for when the signal does not fire.

Weak vs strong induction, in one sentence each

Weak induction. To prove P(n) for all n \geq n_0: verify P(n_0), then show P(k) \Rightarrow P(k+1) for all k \geq n_0.

Strong induction. To prove P(n) for all n \geq n_0: verify P(n_0), then show [P(n_0) \land P(n_0 + 1) \land \dots \land P(k)] \Rightarrow P(k+1) for all k \geq n_0.

Weak induction uses only the previous step. Strong induction uses all previous steps. The two are logically equivalent (either one implies the other), but they are not equally convenient — some proofs go through cleanly with weak induction, some need strong.

The signal

The phrase "prove for all n \geq 1" plus "n on both sides of an equation" is the weak-induction fingerprint. When both are present, the inductive step is almost always "take what holds at k, do one algebraic manipulation, get what you want at k+1" — which is exactly what weak induction provides.

Canonical examples.

In each case, the inductive step is a mechanical one-step propagation: substitute the hypothesis into the k+1 case and simplify.

Why weak induction suffices here

Look at the shape of the inductive step for these problems. Starting from

1 + 2 + \dots + k = \frac{k(k+1)}{2} \quad \text{(hypothesis)}

the (k+1) case is

1 + 2 + \dots + k + (k+1) = \underbrace{1 + 2 + \dots + k}_{\text{hypothesis}} + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}.

Notice what happened: the (k+1)-step expression splits naturally into "the k-step expression" plus "one new term." The inductive hypothesis fills in for the k-step expression. You never needed P(k-1), P(k-2), or any earlier step — just P(k).

Whenever the recursive structure is "new term at step n is built on top of step n-1," weak induction is sufficient. You need only the immediately previous case.

This is why the signal fires for sums, products, simple inequalities, and most identities: their recursive structure is one-step-back, and one-step-back is exactly what weak induction handles.

When the signal does not fire — reach for strong induction

Two features indicate strong induction is needed.

Feature 1: recurrence looks back more than one step.

"Define F_1 = 1, F_2 = 1, F_{n+2} = F_{n+1} + F_n (Fibonacci). Prove F_n < 2^n for all n \geq 1."

Here F_{n+2} depends on both F_{n+1} and F_n. The inductive step at k+2 needs both P(k+1) and P(k). Weak induction (using only P(k+1)) would leave F_k unaccounted for. Strong induction — "assume P(j) for all j \leq k" — covers both cases at once.

Feature 2: case analysis that splits n into smaller parts of varying size.

"Prove that every integer n \geq 2 can be written as a product of primes."

If n is prime, done. If n = ab with 1 < a, b < n, you need to know the claim holds for both a and b — and a, b can be any integers less than n, not just n-1. Strong induction — "assume the claim for all integers in [2, n-1]" — handles the case cleanly. Weak induction would be insufficient because a and b might not equal n-1 specifically.

Feature 3: proofs that split the problem into recursively smaller pieces of unknown sizes.

This is common in combinatorics and graph theory. If you want to prove a property of a graph by removing a vertex and applying the hypothesis to the smaller graph, the smaller graph could be of any size — not just "one less." Strong induction lets you apply the hypothesis to every smaller size simultaneously.

For more on the weak/strong distinction and when each applies, see When Do I Need Strong Induction vs Weak Induction?.

A visual contrast

Weak vs strong induction — which dependencies are requiredA diagram showing two modes of induction. The left mode (weak induction) shows the (k+1) case drawing from only the k case, with a single arrow. The right mode (strong induction) shows the (k+1) case drawing from every previous case, with multiple arrows. A slider toggles between the two views. P(1) P(2) P(k) P(k+1) weak strong
Toggle between the two modes. Weak induction propagates $P(k+1)$ from $P(k)$ alone — a single dependency arrow. Strong induction draws from every previous case. For most sum / product / inequality problems, only one arrow is needed, so weak induction suffices.

The safety question: does strong induction "always work"?

Strong induction is logically at least as powerful as weak induction, so you can use it for any problem — including ones where weak would suffice. Why bother distinguishing?

Reason 1: clarity. A proof by weak induction reads "assume P(k), derive P(k+1)" — a single line of setup. Strong induction reads "assume P(j) for all j \leq k, derive P(k+1)" — and you then have to tell the reader which previous cases you actually used. If you only used one (namely P(k)), you have introduced machinery you did not need. Readers are left wondering which hypothesis matters.

Reason 2: habit formation. Students who reach for strong induction by default sometimes assemble proofs where they use "by strong induction" in the statement but only apply P(k) in the step. This is not wrong, but it is signalling something about your understanding: you have not internalised which induction is needed when.

Reason 3: efficiency in thought. When the signal fires ("n on both sides, one-step recursion"), weak induction is shorter, both to write and to read. Matching technique to problem is part of good mathematical taste.

Why strong induction is never "wrong" but is often "too much": strong induction is logically equivalent to weak induction over the natural numbers. So any proof by weak induction can be rewritten as a proof by strong induction. But the "strong" version uses hypotheses it does not need, which obscures the proof's dependency structure. Matching the induction variant to the problem's actual dependency pattern is a form of proof hygiene.

Choosing the variant for a JEE-style problem

Problem A. Prove \sum_{i=1}^{n} (2i - 1) = n^2 for all n \geq 1.

Signal check: "for all n \geq 1," n on both sides (sum index and RHS). Signal fires. Use weak induction.

Base: n = 1: LHS = 1, RHS = 1. \checkmark

Step: assume \sum_{i=1}^{k} (2i - 1) = k^2. Then

\sum_{i=1}^{k+1} (2i - 1) = k^2 + (2(k+1) - 1) = k^2 + 2k + 1 = (k+1)^2. \quad \checkmark

Done with weak induction. The inductive step used only P(k).

Problem B. Let a_1 = 1, a_2 = 3, a_{n+2} = 5 a_{n+1} - 6 a_n. Prove a_n = 3^n - 2^n for all n \geq 1.

Signal check: "for all n \geq 1" — yes. But the recurrence a_{n+2} = 5 a_{n+1} - 6 a_n looks back two steps, not one. Signal does NOT fire for weak. Use strong induction (or at least two-step induction).

Base: verify n = 1, 2 directly. a_1 = 1 = 3 - 2. a_2 = 3 = 9 - 6. \checkmark

Step: assume a_j = 3^j - 2^j for all j \leq k+1. Then

a_{k+2} = 5 a_{k+1} - 6 a_k = 5(3^{k+1} - 2^{k+1}) - 6(3^k - 2^k) = 3^{k+1}(5) - 3^k(6) - 2^{k+1}(5) + 2^k(6)
= 3^k(15 - 6) - 2^k(10 - 6) = 3^k \cdot 9 - 2^k \cdot 4 = 3^{k+2} - 2^{k+2}. \quad \checkmark

The step used both P(k) and P(k+1), so strong induction is required.

Lesson. Same phrase "prove for all n \geq 1," but the recurrence structure differs. Problem A's signal fires for weak induction. Problem B's recurrence looks back two steps, so the signal does not fire and strong induction is the right tool.

The one-line takeaway

"Prove for all n \geq 1" plus "n on both sides of an equation" plus "one-step recursive structure" equals weak induction. If the recursion looks back more than one step, or the problem splits into pieces of varying size, use strong induction instead.

Match the variant to the shape of the recursion. Do not over-arm with strong induction when weak induction is all the problem needs.

Related: Mathematical Induction · When Do I Need Strong Induction vs Weak Induction? · Strong Induction as a Jenga Tower — Each Block Rests on Many Below · Recognition Signal: Statements Indexed by n With a Recursive Flavour Are Induction by Default