Chap 3: Mathematical Induction (II)

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.

DIVISIBILITY BY A PRIME

Prove that for any integer n≥2, n is divisible by a prime.

Solution:

Let P(n) = n is divisible by a prime, any integer n≥2

Basis      : Prove that P(2) is valid for the statement

P(2) =2/2

    = 1 (divisible)

2 is a prime number

Hence, the statement is true

Inductive  : Show that for all integers k ≥ 2, if P(i) is true for all integers i from 2 through k, then P(k + 1) is also true:

(Assume the statement is true for all i with 2≤i<k (inductive hypothesis) Show that it is true for k.)

We have for all iÎZ with 2≤i<k, i is divisible by a prime number for all integers i from 2 through k                    (1) Inductve hypothesis

We must show:  k+1 is also divisible by a prime.         (2) P(k+1)

Consider 2 cases:

                            a) (k+1 is prime). Then k is divisible by itself, a prime number

                            b) (k+1) is not prime.

In this case (k+1) is a composite k+1= ab where 2≤a<k+1 and 2≤b<k+1.

                                 a is divisible by a prime number p. In addition because

k + 1 = ab, we have that k + 1 is divisible by a. Hence, since k + 1 is divisible by a and a is divisible by p, by transitivity of divisibility, k + 1 is divisible by the prime

number p.

Thus, P(n) is true by strong induction.

∴ We have proven the BASIS and INDUCTIVE step and show that the statement is true.

PROVING A PROPERTY OF SEQUENCE

Suppose a₀, a₁, a₂, … is defined as follows:

                 a₀=1, a₁=2, a₂=3,

                 a_k = a_k-1+a_k-2+a_k-3 for all integers k≥3.

  Then P(n)= a_n ≤ 2ⁿ for all integers n≥0.             

Solution:

Basis      : The statement is true for n=0: a₀=1 ≤1=2⁰                      

                                                 for n=1: a₁=2 ≤2=2¹                       

                                                 for n=2: a₂=3 ≤4=2²
P(3): a₃₌ a₂+a₁+a₀                  a₃ ≤ 2³

                          = 3+2+1                                     6 ≤ 8

                          = 6                                              (True)

Inductive  :

For any k>2, assume P(i) is true for all i with 0≤i<k: a_i ≤ 2ⁱ   for all 0≤i<k .

         Show that P(k) is true:  a_k ≤ 2^k 
                                             a_k = a_k-1+a_k-2+a_k-3 

                                             ≤2^k-1+2 ^k-2+2 ^k-3                           

                                             ≤ 20+21+…+2k-3+2k-2+2k-1

                                             = 2k-1(as a sum of geometric sequence)

                                             ≤ 2k

Thus, P(n) is true by strong induction.