CompSci 102 © Michael Frank9.1Today’s topics••InductionInduction••Reading: Sections 3.3Reading: Sections 3.3••UpcomingUpcoming––More InductionMore InductionCompSci 102 © Michael Frank9.2§3.3: Mathematical Induction••A powerful, rigorous technique for provingA powerful, rigorous technique for provingthat a predicate that a predicate PP((nn) is true for ) is true for everyeverynatural number natural number nn, no matter how large., no matter how large.••Essentially a Essentially a ““domino effectdomino effect”” principle. principle.••Based on a predicate-logic inference rule:Based on a predicate-logic inference rule:PP(0)(0)nn00 ((PP((nn))PP((nn+1))+1)) nn00 P P((nn))“The First Principleof MathematicalInduction”CompSci 102 © Michael Frank9.3The “Domino Effect”0123456…••Premise #1:Premise #1: Domino #0 falls.Domino #0 falls.••Premise #2:Premise #2: For every For every nnNN,,if domino #if domino #nn falls, then so falls, then sodoes domino #does domino #nn+1.+1.••Conclusion:Conclusion: All ofAll ofthe dominoes fallthe dominoes falldown!down!Note: this workseven if thereare infinitelymany dominoes!CompSci 102 © Michael Frank9.4Validity of InductionProofProof that that kk00 PP((kk)) is a valid consequent: is a valid consequent:Given any Given any kk0, the 20, the 2ndnd antecedent antecedentnn00 ((PP((nn)) PP((nn+1))+1)) trivially implies that trivially implies thatnn0 (0 (nn<<kk)) ((PP((nn)) PP((nn+1))+1)), , i.e.i.e., that , that ((PP(0)(0) PP(1)) (1)) ( (PP(1)(1) PP(2)) (2)) …… ( (PP((kk1)1) PP((kk))))..Repeatedly applying the hypothetical syllogismRepeatedly applying the hypothetical syllogismrule to adjacent implications in this list rule to adjacent implications in this list kk1 times1 timesthen gives us then gives us PP(0)(0) PP((kk)); which together with; which together withPP(0) (antecedent #1) and (0) (antecedent #1) and modus modus ponens ponens gives usgives usPP((kk). Thus ). Thus kk00 PP((kk)). . CompSci 102 © Michael Frank9.5The Well-Ordering Property••Another way to prove the validity of theAnother way to prove the validity of theinductive inference rule is by using the inductive inference rule is by using the well-well-ordering propertyordering property, which says that:, which says that:––Every non-empty set of non-negative integers has aEvery non-empty set of non-negative integers has aminimum (smallest) element.minimum (smallest) element.–– SSNN : : mm SS : : nn SS : : mmnn••This implies that {This implies that {nn||¬¬PP((nn)} (if non-empty) has)} (if non-empty) hasa min. element a min. element mm, but then the assumption that, but then the assumption thatPP((mm1)1)PP((((mm1)+1)1)+1) would be contradicted. would be contradicted.CompSci 102 © Michael Frank9.6Outline of an Inductive Proof••Let us say we want to prove Let us say we want to prove nn PP((nn))……––Do the Do the base casebase case (or (or basis stepbasis step): Prove ): Prove PP(0)(0)..––Do the Do the inductive stepinductive step: Prove : Prove nn PP((nn))PP((nn+1)+1)..••E.g.E.g. you could use a direct proof, as follows: you could use a direct proof, as follows:••Let Let nnNN, assume , assume PP((nn)). (. (inductive hypothesisinductive hypothesis))••Now, under this assumption, prove Now, under this assumption, prove PP((nn+1)+1)..––The inductive inference rule then gives usThe inductive inference rule then gives us nn PP((nn))..CompSci 102 © Michael Frank9.7Generalizing Induction••Rule can also be used to prove Rule can also be used to prove nncc PP((nn))for a given constant for a given constant ccZZ, where maybe , where maybe cc0.0.––In this circumstance, the base case is to proveIn this circumstance, the base case is to provePP((cc) rather than ) rather than PP(0), and the inductive step is(0), and the inductive step isto prove to prove nnc c ((PP((nn)) PP((nn+1))+1))..••Induction can also be used to proveInduction can also be used to provenncc PP((aann)) for any arbitrary series { for any arbitrary series {aann}.}.••Can reduce these to the form already shown.Can reduce these to the form already shown.CompSci 102 © Michael Frank9.8Second Principle of Induction••Characterized by another inference rule:Characterized by another inference rule:PP(0)(0)nn0: (0: (00kknn PP((kk)) )) PP((nn+1)+1)nn0: 0: PP((nn))••The only difference between this and theThe only difference between this and the1st principle is that:1st principle is that:––the inductive step here makes use of thethe inductive step here makes use of thestronger hypothesis that stronger hypothesis that PP((kk)) is true for is true for allallsmaller numbers smaller numbers k<nk<n+1+1,, not just for not just for kk==nn..P is true in all previous casesA.k.a. “Strong Induction”CompSci 102 © Michael Frank9.9Induction Example (1st princ.)••Prove that the sum of the first Prove that the sum of the first nn odd oddpositive integers is positive integers is nn22. That is, prove:. That is, prove:••Proof by induction.Proof by induction.––Base case: Let Base case: Let nn=1. The sum of the first 1 odd=1. The sum of the first 1 oddpositive integer is 1 which equals 1positive integer is 1 which equals 122..(Cont(Cont……))21)12(:1 ninni= =P(n)CompSci 102 © Michael Frank9.10Example cont.••Inductive step: Prove Inductive step: Prove nn1: 1: PP((nn))PP((nn+1)+1)..––Let Let nn1, assume 1, assume PP((nn)), and prove , and prove PP((nn+1)+1)..22111)1(12)1)1(2()12()12(+=++=++ ==+=nnnniininiBy inductivehypothesis P(n)CompSci 102 © Michael Frank9.11Problem••ShowShow for all natural numbers for all natural numbers nn––((nn33 - - nn) is) is divisible by 3divisible by 3CompSci 102 © Michael Frank9.12Another Induction Example••Prove that Prove that nn>0, >0, nn<2<2nn. Let . Let PP((nn)=()=(nn<2<2nn))––Base case: Base case: PP(1)=(1<2(1)=(1<211)=(1<2)=)=(1<2)=TT..––Inductive step: For Inductive step: For nn>0, prove >0, prove PP((nn))PP((nn+1)+1)..••Assuming
View Full Document
Unlocking...