Proofs and induction · Definition

Strong induction

discrete mathematicsproofs

Before you start you need to know

It is used when case \(k+1\) does not depend only on the previous one, but on one or several older cases.

Definition

Strong induction proves \(P(n)\) for every \(n\ge n_0\): after checking the base case \(P(n_0)\), one proves \(P(k+1)\) assuming \(P(j)\) for all \(j\) with \(n_0\le j\le k\).

\[\big[P(n_0)\wedge\forall k\ge n_0\,(P(n_0)\wedge\cdots\wedge P(k)\Rightarrow P(k+1))\big]\Rightarrow\forall n\ge n_0\,P(n)\]

In ordinary induction the hypothesis is only \(P(k)\). That is often too little: to factor \(k+1=ab\) one needs the factors \(a\) and \(b\), which may be far from \(k\); for a recurrence such as \(F_{k+1}=F_k+F_{k-1}\) two earlier terms are needed. Strong induction gives the whole history: \(P(j)\) is assumed for every \(j\) between \(n_0\) and \(k\).

It is not a more powerful method, only a more convenient one: if \(Q(n)\) is defined as «\(P(j)\) holds for every \(j\) between \(n_0\) and \(n\)», proving \(Q\) by ordinary induction is the same as strong induction on \(P\). That is why both principles are equivalent to the well-ordering of the integers.

The delicate part is the base cases. If the step uses values up to \(m\) places back, the first \(m\) cases must be checked by hand. In the stamp problem with \(4\)- and \(5\)-cent stamps, the step from \(n-4\) to \(n\) only works from \(n=16\), and the cases \(12,13,14,15\) are checked separately. Forgetting one leaves the chain broken.

Other classic applications are the existence of prime factorizations, closed forms for sequences defined by two-term recurrences and the binary representation of every positive integer.

Think about it

Why is ordinary induction not enough for prime factorization?

Because if \(k+1=ab\), the factors \(a\) and \(b\) are smaller than \(k+1\) but rarely equal to \(k\); \(P\) is needed for all smaller values.

A formula for \(a_n=a_{n-1}+a_{n-2}\) is proved by checking only \(a_1\). What is missing?

The case \(a_2\): the step uses two earlier terms and cannot apply until \(n=3\).

Exercises 10

  1. In the step of a strong induction proving \(P(k+1)\), the hypothesis is:
  2. An inductive step proves \(P(k+1)\) using \(P(k)\) and \(P(k-1)\). At least how many base cases are needed?
  3. With \(F_1=F_2=1\) and \(F_n=F_{n-1}+F_{n-2}\), what is \(F_{10}\)?
  4. To prove that every integer \(n\ge2\) is a product of primes, if \(k+1=ab\) with \(2\le a,b\le k\), which hypothesis is used?
  5. Compared with ordinary mathematical induction, strong induction:
  6. Let \(a_1=1\), \(a_2=2\) and \(a_n=a_{n-1}+a_{n-2}\). What is \(a_8\)?
  7. With stamps of \(4\) and \(5\) cents, what is the least \(n_0\) such that every amount \(n\ge n_0\) can be made?
  8. Let \(a_0=0\), \(a_1=1\) and \(a_n=3a_{n-1}-2a_{n-2}\). It is proved by strong induction that \(a_n=2^n-1\). What is \(a_5\)?
  9. It is proved that every amount \(n\ge12\) can be made with stamps of \(4\) and \(5\), going from \(n-4\) to \(n\). How many base cases must be checked?
  10. To prove every \(n\ge1\) is a sum of distinct powers of \(2\), if \(n+1\) is even, what is used?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §5.2
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §5.4
  • László Lovász, József Pelikán, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyond, 1st edition, Springer, 2003. Cap. 1