Here is a silent bug that kills induction proofs. A student writes:

The proof looks clean. But it is wrong. The inductive step is only valid for k \geq 5, so the chain from P(1) to P(2) is broken — the step cannot fire until k = 5. The base case at n = 1 does not connect to the inductive step at k \geq 5; there is a gap from n = 1 to n = 5 where neither the base case nor the inductive step covers the statement.

The fix: make the base case index match the inductive step's threshold. If the step works from k \geq 5 onward, the base case must be at n = 5 (or you must verify n = 1, 2, 3, 4, 5 individually).

This article explains the rule, how to detect the threshold, and what goes wrong when the indices do not match.

The rule

The base case index n_0 must equal the smallest value of k for which your inductive step is valid.

Not "approximately equal." Not "close enough." Exactly equal. If your step uses an algebraic inequality that fails at k = 4 and first holds at k = 5, then your base case must start at n = 5.

Why exactly equal? Because induction propagates from P(n_0) forward using the step. The step carries you from P(k) to P(k+1) for every k \geq n_0. If the step is only valid for k \geq 5, it cannot carry you from P(1) to P(2) — the step breaks there. So starting at P(1) and claiming to reach P(6) is a logical error: the chain has gaps.

A concrete failure mode

Consider this broken proof.

Claim. 3^n \geq n^3 for all n \geq 1.

Broken attempt.

Base case. n = 1: 3 \geq 1. \checkmark

Inductive step. Assume 3^k \geq k^3. Then 3^{k+1} = 3 \cdot 3^k \geq 3 k^3. We need 3 k^3 \geq (k+1)^3 = k^3 + 3k^2 + 3k + 1, which simplifies to 2 k^3 \geq 3k^2 + 3k + 1.

At k = 1: 2 \geq 7? No. Broken. At k = 2: 16 \geq 19? No. Broken. At k = 3: 54 \geq 37? Yes.

So the inductive step fails for k = 1, 2 and starts working at k = 3.

What actually happens: the base case P(1) is true. But the step cannot fire at k = 1 (the algebra breaks). So P(2) is not established. The chain is broken at the very first link.

Also, the claim itself is false at n = 2: 3^2 = 9 and 2^3 = 8, so 9 \geq 8 holds... but at n = 3: 3^3 = 27 and 3^3 = 27, so 27 \geq 27 holds (with equality). What about larger n? At n = 4: 81 \geq 64, yes. The claim actually is true for all n \geq 1 in this case, but the proof is broken — the inductive step does not establish it for n \geq 2.

Repaired proof.

Base cases. n = 1, 2, 3: check directly.

Inductive step. For k \geq 3: assume 3^k \geq k^3. Then 3^{k+1} \geq 3 k^3 \geq (k+1)^3 using 2 k^3 \geq 3k^2 + 3k + 1 (valid for k \geq 3).

By induction, 3^n \geq n^3 for all n \geq 1. (The base case n = 3 combined with the inductive step from k \geq 3 covers n \geq 3. The cases n = 1, 2 were verified directly.)

The fix was: verify the small cases that the step cannot reach, and set the inductive step to work from the smallest index where it is algebraically valid. The step works from k \geq 3; verify n = 1, 2, 3 directly; everything past n = 3 is covered by the step.

How to detect the threshold in your inductive step

During the inductive step, you will often derive an inequality like "it suffices to show f(k) \geq 0" or "we need g(k) \geq h(k)." This inequality is a function of k, and it may or may not hold for all k \geq 1. The threshold is the smallest k for which it does hold.

To find the threshold:

  1. Identify the residual inequality in your step — the algebraic fact about k that you used.
  2. Test it at small values of k: k = 1, 2, 3, \dots until it holds.
  3. The smallest k at which it holds is your threshold. Your base case must start there (or you verify all smaller values directly).

This is a mechanical process. You do not need to solve the inequality exactly — just test it at k = 1, 2, 3, 4, 5 and find the cutoff.

A visual: chain breakage when indices do not match

The inductive step is invalid for $k = 1, 2, 3, 4$ (red dashed arrows) and first valid at $k = 5$ (green arrows). Drag the base case. If you set it at $n = 1$, even a true $P(1)$ cannot propagate to $P(2)$ because the step breaks. The base case must be at $n = 5$ (or $n = 1, 2, 3, 4, 5$ all verified directly) for the chain to be unbroken.

Two equally valid repairs

When you discover the threshold mismatch, you have two repair strategies.

Repair 1: raise the base case.

Set n_0 to the threshold. Verify P(n_0) directly, run the inductive step from k \geq n_0, and conclude "P(n) for all n \geq n_0." This is the minimum-effort fix.

Use this when: the original claim is false (or uninteresting) below the threshold, or when you only care about large n.

Repair 2: verify multiple base cases.

Verify P(1), P(2), \dots, P(n_0) all directly. Run the inductive step from k \geq n_0 (or from whatever threshold applies). Conclude "P(n) for all n \geq 1" — provided every missing case is verified.

Use this when: the claim really is true from n = 1 onward, and you need to establish it for small n too.

Both are logically valid. The first is more honest about what the proof establishes; the second matches the original claim but requires more direct work on small cases.

Why this rule is a common pitfall

Students learn induction with sum formulas (1 + 2 + \dots + n = \frac{n(n+1)}{2}), where the inductive step works mechanically for all k \geq 1 — the algebra never requires an auxiliary bound like "k^2 \geq 5." This trains an unconscious habit: "base case is n = 1, always."

Then the student meets an inequality or a more sophisticated claim, and the step secretly requires a bound that fails for small k. The student does not notice the bound, sets the base case to n = 1 as usual, and writes a proof that looks complete but has a hidden gap.

The defence is to audit your inductive step. Every time you use an inequality on k, check whether it holds for k = n_0. If not, you have a threshold mismatch.

Why the threshold is easy to miss: residual inequalities often come up in the middle of a chain of algebra, looking like "...and since k^2 \geq 2k + 3, we are done." The student writes "\checkmark" without noticing this is an inequality that requires k to be large enough. One extra line — "k^2 \geq 2k + 3 holds for k \geq 5 but fails for k = 1, 2, 3, 4" — catches the bug.

When the base case index is not obvious from the problem

Some problems state "prove for all n \geq 1" but secretly need a larger threshold. Other problems state "prove for all n \geq 5" — the threshold is given. Always check the claim's quantifier and match your base case to it.

If the problem says "for all n \geq 1": you must establish every n \geq 1, including small cases. If your inductive step only works for k \geq 5, use Repair 2 — verify n = 1, 2, 3, 4, 5 directly.

If the problem says "for all n \geq 5": your base case is n = 5, and you only need the step to work for k \geq 5. Use Repair 1.

If the problem lets you choose the threshold: pick the threshold that matches your inductive step, state the claim at that threshold, and verify the single base case. Cleanest.

Finding the threshold in a JEE-style problem

Problem. For what integers n is n! \geq 2^n? Prove your claim by induction.

Investigate.

  • n = 1: 1 \geq 2? No.
  • n = 2: 2 \geq 4? No.
  • n = 3: 6 \geq 8? No.
  • n = 4: 24 \geq 16? Yes.
  • n = 5: 120 \geq 32? Yes.

So the claim first holds at n = 4. Set the threshold to n = 4.

Claim. n! \geq 2^n for all n \geq 4.

Base case. n = 4: 24 \geq 16. \checkmark

Inductive step. Assume k! \geq 2^k for some k \geq 4. Then

(k+1)! = (k+1) \cdot k! \geq (k+1) \cdot 2^k \geq 2 \cdot 2^k = 2^{k+1},

where the last step uses k + 1 \geq 2, which holds for k \geq 1 (hence for k \geq 4).

Audit the step. The residual inequality is k + 1 \geq 2, valid for k \geq 1. Our base case threshold is n = 4 \geq 1, so the step is valid for all k \geq 4. The indices match. \checkmark

By induction, n! \geq 2^n for all n \geq 4.

Lesson. The threshold n \geq 4 is dictated by the claim itself (it fails for smaller n). The inductive step's residual inequality happens to hold from k = 1, but we only need it from k = 4. Because 4 \geq 1, the step is valid throughout the range we care about, and the indices match.

Contrast this with 2^n > n^2: there, the claim happens to be true at n = 1, but the inductive step only works from k = 3. That mismatch is what forces either a bumped base case or multiple direct verifications.

The one-line takeaway

The base case index must equal the smallest k for which the inductive step is valid. Always audit the inequalities you use in the step; if one fails at small k, either raise the base case to match or verify the small cases directly. A base case at n = 1 with a step that only works for k \geq 5 is a broken chain, regardless of how the surrounding algebra looks.

This is the single most common silent bug in induction proofs. Build the audit habit — check every inequality in your step against the base case index — and the bug disappears.

Related: Mathematical Induction · Recognition: Inequality Induction Proofs Need the Hypothesis Plus One Extra Inequality — Plan for the Gap · Base Case Index Slider — Watch the Proved Set Shrink From n ≥ 1 to n ≥ 5 · Missing Base Case — The Domino Chain That Never Starts · Skipping the Base Case Because It's 'Obvious'