Mathematical InductionWhat is induction?Induction exampleInduction example, continuedSlide 5What did we showThe idea behind inductive proofsQuick surveySlide 9Why speling is not so important…Second induction exampleSecond induction example, continuedSlide 13Notes on proofs by inductionThird induction exampleSlide 16Third induction again: what if your inductive hypothesis was wrong?Slide 18Fourth induction exampleSlide 20Strong inductionStrong induction example 1Slide 23Strong induction vs. non-strong inductionAnswer via mathematical inductionAnswer via strong inductionStrong induction vs. non-strong induction, take 2Slide 28Slide 29Slide 30An aside: IOCCCSlide 32Chess and inductionSlide 34We are skipping…Question 40Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 4311Mathematical InductionMathematical InductionCS/APMA 202CS/APMA 202Rosen section 3.3Rosen section 3.3Aaron BloomfieldAaron Bloomfield22 What is induction?What is induction?A method of proofA method of proofIt does not generate answers: It does not generate answers: it only can prove themit only can prove themThree parts:Three parts:Base case(s): show it is true Base case(s): show it is true for one elementfor one elementInductive hypothesis: assume Inductive hypothesis: assume it is true for any given elementit is true for any given elementMust be clearly labeled!!!Must be clearly labeled!!!Show that if it true for the next Show that if it true for the next highest elementhighest element33 Show that the sum of the first Show that the sum of the first nn odd odd integers is integers is nn22Example: If Example: If nn = 5, 1+3+5+7+9 = 25 = 5 = 5, 1+3+5+7+9 = 25 = 522Formally, ShowFormally, ShowBase case: Show that P(1) is trueBase case: Show that P(1) is trueInduction exampleInduction examplenini12121111)(2112ii )P( where)P( nnn)1P(44 Inductive hypothesis: assume true for Inductive hypothesis: assume true for kkThus, we assume that P(Thus, we assume that P(kk) is true, or that) is true, or thatNote: we don’t yet know if this is true or not!Note: we don’t yet know if this is true or not!Inductive step: show true for Inductive step: show true for kk+1+1We want to show that: We want to show that: kiki1212112)1(12kikiInduction example, continuedInduction example, continued55 12121)1(221kkikki121)1(222 kkkkInduction example, continuedInduction example, continuedRecall the inductive hypothesis:Recall the inductive hypothesis:Proof of inductive step:Proof of inductive step:kiki1212121222 kkkk211)1(12 kiki66 What did we showWhat did we showBase case: P(1)Base case: P(1)If P(If P(kk) was true, then P() was true, then P(kk+1) is true+1) is truei.e., P(i.e., P(kk) → P() → P(kk+1)+1)We know it’s true for P(1)We know it’s true for P(1)Because of P(Because of P(kk) → P() → P(kk+1), if it’s true for P(1), then it’s true for P(2)+1), if it’s true for P(1), then it’s true for P(2)Because of P(Because of P(kk) → P() → P(kk+1), if it’s true for P(2), then it’s true for P(3)+1), if it’s true for P(2), then it’s true for P(3)Because of P(Because of P(kk) → P() → P(kk+1), if it’s true for P(3), then it’s true for P(4)+1), if it’s true for P(3), then it’s true for P(4)Because of P(Because of P(kk) → P() → P(kk+1), if it’s true for P(4), then it’s true for P(5)+1), if it’s true for P(4), then it’s true for P(5)And onwards to infinityAnd onwards to infinityThus, it is true for all possible values of Thus, it is true for all possible values of nnIn other words, we showed that:In other words, we showed that:  )P()1P()P()1P( nnkkk 77 The idea behind inductive proofsThe idea behind inductive proofsShow the base caseShow the base caseShow the inductive hypothesisShow the inductive hypothesisManipulate the inductive step so that you Manipulate the inductive step so that you can substitute in part of the inductive can substitute in part of the inductive hypothesishypothesisShow the inductive stepShow the inductive step8 Quick surveyQuick surveyI felt I understood the first example of I felt I understood the first example of induction…induction…a)a)Very wellVery wellb)b)With some review, I’ll be goodWith some review, I’ll be goodc)c)Not reallyNot reallyd)d)Not at allNot at all9 Quick surveyQuick surveyI felt I could do my own inductive I felt I could do my own inductive proof…proof…a)a)Very wellVery wellb)b)With some review, I’ll be goodWith some review, I’ll be goodc)c)Not reallyNot reallyd)d)Not at allNot at all1010Why speling is not so Why speling is not so important…important…I cdnuolt blveieetaht I cluod aulaclty uesdnatnrd I cdnuolt blveieetaht I cluod aulaclty uesdnatnrd waht I was rdanieg. The phaonmneal pweor of waht I was rdanieg. The phaonmneal pweor of thehmuan mind. Aoccdrnig to a rscheearch at thehmuan mind. Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it deosn't mttaer in waht Cmabrigde Uinervtisy, it deosn't mttaer in waht oredr the ltteers in a wrod are, the olny oredr the ltteers in a wrod are, the olny iprmoatnt tihng is taht thefrist and lsat ltteer be iprmoatnt tihng is taht thefrist and lsat ltteer be in the rghit pclae. The rset can be a taotl mses in the rghit pclae. The rset can be a taotl mses andyou can sitll raed it wouthit a porbelm. Tihs andyou can sitll raed it wouthit a porbelm. Tihs is bcuseae the huamn mnid deosnot raed ervey is bcuseae the huamn mnid deosnot raed ervey lteter by istlef, but the wrod as a wlohe. lteter by istlef, but the wrod as a wlohe. Amzanig huh? yaeh and I awlyas thought Amzanig huh? yaeh and I awlyas thought slpeling was ipmorantt.slpeling was ipmorantt.1111 Second induction exampleSecond induction exampleRosen, section 3.3, question 2:Rosen, section 3.3, question 2:Show the sum of the first Show the sum of the first nn positive even positive even integers is integers is nn22 + + nnRephrased: Rephrased: The three parts:The three parts:Base caseBase caseInductive hypothesisInductive hypothesisInductive stepInductive stepninninnn122)P( where)P(1212 Second induction