Recipe

Prove a claim by strong induction

Use when: the inductive step for P(k+1) needs more than P(k) alone, such as splitting k+1 into two smaller, unpredictable pieces, or a recurrence referencing more than one prior term

Goal: a complete proof establishing P(n) for every n at or above n0, using the full strong inductive hypothesis

Taught in Strong induction

1. 1

   Write P(n) out exactly. Identify every value the inductive step cannot yet reach back to, since strong induction sometimes needs more than one base case checked directly.

   Example

   Proving "every amount of postage \ge12 cents is made from 4-cent and 5-cent stamps" needs four base cases checked directly, 12,13,14,15, since removing one stamp from 16 or higher always lands back on one of those four or higher.

   • the inductive step always reaches back to one predictable smaller value — a single base case, at n_0, is enough.
   • the inductive step can land on several different smaller values — check every value from n_0 up through the largest one the step cannot yet reach, directly.

   Why: the inductive step's own reach decides how many base cases are needed; assuming just one, the way ordinary induction does, can leave some small value unconfirmed.

2. 2

   Fix an arbitrary k past the base cases. Assume P(n_0), P(n_0+1), \ldots, P(k) are all true, not just P(k) alone.

   Example

   Assume every integer from 2 through k is a product of primes.

   Why: writing out the full range, not just P(k), is the entire extra reach strong induction adds over the ordinary version.

3. 3

   Show P(k+1) follows from the strong hypothesis, reaching back to whichever specific earlier case the argument actually needs, not necessarily P(k) itself.

   Example

   If k+1 is composite, k+1=ab with 2\le a,b\le k. Both a and b are covered by the strong hypothesis, so each is a product of primes, and k+1=ab combines them into one.

   • k+1 satisfies the property outright, such as being prime itself — note that trivial case separately, then move on.
   • k+1 needs the property of a specific smaller value, not k — cite that value's case by name from the strong hypothesis.

   Why: the strong hypothesis only pays off once the step reaches for a case other than k; using only P(k) here is correct but unnecessarily narrow.

4. 4

   State that since every base case holds, and the inductive step holds for an arbitrary k, P(n) is true for every n\ge n_0, by the principle of strong induction.

   Why: the conclusion covers every n at once, the same way it does for ordinary induction, once both obligations are verified.