8.7 Mathematical Induction - Kean University

1 Prove a statementbymathematicalinductionMany mathematicalfactsareestablishedby rstobservinga pattern,thenmakinga conjectureaboutthegeneralnatureofthepatt ern,and conjecture,weuseexistingfacts,combinethe minsucha waythatthey arerelevanttotheconjecture,andproceedina logicalmanneruntilthetruthoftheconjectur eis ,letusmake a conjectureregardingthesumofthe ,welookfora pattern:2 = 22 + 4 = 62 + 4 + 6 = 122 + 4 + 6 + 8 = 202 + 4 + 6 + 8 + 10 = , rstnnevenintegers1226312420530 Thenumbersin the sum columnofthetablecanbefactoredasfollows:2 = 1 2,6 = 2 3,12 = 3 4,20 = 4 5, and30 = 5 6. Notingthevaluesofntowhichthefactorizatio nscorrespond,wemake ourconjecture:Thesumofthe rstnevenintegers isn(n+ 1).Accordingtoourcalculations,thisholdsf ornuptoandincluding5. Butdoesit holdforalln? To establishthepatternforallvaluesofn, notfeasible,sinceyouwouldhave to verifythestatementforin nitelymanyn. A morepracticalprooftechniqueis nextintroducea methodcalledmathematicalinduction, whichistypicallyusedtoprove forthesumofthe rstnoddintegers?

2 MathematicalinductionBeforegivinga formalde nitionofmathematicalinduction,wetake ourdiscussionofthesumofthe rstnevenintegersandintroducesomenew ,theconjectureis givena name:Pn. Thesubscriptnmeansthattheconjecturedepen dsonn. Statingourconjecture,wehavePn:Thesumofth e rstnevenintegersisn(n+ 1)Forsomespeci cvaluesofn, theconjecturereadsasfollows:P8:Thesumoft he rst8evenintegersis8 9 = 72P12: Thesumofthe rst12evenintegersis12 13 = 156Pk:Thesumofthe rstkevenintegersisk(k+ 1)Pk+1:Thesumofthe rstk+ 1evenintegersis(k+ 1)(k+ 2)We nextstatetheprincipleofmathematicalinduc tion, naturalnumberandletPnbea statementthatdependsonn. true, integersk,Pk+1canbeshowntobetrueifPkis assumedtobetrue,thenPnis key :provingthatP1is (theassumptionthatPkis true)fora generalvalueofktoshow thatPk+1is , thesetwo pieces(proofofthebasecaseanduseoftheindu ctionhypothesis)prove ,weoftenhave totake anexpressioninthevariablekandreplacekwit hk+ 1. + 1in analgebraicexpressionReplacekwithk+ )3k 1b)k(k+ 1)(2k+ 1)6 Solutiona)Replacingkbyk+ 1,weobtain3k+1 1b)Replacingkbyk+ 1andsimplifying,(k+ 1)((k+ 1) + 1)(2(k+ 1) + 1)6=(k+ 1)(k+ 2)(2k+ 3)6 Out1 Replacekbyk+ 1in2k(k+ 2).

3 We nowreturntotheconjecturewemadeatthebegin ningofthissection,andprove it formulaby inductionProve thefollowingformulabyinduction:2 + 4 + + 2n=n(n+ 1):SolutionThisisthejustthestatementthat weconjecturedearlier, , ,weprove thatPnis trueforn= 1(thebasecase).We dothisbyreplacingeveryninPnwitha1, andthendemonstratingthattheresultis :2(1)= 1(1 + 1)Since2(1)= 1(1 + 1), weseethatP1is ,westatePk(replaceeveryninPnwithak) andassumethatPkis :2 + 4 + + 2k=k(k+ 1)Finally, westatePk+1, andusetheinductionhypothesis(theassumpti onthatPkis true)toprove thatPk+ +1:2 + 4 + + 2k+ 2(k+ 1) = (k+ 1)(k+ 2) prove thatPk+1holds,wewillstartwiththeexpressi onontheleft-handsideofPk+1, andshow thatit is + 4 + + 2k+ 2(k+ 1)Left-handsideofPk+1=k(k+ 1)+ 2(k+ 1)Inductionhypothesis=k2+k+ 2k+ 2 Expand=k2+ 3k+ 2 Combinelike terms= (k+ 1)(k+ 2)FactorWe seethattheresult,(k+ 1)(k+ 2), is theexpressionontheright-handsideofPk+1. Thus,bymathematicalinduction,Pnis trueforallnaturalnumbersn.

4 CheckIt Out2 Provethefollowingformulabymathematicalin duction:1 + 3 + 5 + + (2n 1) =n2. Example3 Provinga summationformulaby inductionProve thefollowingformulabyinduction:1 + 2 + 3 + +n=n(n+ 1)2 ,denotetheproposedequationbyPn, andprove thatit holdsforn= 1(thebasecase).Replacingeverynwitha1, wegetP1:1 =1(1 + 1)2 Clearly, thisis true, ,statePkandassumethatPkis :1 + 2 + 3 + +k=k(k+ 1)2:Finally, statePk+1, andusetheinductionhypothesis(theassumpti onthatPkistrue)toprove thatPk+ +1:1 + 2 + 3 + +k+ (k+ 1) =(k+ 1)(k+ 2)21 + 2 + 3 + +k+k+ 1 Left-handsideofPk+1=k(k+ 1)2+k+ 1 Inductionhypothesis=k(k+ 1) + 2(k+ 1)2 Usecommondenominator=k2+k+ 2k+ 22 Expand=k2+ 3k+ 22 Combinelike terms=(k+ 1)(k+ 2)2 FactorWe seethattheresult,(k+ 1)(k+ 2)2, is theexpressionontheright-handsideofPk+1. Thus,bymathematicalinduction,Pnis trueforallnaturalnumbersn. Out3 Prove byinduction:2 + 5 + 8 + + (3n 1) =12n(3n+ 1). Example4 Provinga formulaforpartialsumsby inductionProve byinduction:1 + 2 + 22+ 23+ + 2n 1= 2n 1:SolutionFirst,denotetheproposedequatio nbyPn, andprove thatit holdsforn= 1(thebasecase), :1 = 21 1;It is easytoseethatP1is ,statePkandassumethatPkis :1 + 2 + 22+ 23+ + 2k 1= 2k 1 Finally, statePk+1, andusetheinductionhypothesis(theassumpti onthatPkistrue)toshow thatPk+ +1:1 + 2 + 22+ 23+ + 2k 1+ 2k= 2k+1 11 + 2 + 22+ 23+ + 2k 1+ 2kLeft-handsideofPk+1=2k 1+ 2kInductionhypothesis= 2(2k) 1 Combinelike terms= 2k+1 seethattheresult,2k+1 1, is theexpressionontheright-handsideofPk+ ,bymathematicalinduction,Pnis trueforallnaturalnumbersn.

5 CheckIt Out4 Prove byinduction:1 + 4 + 42+ + 4n 1=4n 13 Youmaywonderhow onegetstheformulasto prove byinductionin the ofthesearearrivedat by Points ThePrincipleofMathematicalInductionis statedasfollows:Letnbeanaturalnumberandl etPnbea statementthatdependsonn. true, integersk,Pk+1canbeshowntobetrueifPkisas -sumedtobetrue,thenPnis + 1in (k+ 1)(k+ 2) + +k2 InExercises5 18,prove thestatementsby + 5 + + (2n+ 1) =n(n+ 2) + 6 + 10 + + (4n 2) = + 4 + 7 + + (3n 2) =n(3n 1) + 4 + 3 + + (6 n) =12n(11 n) + 5 + 3 + + (9 2n) = n2+ + 22+ 32+ +n2=n(n+ 1)(2n+ 1) + 23+ +n3=n2(n+ 1) 2+12 3+12 3+ +1n(n+ 1)=nn+ 2 + 2 3 + 3 4 + +n(n+ 1) =n(n+ 1)(n+ 2) + 3 + 32+ + 3n 1=3n + 5 + 52+ + 5n 1=5n +r+r2+ +rn 1=rn 1r 1,ra positive integer,r6= 1is +nis exerciseswilldraw ontheideaspresentedin thissectionandyourgeneral +n,na naturalnumber, show thatn2+nis b3,a; bpositive integers,show thata3 b3is divisiblebya that1 + 4 + 7 + + (3n 2) =n(3n 1) that1 + 4 + 42+ + 4n 1=4n 13byusingtheformulaforthesumoftermsofa geometricsequence.