STRONG
MATHEMATICAL INDUCTION:
Almost similar to
ordinary mathematical induction, however in strong mathematical induction, the
basis step may contain proofs for several initial values, and in inductive step
the truth of the predicate P(n) is assumed and not just for one value of n but
for all from a through k and then the truth of P(k+1) is proved.
Principle of
Strong Mathematical Induction:
Let P(n) be a
property that is defined for integer n, and let a and b be fixed integer with a≤b.
Suppose the following
2 statements are true:
①
P(a),
P(a+1), … and P(b) are all tue (BASIS)
②
For any
integer k≥b, if P(i) is true for all int I from a
through k, then P(k+1) is true. (INDUCTIVE STEP)
Then, the statement “for all integer n≥a, P(n) is true.”
(The supposition that P(i) is true for all
integer i from a through k is called the inductive hypothesis.)
(Another way to state the inductive
hypothesis is to say that P(a), P(a+1),…, P(k) are all true)
Note: Any statement that can be proved by ordinary
mathematical induction can be proved by strong induction too.
