Discrete Math · Undergraduate

Strong Induction and the Well-Ordering Principle

Quick answer

Ordinary induction assumes one case, P(k), to prove the next. Strong induction assumes every case from the start up to k. That extra strength is what you need when a case leans on values further back: factoring a number into primes uses its factors, and the Fibonacci recurrence uses the two previous terms. A step that reaches back several places needs that many base cases. Strong induction matches the well-ordering principle: every nonempty set of positive integers has a least element.

What you'll learn

  • State the principle of strong induction
  • Decide how many base cases a proof needs
  • Prove results about prime factorizations, postage and recurrences
  • Connect strong induction with the well-ordering principle

Assuming everything so far

Ordinary induction proves P(k+1)P(k + 1) from P(k)P(k) alone. Sometimes the next case depends on an earlier one instead. Strong induction lets you assume all of them:

  1. Base cases. Prove P(n0)P(n_0), and as many following cases as the step needs.
  2. Step. Assume P(n0),P(n0+1),…,P(k)P(n_0), P(n_0 + 1), \ldots, P(k) are all true, and prove P(k+1)P(k + 1).

Then P(n)P(n) holds for every n≥n0n \ge n_0.

Why the extra assumption is allowed

Imagine the cases as dominoes. In ordinary induction each domino knocks over the next. In strong induction, by the time domino k+1k + 1 is reached, every earlier domino has already fallen, so leaning on any of them is fair. Nothing new is being assumed; strong induction only admits that the earlier cases were proved too. Equivalently, if some P(n)P(n) failed, there would be a smallest failure by the well-ordering principle, and the step would show that smallest failure is not one: a contradiction.

Worked examples

Common mistakes

Practice problems

  1. Prove that every amount of 88 cents or more can be paid with 33- and 55-cent stamps. Which base cases are needed?

    Answer

    88, 99 and 1010

    Full solution

    8=3+58 = 3 + 5, 9=3+3+39 = 3 + 3 + 3, 10=5+510 = 5 + 5. The step adds a 33-cent stamp to k−2k - 2, which reaches back 33 places.

  2. Which amounts cannot be paid with 44- and 55-cent stamps?

    Answer

    1,2,3,6,7,111, 2, 3, 6, 7, 11

    Full solution

    Every amount from 1212 on works, by Example 2; checking the smaller amounts by hand leaves these six.

  3. With a1=1a_1 = 1, a2=3a_2 = 3 and an=an−1+2an−2a_n = a_{n-1} + 2a_{n-2}, find a3a_3, a4a_4 and a5a_5.

    Answer

    55, 1111, 2121

    Full solution

    3+2=53 + 2 = 5, 5+6=115 + 6 = 11, 11+10=2111 + 10 = 21.

  4. Prove that the sequence in Exercise 3 satisfies an=2n+1+(−1)n3a_n = \tfrac{2^{n+1} + (-1)^n}{3}.

    Answer

    Check n=1,2n = 1, 2, then substitute the formula for aka_k and ak−1a_{k-1}.

    Full solution

    ak+2ak−1=2k+1+(−1)k+2k+1+2(−1)k−13=2k+2+(−1)k+13a_k + 2a_{k-1} = \tfrac{2^{k+1} + (-1)^k + 2^{k+1} + 2(-1)^{k-1}}{3} = \tfrac{2^{k+2} + (-1)^{k+1}}{3}.

  5. A chocolate bar has nn squares. Each break splits one piece into two. Prove it takes n−1n - 1 breaks to separate all squares.

    Answer

    After the first break into pieces of aa and bb squares, they need (a−1)+(b−1)(a - 1) + (b - 1) more.

    Full solution

    Base: n=1n = 1 needs 00 breaks. Step: 1+(a−1)+(b−1)=a+b−1=n−11 + (a - 1) + (b - 1) = a + b - 1 = n - 1, using the assumption for a,b<na, b < n.

  6. How many base cases does a proof need if its step uses P(k)P(k) and P(k−2)P(k - 2)?

    Answer

    33

    Full solution

    The step for k+1k + 1 uses P(k−2)P(k - 2), three places back, so the first three cases must be checked directly.

  7. Use well-ordering to explain why there is no smallest positive rational number.

    Answer

    Well-ordering applies to integers only; for any positive rational rr, r2\tfrac{r}{2} is smaller.

    Full solution

    The positive rationals are not well-ordered, which is why induction is a tool for integers.

  8. A student proves Fn<2nF_n < 2^n checking only F1<2F_1 < 2. What is wrong?

    Answer

    The step uses two earlier terms, so F2<4F_2 < 4 must be checked too.

    Full solution

    For k+1=2k + 1 = 2, the step would need F0F_0, which is outside the proof’s range.

Frequently asked questions

What is strong induction?

To prove P(n) for all n ≥ n₀: prove the base case(s), then show that if P(n₀), …, P(k) are all true, P(k + 1) is true.

When do you need strong induction?

When proving P(k + 1) needs a case other than P(k), such as P(k − 1), P(k − 3) or P(a) for a factor a of k + 1.

How many base cases are needed?

Enough that the step never reaches below them. If the step uses P(k − 3), the first four cases must be checked directly.

Is strong induction stronger than ordinary induction?

No. Each can be derived from the other; strong induction is ordinary induction applied to 'P holds for every case up to n'.

What is the well-ordering principle?

Every nonempty set of positive integers has a smallest element. Proofs by smallest counterexample use it.

What to learn next