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 has a prime factorization (1 = 1).
Strong inductive step:
- Assume that for some positive k−1, every positive integer 1 through k−1 has a prime factorization.
-
There are two possible cases for k:
- k is prime
Then k has a prime factorization k = k.
- k is not prime
- Then k is the product of two positive integers i and j.
- i<k, so P(i) (i has a prime factorization).
- j<k, so P(j) (j has a prime factorization).
- Then k has a prime factorization, which is the product of i's prime factorization and j's prime factorization.
- k is prime
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.)
- 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.
- D is not empty — it at least contains the element D − 0d, which is nn (because D is).
-
For any d,
there is a minimum element
rd = D − qdr
because of the well-ordering property.
-
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).
- thomas · alspaugh @ acm · org
-
-
Attribution