• Home
• Foundations
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.

• The basis step, in which a proposition P is proved about some specific integer (same as for mathematical induction), and
• the induction step, in which it is proved that if P is true for every integer from the basis case to n, then P is also true for the next integer in the sequence (usually n+1, but sometimes it's n+2 or 2n or something similar).

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

and

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

r′d=D−q(dr+1)

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).