MATHEMATICAL INDUCTION-(E)-03-Theory

6.2.1 First Principle of Mathematical Induction . The proof of proposition by mathematical induction consists of the following three steps : Step I : (Verification step) : Actual verification of the proposition for the starting value “i” Step II : (Induction step) : Assuming the proposition to be true for “k”, k  i and proving that it is true for the value (k + 1) which is next higher integer. Step III : (Generalization step) : To combine the above two steps Let p(n) be a statement involving the natural number n such that (i) p(1) is true i.e. p(n) is true for n = 1. (ii) p(m + 1) is true, whenever p(m) is true i.e. p(m) is true  p(m + 1) is true. Then p(n) is true for all natural numbers n. 6.2.2 Second Principle of Mathematical Induction . The proof of proposition by mathematical induction consists of following steps : Step I : (Verification step) : Actual verification of the proposition for the starting value i and (i + 1). Step II : (Induction step) : Assuming the proposition to be true for k – 1 and k and then proving that it is true for the value k + 1; k  i + 1. Step III : (Generalization step) : Combining the above two steps. Let p(n) be a statement involving the natural number n such that (i) p(1) is true i.e. p(n) is true for n = 1 and (ii) p(m + 1) is true, whenever p(n) is true for all n, where Then p(n) is true for all natural numbers. For a  b, The expression is divisible by (a) a + b if n is even. (b) a – b is n if odd or even. 6.2.3 Some Formulae based on Principle of Induction . For any natural number n (i) (ii) (iii) Example: 1 The smallest positive integer n, for which hold is (a) 1 (b) 2 (c) 3 (d) 4 Solution: (b) Let P(n) : Step I : For n = 2 which is true. Therefore, P(2) is true. Step II : Assume that P(k) is true, then p(k) : Step III : For n = k + 1, …..(i) and …..(ii) Which is true, hence (ii) is true. From (i) and (ii), Hence is true. Hence by the principle of mathematical induction P(n) is true for all Trick : By check option (a) For n = 1,  which is wrong (b) For n = 2,  which is correct (c) For n = 3,  6 < 8 which is correct (d) For n = 4,   24 < 39.0625 which is correct. But smallest positive integer n is 2. Example: 2 Let . Then which of the following is true. (a) Principle of mathematical induction can be used to prove the formula (b) (c) (d) S(1) is correct Solution: (c) We have , , Which is not true and , Which is not true. Hence induction cannot be applied and Example: 3 When P is a natural number, then is divisible by (a) P (b) (c) (d) Solution: (c) For n =1, we get, , Which is divisible by , so result is true for n =1 Let us assume that the given result is true for i.e. is divisible by i.e. …..(i) Now, by using (i) Which is divisible by , so the result is true for . Therefore, the given result is true for all by induction. Trick : For n = 2, we get, Which is divisible by . Given result is true for all Example: 4 Given and , , the value of for all is (a) (b) (c) 0 (d) None of these Solution: (b) …..(i) Step I : Given For n =1, , Option (b) For n = 1, which is true. For n = 2, which is true Therefore, the result is true for n = 1 and n = 2 Step II : Assume it is true for n = k then it is also true for n = k – 1 Then …..(ii) and …..(iii) Step III : Putting n = k in (i), we get This shows that the result is true for , by the principle of mathematical induction the result is true for all . 6.2.4 Divisibility Problems. To show that an expression is divisible by an integer (i) If a, p, n, r are positive integers, then first of all we write (ii) If we have to show that the given expression is divisible by c.S Then express, , if some power of has c as a factor. , if some power of has c as a factor. if some power of has c as a factor. Example: 5 is divisible by (where ) (a) (b) (c) (d) All of these Solution: (b)  From above it is clear that is divisible by . Trick : . Put and ; Then Is not divisible by 6, 54 but divisible by 9. Which is given by option (c) = . Example: 6 The greatest integer which divides the number is (a) 100 (b) 1000 (c) 10000 (d) 100000 Solution: (c)  From above it is clear that, is divisible by