Mathematical Induction I & II

Mathematical Induction I & II

Question 1

1) What do you show in the basis step and what do you show in the inductive step when you use (ordinary) mathematical induction to prove that a property involving an integer  n  is true for all       integers greater than or equal to some initial integer? - You may use example of problems to explain this answer.

Answer

Let P(n) be a property that is defined for integers n, and let a be a fixed integer. Suppose the following two statements are true:
1. P(a) is true. 2. For all integers k ≥a, ifP(k) is true then P(k +1) is true. Then the statement for all integers n ≥a, P(n)is true.

Consider a statement of the form, “For all integers n ≥a, a property P(n) is true.” To prove such a statement, perform the following two steps: Step 1 (basis step): Show that P(a) is true. Step 2 (inductive step): Show that for all integers k ≥a, ifP(k) is true then P(k +1) is true. To perform this step, suppose that P(k) is true, where k is any particular but arbitrarily chosen integer with k ≥a. [This supposition is called the inductive hypothesis.] Then show that P(k +1) is true.

Example

For all integers n ≥ 8, nc / can be obtained using 3c / and 5c / coins.

Proof (by mathematical induction):
Let the property P(n) be the sentence  

nc / can be obtained using 3c / and 5c / coins. ← P(n)

 Show that P(8) is true: 

P(8) is true because 8c / can be obtained using one 3c / coin and one 5c / coin.

 Show that for all integers k≥8, if P(k) is true then P(k+1) is also true:

 [Suppose that P(k) is true for a particular but arbitrarily chosen integer k ≥ 8. That is:] 

Suppose that k is any integer with k ≥ 8 such that 

kc / can be obtained using 3c / and 5c / coins. ←P(k)inductive hypothesis 

 [We must show that P(k +1) is true. That is:] We must show that 

(k +1)c / can be obtained using 3c / and 5c / coins. ← P(k +1) 

 

 Case 1 

(There is a 5 c / coin among those used to make up the kc /.): 

In this case replace the 5c / coin by two 3c / coins; the result will be (k +1)c /.

 Case 2

 (There is not a 5 c / coin among those used to make up the kc /.):

 In this case, because k ≥ 8, at least three 3c / coins must have been used. 

So remove three 3c / coins and replace them by two 5c / coins; the result will be (k +1)c /. Thus in either case (k +1)c / can be obtained using 3c / and 5c / coins [as was to be shown].
[Since we have proved the basis step and the inductive step, we conclude that the propo- sition is true.]

Question 2

2) What is the inductive hypothesis in a proof by (ordinary) mathematical induction? 

Answer

Inductive hypothesis is the supposition in inductive step for P(n).

    Way to state inductive hypothesis :

                                If P(k) is a true, then P(k + 1) is true.

:: We need to assumes  the inductive hypothesis for P(k) is true before we can proof that P(x-1) is true.                                   

Question 3

3) Are you able to use (ordinary) mathematical induction to construct proofs involving various kinds of statements such as formulas, divisibility properties and inequalities? - You may use example of problems to explain this answer. Give examples of question for each type of problems (formulas, divisibility properties and inequalities)  

Answer 

By Formula

Show that if n is a positive integer, then

1 + 2+· · ·+n =

Solution :

 Let P(n) = 1 + 2+· · · n = n(n+1)/2  is   .

Prove that P(n) is true for n = 1, 2, 3, . . . .

BASIS STEP:

P(1) is true, because 1 = 1(1 + 1).

~ The left-hand side of this equation is 1 because 1 is the sum of the first positive integer. The right-hand side is found by substituting 1 for n in .

INDUCTIVE STEP:

For the inductive hypothesis we assume that P(k) holds for an arbitrary positive integer k. That is, we assume that          1 + 2+· · ·+k =

Under this assumption, it must be shown that P(k + 1) is true, namely, that

1 + 2+· · ·+k + (k + 1) =    =

is also true. When we add k + 1 to both sides of the equation in P(k), we obtain

1 + 2+· · ·+k + (k + 1) =   + (k + 1) =    
=

This last equation shows that P(k + 1) is true under the assumption that P(k) is true. This completes the inductive step.

Therefore, P(n) is true for all positive integers n. That is, we have proven that 1 + 2+· · ·+n =  

for all positive integers n.

Divisibility Properties

Use mathematical induction to prove that n³− n is divisible by 3 whenever n is a positive integer.

Solution:

To construct the proof, let P(n) denote the proposition: “n³ − n is divisible by 3.”

BASIS STEP:

The statement P(1) is true because 1³ − 1 = 0 is divisible by 3. This completes the basis step.

INDUCTIVE STEP:

Assume that P(k) is true; that is, we assume that k³ − k is divisible by 3 for an arbitrary positive integer k.

Then, P(k + 1) = (k + 1)³ − (k + 1) is divisible by 3, is also true. That is, we must show that

(k + 1) ³ − (k + 1) is divisible by 3.

Expand : (k + 1) ³ − (k + 1) = (k³ + 3k² + 3k + 1) − (k + 1)

= (k³ − k) + 3(k² + k).

Therefore, n³ − n is divisible by 3 whenever n is a positive integer.

Inequalities

Use mathematical induction to prove the inequality n < 2ⁿ for all positive integers n.

Solution:

Let P(n) be the proposition that n < 2ⁿ.

BASIS STEP:

P(1) =  1 <  = 2, true.

INDUCTIVE STEP:

Assume the inductive hypothesis that P(k) is true for an arbitrary positive integer k.

P(k + 1) =  k + 1 < , is true.

To show that this conditional statement is true for the positive integer k, we first add 1 to both sides of

k < , and then note that 1 ≤ . This tells us that

k + 1 <  ≤ 2k + 2k = 2 · 2k = 2k+1.

This shows that P(k + 1) is true, namely, that k + 1 < , based on the assumption that P(k)

is true. The induction step is complete.