Sunday 31 March 2013

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 is divisible by 3 whenever n is a positive integer.
Solution:
To construct the proof, let P(n) denote the proposition: 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 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.