Do I Ever Need More Than One Base Case?

Most introductory induction problems have exactly one base case. You prove P(1), then carry out the inductive step P(k) \Rightarrow P(k+1), and you are done. The singular base case fits the machinery perfectly: the step moves forward one rung, so you need one rung set in place at the start.

But some arguments reach further back — the inductive step might need both P(k) and P(k-1) to produce P(k+1). When the step reaches back by two, the induction machine will crash at k = 1 because P(0) was never defined or proved. The fix is simple: prove as many base cases as the reach of your inductive step.

The general rule

If your inductive step deduces P(k+1) from P(k), P(k-1), \dots, P(k-d+1) — that is, it reaches back d rungs — then you need d base cases: P(1), P(2), \dots, P(d).

This is not a stylistic choice. It is a logical necessity. The chain of implications generated by the inductive step only starts producing new truths once you have verified enough consecutive starting values to feed the step. Miss one, and the step has nothing to stand on when it tries to fire.

Why d base cases are exactly right: the inductive step lets you conclude P(k+1) whenever you know P(k), P(k-1), \dots, P(k-d+1). The smallest k for which all of these previous values exist is k = d — because k - d + 1 needs to be at least 1. So the step first produces P(d+1). For the chain to cover P(1), P(2), \dots, P(d) as well, you must verify those by hand. Fewer than d base cases leaves gaps; more than d is redundant.

Example: Fibonacci inequality

Let F_1 = 1, F_2 = 1, and F_{n+2} = F_{n+1} + F_n. Claim: F_n \leq \left(\dfrac{7}{4}\right)^{n-1} for every n \geq 1.

The recursion F_{n+2} = F_{n+1} + F_n reaches back two rungs, so you need two base cases.

Base case 1 (n = 1): F_1 = 1 \leq (7/4)^0 = 1. True.

Base case 2 (n = 2): F_2 = 1 \leq (7/4)^1 = 1.75. True.

Inductive step: assume F_k \leq (7/4)^{k-1} and F_{k-1} \leq (7/4)^{k-2}, for some k \geq 2. Show F_{k+1} \leq (7/4)^k.

F_{k+1} = F_k + F_{k-1} \leq \left(\frac{7}{4}\right)^{k-1} + \left(\frac{7}{4}\right)^{k-2} = \left(\frac{7}{4}\right)^{k-2}\left(\frac{7}{4} + 1\right) = \left(\frac{7}{4}\right)^{k-2} \cdot \frac{11}{4}.

You want this to be at most (7/4)^k = (7/4)^{k-2} \cdot (49/16). Since 11/4 = 44/16 \leq 49/16, done.

Notice: if you had only verified P(1), the first time the step fires is with k = 2, but it then needs F_1 and F_0 — and F_0 is not defined in this formulation. Without P(2) verified separately, the chain never starts correctly.

Example: the chicken-nugget problem

Claim. Every integer n \geq 12 can be written as a non-negative integer combination of 4s and 5s.

The inductive step: given that the claim holds for some k \geq 12, can we deduce it for k + 1? Write k = 4a + 5b. You would like to change that into a representation of k + 1 — but 4a + 5b + 1 is not obviously expressible. So instead, reach back further. Notice that k + 1 = (k - 3) + 4 = (4a' + 5b') + 4, which uses the representation of k - 3. That means the inductive step reaches back 4 rungs, so you need 4 consecutive base cases.

Base cases:

12 = 4 + 4 + 4 = 4 \cdot 3. True.
13 = 4 + 4 + 5. True.
14 = 4 + 5 + 5. True.
15 = 5 + 5 + 5. True.

Inductive step: for k \geq 15, assume the claim holds for k - 3 (which is at least 12, so within the covered range). Then k + 1 = (k - 3) + 4, and the representation of k - 3 extended by one more 4 gives a representation of k + 1.

If you had only verified 12, the step would try to produce 16 from 12, fine, but then 17 from 13 — which you never proved directly. Four base cases are genuinely needed.

Example: tiling problems

Tilings and chessboard problems often involve inductive steps that reach back by several rungs, because the reduction trick removes a block of size 2 or 3 from the figure. If you remove a 2 \times 2 square and invoke the hypothesis on the remaining n - 2 squares, the step reaches back by 2 and you need 2 base cases. If the recursion removes different-sized pieces depending on parity, you might need base cases for n = 1, 2, 3, 4 to cover all combinations of parity and starting configuration.

The rule stays the same: verify enough base cases to cover every starting point the inductive step could land on.

A sanity check you should always run

Before finishing any inductive proof, run this mental check:

Pick the smallest value of k the inductive step is valid for. List every P(j) it needs. For each of those j, is P(j) either a base case I proved directly, or a value the step could have already produced?

If yes, your base cases are sufficient. If no, add the missing ones.

For most problems, the answer is a single base case P(1). But for Fibonacci-style arguments, combinatorial claims about "every integer at least N", and tiling reductions, you will find yourself needing two, three, or more. Missing one is a silent bug that leaves a hole in the proof — the conclusion still looks right, but the logic does not actually cover the gap.

One base case for strong induction is usually enough

With strong induction, the inductive step assumes P(1), P(2), \dots, P(k) — all of the history is available. Because the hypothesis is so generous, you usually only need one base case P(1). The step first fires at k = 1 and produces P(2), and everything above follows automatically.

However, if strong induction is combined with a recursion whose "smallest previous value" is \geq 2, you may still need more base cases. Always check: what is the smallest k for which the step actually produces new information, and are all values below that covered?

The short version

Count how far back your inductive step reaches. Verify exactly that many consecutive base cases, starting from the smallest value in the claim. Missing any one of them is a broken proof, regardless of how clean the inductive step looks.