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 next integerin 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:
Strong inductive step:
Then k has a prime factorization k = k.
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.)
r_{d} = D − qd_{r}
because of the well-ordering property.
r′_{d}=D−q(d_{r}+1)
that is still nn (because d_{r} would be less than r_{d} and thus r′_{d} would still be nn and therefore a member of S_{D}).