Some proofs require hunting for the right technique. Others broadcast the technique the moment you read them. When you see a statement indexed by a natural number n that has a recursive flavour — a sum, a product, a sequence, a quantity that is built from the previous one — induction is almost always the right first move. Not because it is the only tool, but because the structure of the problem matches the structure of the proof technique so closely that reaching for anything else is wasted effort.

This article explains the recognition signal, why it fires so reliably for this class of problems, and when to override the default.

The signal in one line

If the statement has an n in it, and the object at step n is defined in terms of the object at step n-1 (explicitly or implicitly), try induction first.

The two features that fire the signal together:

  1. Indexed by \mathbb{N} — the statement says "for all n \geq 1" or "for all positive integers n" or "for every natural number n."
  2. Recursive flavour — the object at step n can be described as "the object at step n-1, plus something" or "the object at step n-1, times something." Sums, products, sequences, factorials, Fibonacci-style recurrences, repeated applications of an operation — all count.

When both features are present, induction is the default.

Three canonical recognitions

Example 1: sums. "Prove that 1 + 2 + \dots + n = \frac{n(n+1)}{2} for all n \geq 1."

Example 2: products. "Prove that \prod_{k=1}^{n} (1 + \tfrac{1}{k}) = n + 1 for all n \geq 1."

Example 3: sequences. "Let a_1 = 1, a_{n+1} = 2 a_n + 1. Prove a_n = 2^n - 1 for all n \geq 1."

In each case, the moment you read the problem the shape of the proof is dictated: verify the base case, assume P(k), derive P(k+1) using the recursive relationship. You do not have to invent the structure; the problem hands it to you.

Why the signal is so reliable

The deep reason is that the axiom of induction matches the structure of recursion exactly.

Induction says: if P(1) holds and P(k) \Rightarrow P(k+1) for all k \geq 1, then P(n) holds for all n \geq 1.

A recursive statement has exactly this shape. The object at step n is built from the object at step n-1. If you can verify:

then the claim holds for every step. The proof technique is not coincidentally matching the problem structure — it is designed for this kind of problem. That is why the signal is so reliable.

Why induction is literally "made for" recursion: Peano's axioms define the natural numbers as precisely the set generated by starting at 0 and repeatedly applying the successor function. Induction is the proof principle that corresponds to this generative process — if a property holds at the start and survives the successor step, it holds throughout. Recursive definitions generate objects by the same mechanism. So induction and recursion are two faces of the same structure.

A visual cue you can internalise

Recognition signal toggle — indexed by n with recursive flavour triggers inductionA two-panel diagram. The left panel shows a problem statement indexed by n with recursive flavour, with a green "induction signal" indicator. The right panel shows a problem that is indexed by a real number r or has no recursive flavour, with a red "no induction signal" indicator. A slider toggles between the two views. indexed-by-n, recursive not-indexed-by-n
Toggle between a problem where the recognition signal fires (left) and one where it does not (right). The signal requires *both* features: natural-number indexing AND recursive structure. If either is missing, induction is not the default tool.

The signal's two failure modes

Failure mode 1: indexed by n but no recursion.

"Prove that n^2 + 3n + 2 factors as (n+1)(n+2) for all n."

Indexed by n, but this is a statement about a single polynomial identity. There is no recursion — the object at n is not built from the object at n-1. Direct algebra handles it in one line: (n+1)(n+2) = n^2 + 3n + 2. Induction would work mechanically but would be overkill; the statement is already a pure identity.

Failure mode 2: recursive but not indexed by n.

"Define a sequence of real numbers x_{n+1} = \cos(x_n). Prove that x_n converges as n \to \infty."

Recursive in n, yes. But the claim is about a limit — not about a property that can be stated at each finite n. Induction can prove statements that hold at every n, but a limit statement requires analysis tools (monotone convergence, contraction mapping). Induction alone does not reach the limit.

When either of these modes applies, the signal does not fire, and induction is not the default.

What to do when the signal fires

Follow the induction template mechanically:

  1. Identify P(n). Write the statement you need to prove, as a clean predicate in n.
  2. Verify the base case. Usually n = 1, but sometimes n = 0 or n = n_0 for some larger threshold (see Match Base Case to Inductive Step Threshold for when).
  3. Write the inductive hypothesis. Assume P(k) for some k \geq n_0.
  4. Derive P(k+1). Use the recursive relationship — the fact that the object at step k+1 is built from the object at step k — to transport the hypothesis across the step. Write P(k+1) explicitly on a fresh line before manipulating (see Write P(k+1) Explicitly Before Manipulating).
  5. Conclude. By induction, P(n) for all n \geq n_0.

The recursive flavour fuels step 4 specifically: the transition from P(k) to P(k+1) is exactly the recursive relationship the problem gave you.

When to override the default

Even when the signal fires, other techniques sometimes give cleaner proofs. For sums and identities, direct algebraic tricks or telescoping can be shorter. For combinatorial identities, bijective proofs are often more insightful. The signal says "try induction first" — not "induction is the only option." If you see a slicker path, take it. But if you do not, induction always works when the signal is present.

Applying the signal to a JEE-style problem

Problem. Prove that 1^3 + 2^3 + \dots + n^3 = \left( \frac{n(n+1)}{2} \right)^2 for all n \geq 1.

Step 1: check the signal.

  • Indexed by n ("for all n \geq 1"). Yes.
  • Recursive flavour. Yes — the sum up to n is the sum up to n-1 plus n^3.

Signal fires. Induction is the default.

Step 2: run the template.

Base case: n = 1. LHS = 1^3 = 1. RHS = \left( \frac{1 \cdot 2}{2} \right)^2 = 1. Match.

Inductive hypothesis: assume 1^3 + 2^3 + \dots + k^3 = \left( \frac{k(k+1)}{2} \right)^2 for some k \geq 1.

Inductive step: show 1^3 + 2^3 + \dots + k^3 + (k+1)^3 = \left( \frac{(k+1)(k+2)}{2} \right)^2.

1^3 + \dots + k^3 + (k+1)^3 = \left( \frac{k(k+1)}{2} \right)^2 + (k+1)^3 \quad \text{(by hypothesis)}
= \frac{k^2 (k+1)^2}{4} + (k+1)^3 = \frac{(k+1)^2 [k^2 + 4(k+1)]}{4} = \frac{(k+1)^2 (k+2)^2}{4} = \left( \frac{(k+1)(k+2)}{2} \right)^2. \quad \checkmark

By induction, the claim holds for all n \geq 1.

Lesson. Because both features of the signal were present, the proof strategy was fixed from the moment the problem was read. No hunting, no back-tracking — just run the template.

The one-line takeaway

When the statement is indexed by a natural number n and the object at step n is built from the object at step n-1, induction is the default. Run the template; do not search for a cleverer path until the default is exhausted.

This is one of the most reliable recognition signals in proof-strategy selection. Internalise it, and an entire class of problems becomes mechanical.

Related: Mathematical Induction · Write P(k+1) Explicitly Before Manipulating · Match Base Case to Inductive Step Threshold · Can I Prove a Formula I Guessed Without Using Induction? · Induction Ladder — Climb From P(k) to P(k+1), One Rung at a Time