Induction: One Step At A TimeSlide 2Slide 3Slide 4Slide 5Standard NotationSlide 7The Natural NumbersPlato: The Domino Principle works for an infinite row of dominoesPlato’s Dominoes One for each natural numberSlide 11Inductive Proof / Reasoning To Prove k 2 , SkSlide 13Inductive Proof / Reasoning To Prove k ≥ b, SkSlide 15Slide 16Slide 17Sn “The sum of the first n odd numbers is n2.” “1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2” Trying to establish that: 8n ≥ 1 SnSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Sn ´ “n =n(n+1)/2” Use induction to prove k ≥ 0, SkSlide 28Sn ´ “n =n(n+1)/2” Use induction to prove k ≥ 0, SkSlide 30Slide 31Slide 32Trying to prove Sk-1 ) SkSlide 34Sn “n can be factored into primes” Use induction to prove k > 1, SkSlide 36All Previous Induction To Prove k, SkSlide 38Slide 39Aristotle’s ContrapositiveSlide 41Contrapositive or Least Counter-Example Induction to Prove k, SkLeast Counter-Example Induction to Prove k, SkRene Descartes [1596-1650]Each number > 1 has a prime factorization.Slide 46Slide 47Theorem: Each natural has a unique factorization into primes written in non-decreasing order.Slide 49Slide 50Slide 51Theorem: Each natural has a unique factorization into primes written in non-decreasing order.Slide 53Slide 54Slide 55Slide 56Invariant Induction Suppose we have a time varying world state: W0, W1, W2, … Each state change is assumed to come from a list of permissible operations. We seek to prove that statement S is true of all future worlds.Invariant Induction Suppose we have a time varying world state: W0, W1, W2, … Each state change is assumed to come from a list of permissible operations.Odd/Even Handshaking Theorem: At any party at any point in time define a person’s parity as ODD/EVEN according to the number of hands they have shaken. Statement: The number of people of odd parity must be even.Statement: The number of people of odd parity must be even.Slide 61Slide 62Slide 63Inductive Definition Of FunctionsSlide 65Slide 66Slide 67Slide 68Slide 69Programs to compute Fib(n)?Slide 71What is a closed form formula for Fib(n) ????Slide 73Study BeeInduction: One Step At A TimeGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2006Lecture 2 Aug 31, 2006 Carnegie Mellon UniversityToday we will talk about INDUCTIONInduction is the primary way we:1.Prove theorems2.Construct and define objectsDominoesDomino Principle: Line up any number of dominos in a row; knock the first one over and they will all fallDominoes Numbered 1 to nFk ´ “The kth domino falls”If we set them up in a row then each one is set up to knock over the next:For all 1 ≤ k < n:Fk ) Fk+1F1 ) F2 ) F3 ) …F1 ) All Dominoes FallStandard Notation“for all” is written “8”Example:For all k>0, P(k)8 k>0, P(k)=Dominoes Numbered 1 to nFk ´ “The kth domino falls”8k, 0 ≤ k < n-1:Fk ) Fk+1F0 ) F1 ) F2 ) …F0 ) All Dominoes FallThe Natural NumbersOne domino for each natural number:0 1 2 3 4 5 …. = { 0, 1, 2, 3, . . .}Plato: The Domino Principle works for an infinite row of dominoesAristotle: Never seen an infinite number of anything, much less dominoes.Plato’s DominoesOne for each natural numberTheorem: An infinite row of dominoes, one domino for each natural number.Knock over the first domino and they all will fallSuppose they don’t all fall. Let k > 0 be the lowest numbered domino that remains standing. Domino k-1 ≥ 0 did fall, but k-1 will knock over domino k. Thus, domino k must fall and remain standing. Contradiction.Proof:Mathematical Induction statements proved instead of dominoes fallenInfinite sequence ofdominoesInfinite sequence of statements: S0, S1, …Fk ´ “domino k fell” Fk ´ “Sk proved”Conclude that Fk is true for all kEstablish: 1. F02. For all k, Fk ) Fk+1Inductive Proof / ReasoningTo Prove k 2 , SkAssume hypothetically that Sk for any particular k; k, Sk ) Sk+1Establish “Base Case”: S0Establish that k, Sk ) Sk+1Conclude that Sk+1Inductive Proof / ReasoningTo Prove k 2 , SkEstablish “Base Case”: S0“Induction Hypothesis” Sk“Induction Step” Use I.H. to show Sk+1k, Sk ) Sk+1Establish that k, Sk ) Sk+1Inductive Proof / ReasoningTo Prove k ≥ b, SkEstablish “Base Case”: SbEstablish that k ≥ b, Sk ) Sk+1Assume k ≥ b“Inductive Hypothesis”: Assume Sk “Inductive Step:” Prove that Sk+1 followsTheorem:? The sum of the first n odd numbers is n2.Check on small values:1 = 11+3 = 41+3+5 = 91+3+5+7 = 16Theorem:?The sum of the first n odd numbers is n2. The kth odd number isexpressed by the formula(2k – 1), when k>0.Sn “The sum of the first n odd numbers is n2.” Equivalently, Sn is the statement that: “1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2 ”Sn “The sum of the first n odd numbers is n2.” “1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2” Trying to establish that: 8 n ≥ 1 SnSn “The sum of the first n odd numbers is n2.” “1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2” Trying to establish that: 8 n ≥ 1 SnAssume “Induction Hypothesis”: Sk (for any particular k¸ 1) 1+3+5+…+ (2k-1) = k2Induction Step:Add (2k+1) to both sides.1+3+5+…+ (2k-1)+(2k+1) = k2 +(2k+1) Sum of first k+1 odd numbers = (k+1)2CONCLUDE: Sk+1Sn “The sum of the first n odd numbers is n2.” “1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2” Trying to establish that: 8 n ≥ 1 SnIn summary:1) Establish base case: S12) Establish domino property: 8k ≥ 1 Sk ) Sk+1By induction on n, we conclude that: 8k ≥ 1 SkSn “The sum of the first n odd numbers is n2.” “1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2” Trying to establish that: 8 n ≥ 1 SnTHEOREM: The sum of the first n odd numbers is n2.Theorem? The sum of the first n numbers is ½n(n+1).Theorem? The sum of the first n numbers is ½n(n+1).Try it out on small numbers!1 = 1 =½1(1+1).1+2 = 3 =½2(2+1).1+2+3 = 6 =½3(3+1).1+2+3+4 = 10 =½4(4+1).Theorem? The sum of the first n numbers is ½n(n+1). = 0 =½0(0+1).1 = 1 =½1(1+1).1+2 = 3 =½2(2+1).1+2+3 = 6 =½3(3+1).1+2+3+4 = 10 =½4(4+1).Notation: 0 = 0 n= 1 + 2 + 3 + . . . + n-1 + nLet Sn be the statement “n =n(n+1)/2”Sn ´ “n =n(n+1)/2”Use induction to prove k ≥ 0, SkSn ´ “n =n(n+1)/2”Use induction to prove k ≥ 0, SkSn ´ “n =n(n+1)/2”Use induction to prove k ≥ 0, SkEstablish “Base
View Full Document