MATHEMATICAL INDUCTION, PRINCIPLE OF Ma’ THEMATIC, MATICAL INDUCTION Let P(n) be a statemey . number 0. Then ément oF proposition involving the natural ; HfP(1) is true and PP(K+1) is true on "e assumption tha ru (k+1) is true on th 'ssumption that (k) that P(k) is true we conclude that a statement P(n) is true for all natural numbers n Hence to prove that a statement P(n) is true for all natural numbers, we must go through two steps : First: We must prove that P(1) is true: Second > Assuming that P(k) is true, we must prove that The first step is called the basis step of the proof. The second step is called the induction step of the proof. The following examples illustrate this method of proof. P(k +1) is also trueW.E.1. Prove by induction method, for n 2 |, - R= n(n+\(2n+1) te 6 (Apr ‘99, B.E., Madurai Uni.; Apr '99, M.C.A,, Bharathidasan Uni.) Solution Let P(n) denote the statement p(n): +2 +...43 = nls I(2n+ 1) o Mee Letn= 1, LHS. of P(I)=1 = 1. RHS. of I) =e nee =1= LHS. of PU) ~. P(1) is true. Let us assume that P(k) is true.2 2 2 2 ie, Pk): P42 tent k= mesner is true. 22 2 (K+ W(A+2)(2k +3) We claim that P(k+1): +2 + ..,0+ (k+l) eee is true. Nowl +2 +. 4K + (RH =(L 42 to +k )+(ktL) k > . =H? +O sean? (+ P(k) is true)dd K(k 1 also true. « p(ktl) is true e, P(Kt! )is induction, Thus, if P(k) 5 Je of mathematical _ nent 204) . 5 for alln 2 1.Example 2.1 Prove, by mathematical induction, that T4324 S24 oe + (Qn — IP = nn 1) Qn +1). Let Sn): 1? + 37 + 5? + + + Qn — 1)? 4n(2n 1) Qn +1) When m= 1, 1 SQ): P= 2-113 (1): 3 So S(1) is true, viz., the basic step is valid Let S(n) be true for m = k ic, PSE SPH + QE P= FAR 1) Qk + 1) Now 17 +374 5? 4... + (2k- 1)? + (2k + 1P = 542k 1) Qk + 1) + (2k + DP, using the truth of S(k) = FQk+ 1) OK 1) + 32K +1} 4k + 1) 22 + 5k +3) 408 + 1) Qk + 3k + 1) or qk 1) 2k + 1) (2k +3) ie, Sk +1) is valid,Thus the inductive step is also true. Hence, S(n) is true for all ne Z’. Example 2.2 Prove, by mathematical induction, that 1-2-342-3-443-4-54--4+n(n+ 1) (nt 2) fain +1) (0 +2) (0 +3). Lat S21-2-3423 4 vet nl 1) (0+ 2)= El +1) (0+ 2) (+ 9), Now S:1-2-3=4-1 31/4 Thus, the basic step 5S, is true Let S, be true ey VDF 3 AE EMA D EH I= Tes DESDE) ad) Now [1-2-342-3-44--+kk+ G+ 21+ b+ +2 +3) Atk + 1) (k + 2) (K+ 3) + (k + 1) (k + 2) (k + 3), by CD (k + 1) (k +2) (K+ 3) tk + 4} Thus S; « ; is true, if S; is true. i.e., the inductive step is true. Hence, S,, is true for all n € Z".Example 2.3 Prove. by mathematical induction, that Litit Lin 12°23 °34* *i@e) ntl 1 n Let on al) al Then i.e., the basie ste __k +k +l k+l a gl gs Mk +) (k+1(K+2) "Ee eesD" ma) 1 [k(k+2)41 k+l| k+2- 1 [ks k+l| k+2 (2) means that 5, ., is also true. i.e., the inductive step is true. Henee, S, is true for all n € Z*. Example 2.4 Use mathemati a2 2"-', forn=1, Let S, ml 22"-! e Sy: 1! 2 2°, which is true. ie., the basic step is true Let S; be true ie, ee (a) Now (K+ DI=(k+ 1). At 2 (k + 1). 2-1 by (1) 22.21 since k+ 122 oF Q) Step (2) means that S, , , is also true. i.e., the inductive step is true. Hence, S,, is true for m = 1, 2, 3, Q) I induction to show that BF asExample 2.5 Use mathematical induction to show that i ova, for n> 2 on | 1 Let Sp theta dn "Vi 2° V3 vn 5; 444 += > V2, since LS = 1.707 and RS = 1414 vi v2 i.e., the basic step is true form = Let S; be true. ie, a) vi v2 3 Liiva Li I N ep Up eg ey ove + » by (1) ~ vi v2 3 ik k+l Jie”ie, > fk+i Li Lo qty ek > fe Q) vi v2 veo fest Step (2) means that S; ,; is also true. Hence, S, is true for n = 2, 3, 4, ... . Example 2.6 Use mathematical induction to show that 1:3-5-(Qn-D) 1 2-4-6--Qn) ~ Ini” 13-5--Qn-). 1 2n) n+l which is true. for n = 1, 2, 3, ... Let Sy i.e., the basic step is true. Let S, be true L3-5--(2k-) 2 1 2-4-6--2k) ~ Seat ie, qa) Now Q)2k+2~ [eae phi? w Qk +1) (2k +2 2 a ‘ jet AA 4K HL RH AP 48k 440K +2 ie, if 46 + 120 + 9k +25 403 + 12? + 12k + 4 ie, if 9% +2< 12k+4 ie. if 3k +220, which is true. Using this in step (2), we get 13-5--(Qk-D2K+I) . 1 k+l 24-62 2K+2) ~ kal Jke2 ie, tn (3) ED Step (3) means that S,, , also true. ie. the induction step is true. Hence, S, is true for n = 1, 2, 3,Example 2.7 Use mathematical induction to prove that H,.>1+ 4, where . n Let Sy Hyp 2A Le p21ed, which is true i.e., the basic step is true. Let S; be true. i all 1 ie, l4styt ayant Now Q)- each of the 2 terms in the second group = aa the last term) Q) Step (2) means that S, , , is true. ie., the inductive step is true. §, is true forn € Z’. Example 2.8 Use mathematical induction to prove that »° + 2n is divisible by 3, form > 1 Let S,: (® + 2n) is divisible by 3. 5: (3 + 2) is divisible by 3, which is true. ie., the basic step is true. Let S, be true. ley iP + 2k is divisible by 3 (dl)Now (K+ 13 +k +1) = (@ + 2k) + BF + 3k + 3) ( + 2k) is divisible by 3, by (1) Also 343 + 3k + 3 = 3(K? + k + 1) is divisible by 3. The sum, namely, (k + 1)3 + 2(k + 1) is divisible by 3 Q) ie, Sy is also true i the inductive step is true. true for n 2 1. Example 2.9 Use mathematical induction to prove that w+ (n+ 1) +(n + 2) is divisible by 9, for 7 > 1. Let Sy + (n+ IP + (n+ 2) is divisible by 9. Sy: B + 23 + 33 = 36 is divisible by 9, which is true. ie., the basic step is true. Let S, be true. ie, 1B + (k + 1) + (k + 2)3 is divisible by 9 aw Now kt IP HRW E+ 3S = [Rh + (+ IP + (K+ 293] + [9 + 27k + 27] = [Rh + (K+ IP + (K+ 2))] + 90 + 3k + 3) The first expression is divisible by 9 [by (1)] and the second expression is a multiple of 9. Their sum is divisible by 9 Sys, is true. - ie, the inductive step is true. ee 5, is true form > 1Example 2.10 Use mathematical induction to prove that (3" + 7" — 2) is divisible by 8, for 2 2 1. Let 5, 3" + 7" — 2) is divisible by 8 ‘ S\: 3 + 7— 2) is divisible by 8, which is true. ie, the basic step is true. Let S, be true. ie, (34 + 7 — 2) is divisible by 8 a Now get ly peel 3 + 7(74 — 2 = 3434 + 7-23 + 47 + 1) (2) 3(3* + 7* — 2) is divisible by 8, by step (1) 7* + 1 is an even number, for k = 1 4(7* + 1) is divisible by 8 RS. of (2) is divisible by 8 BEM eed divisible by 8 é,, Sy 41 is also true. ie, the inductive step is true S, is true for n > 1.WE2. Show that a’ - b" is divisible by (a-b ) for all n € N. (Apr 97, B.E., Bharthisdasan Uni.)Solution hon Let P(n): a -b is Putn=1. P(1)=a - ~. P(1) is true. Let us assume that P(k) is true. i.e., a Leta -b =c(a-b). Soa =b +c(a-b) Now ye! eda-t'b caussnedt (1) oak k k walt *¢(@-b)]- b..b substituting for a from (1) “ab + ac(a—b)—bb =b (ab) + ac (a—by citer =@~b)(b + ac) divisible by (a - b). b!=a-bis divisible by (a - b). * bt is divisible by (ab).W.E.3. Prove by mathematical induction that 2° > 0 for alln € N Solution Let P(n): 2"—n >0. Putn 1: P(1): 2! So P(1) is true. Let us assume that P(k) is true. Here i.e. 2' ~ k is positive weve 1=2-1=1>0 k is a positive integer. Let 2°—k=m , To prove that P(k+1) also is positive, consider 2 —(k + )- Now2. — (kt) =2.2 -k-1 ‘ (k+m)—k-1 substituting for 2. from d) +2m-1 ositive number ( ° m is positive ) i.e., if P(k) is true, P(k+1) is also true. So by the principle of mathematical induction, P(n) is true. n ie..2 —n>0. So 2" >n forallne N.by mathematical induction that WEA IA Ag oon A, are any n sets, show 7 2 ( Extended De Morgan's Law ) Ua =a: oom ul (A denotes complement of A) Solution Let P(n) be the statement that the equality holds for n sets. Basis Step : P(1) is the statement that ‘A. =A which is obviously true. S. Induction Step :. Suppose P(ky is true for any k set jie, A, UA, Une UAL AA, oe MA, . for any k sets AA, Let A), Aye co Ay, beany k + I sets: Let B= A,UA,U Ay Then B= A, UA, U2 UA, = LHS. of P(k+1 A,UA,U- =(K,UA,U- kBAA. (by DeMorgan’s law for two sets ) be MIA DAL DAO ALY fh (nye rt kal 114, R.H.S. of P(k+1) “| Le. if P(k) is true, P(k+1) is also true. So by the principle of mathematical induction P(n) is true for alln > 1Suppose we have stamps of two different mt dteres Rs 5. show that it is possible to make up exactly any postage where n2 8 is an integer, using stamps of these two denominations. Solution Let P(n) be the statement, . P(n) : Itis possible to make up exactly a postage of Rs n using Rs 3 and Rs 5 stamps. Clearly P(8) is true as one Rs 3 stamp and one Rs 5 are enough to make upa Postage of Rs 8 Now assume that P(k) is true for some k > 8. Suppose we make Up a postage of Rs k using at least one Rs 5 stamp. Replacing a Rg § stamp by two Rs 3 stamps will yield a way to make UP a postage of Rs (k + 1). On the other hand, Suppose we make up a Postage of Rs k using Rs 3 stamps only. Since k > 8, there must be at least three Rs 3 stamps. Replacing three Rs 3 stamps by two Rs 5 stamps will yield a Way to make up a postage of Rs (k +1). Thus if P(k) is true for some k 2 8, then P(k + 1) is also true, Thus by the Principle of mathematical induction, P(n) is true for alln>8.