Thomas A. Alspaugh
Strong Induction

Strong induction is like mathematical induction, but its inductive step's antecedent is that P is true not just for n, but for every integer n and earlier.

It's called strong induction because that antecedent is stronger than the one for mathematical induction.

Strong induction is equivalent to the Well-Ordering Property of the integers, which states that

Every non-empty subset of the positive integers has a least element.

Strong induction may be used for any well-ordered set, not just the positive integers.

Every positive integer n has a prime factorization.

Basis step:

  1. 1 has a prime factorization (1 = 1).

Strong inductive step:

  1. Assume that for some positive k−1, every positive integer 1 through k−1 has a prime factorization.
  2. There are two possible cases for k:
    1. k is prime

      Then k has a prime factorization k = k.

    2. k is not prime
      1. Then k is the product of two positive integers i and j.
      2. i<k, so P(i) (i has a prime factorization).
      3. j<k, so P(j) (j has a prime factorization).
      4. Then k has a prime factorization, which is the product of i's prime factorization and j's prime factorization.

A quotient and remainder exist for every integer divisor and dividend.

Prove: For every positive integer D (the dividend) and d (the divisor), there exists a positive integer quotient q and remainder r, such that

r < d


D = dq + r

(q is the quotient ⎣ D/d ⎦, and r is the remainder D%d, for the integer division D÷d.)

  1. Consider the set SD of non-negative (nn) integers r = D − qd, where D is a specific nn integer d is any positive integer, and q is any nn integer.
  2. D is not empty — it at least contains the element D − 0d, which is nn (because D is).
  3. For any d, there is a minimum element

    rd = D − qdr

    because of the well-ordering property.

  4. rd < dr , because otherwise there would be another element of SD


    that is still nn (because dr would be less than rd and thus r′d would still be nn and therefore a member of SD).

flip bgunflip