Induction: One Step At A TimeSlide 2Slide 3Let’s start with dominoesDomino Principle: Line up any number of dominos in a row; knock the first one over and they will all fall.n dominoes numbered 1 to nSlide 7n dominoes numbered 0 to n-1The Natural NumbersSlide 10Standard Notation/Abbreviation “for all” is written “8”Slide 12Plato: The Domino Principle works for an infinite row of dominoesPlato’s Dominoes One for each natural numberThe Infinite Domino PrincipleMathematical Induction: statements proved instead of dominoes fallenInductive Proof / Reasoning To Prove k 2 , SkSlide 18Inductive Proof / Reasoning To Prove k ≥ b, SkSlide 20Slide 21Slide 22Slide 23Sn “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 25Slide 26Slide 27Slide 28Slide 29Slide 30Sn ´ “n =n(n+1)/2” Use induction to prove k ≥ 0, SkSlide 32Slide 33Slide 34Trying to prove Sk-1 ) SkSlide 36Slide 37All Previous Induction To Prove k, SkSlide 39“All Previous” Induction Can Be Repackaged As Standard InductionSlide 41Aristotle’s ContrapositiveSlide 43Contrapositive or Least Counter-Example Induction to Prove k, SkLeast Counter-Example Induction to Prove k, SkRene Descartes [1596-1650] “Method Of Infinite Decent”Each number > 1 has a prime factorization.Slide 48Slide 49Theorem: Each natural has a unique factorization into primes written in non-decreasing order.Theorem: Each natural has a unique factorization into primes written in non-decreasing order.Slide 52Slide 53Slide 54Slide 55Invariant 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 60Slide 61Slide 62Slide 63Inductive Definition Of FunctionsInductive Definition Recurrence Relation for F(X)Slide 66Slide 67Slide 68Inductive Definition Recurrence Relation for F(X) = 2XInductive Definition Recurrence RelationSlide 71Slide 72Slide 73Inductive Definition Recurrence Relation F(X) = X for X a whole power of 2.Leonardo FibonacciSlide 76Slide 77The rabbit reproduction modelSlide 79Slide 80Slide 81Slide 82Slide 83Slide 84Inductive Definition or Recurrence Relation for the Fibonacci NumbersSlide 86Programs to compute Fib(n)?Slide 88What is a closed form formula for Fib(n) ????Slide 90Study BeeInduction: One Step At A TimeGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2005Lecture 2 Sept 01, 2005 Carnegie Mellon UniversityToday we will talk about INDUCTIONInduction is the primary way we:1.Prove theorems2.Construct and define objectsLet’s start with dominoesDomino Principle: Line up any number of dominos in a row; knock the first one over and they will all fall.n dominoes numbered 1 to nFk ´ The kth domino fallsIf we set them all up in a row then we know that each one is set up to knock over the next one:For all 1 ≤ k < n:Fk ) Fk+1n dominoes numbered 1 to nFk ´ The kth domino fallsFor all 1 ≤ k < n:Fk ) Fk+1F1 ) F2 ) F3 ) …F1 ) All Dominoes Falln dominoes numbered 0 to n-1Fk ´ The kth domino fallsFor all 0 ≤ k < n-1:Fk ) Fk+1F0 ) F1 ) F2 ) …F0 ) All Dominoes FallThe Natural Numbers = { 0, 1, 2, 3, . . .}The Natural Numbers = { 0, 1, 2, 3, . . .}One domino for each natural number:0 1 2 3 4 5 ….Standard Notation/Abbreviation“for all” is written “8”Example:For all k>0, P(k)is equivalent to8 k>0, P(k)n dominoes numbered 0 to n-1Fk ´ The kth domino falls8 k, 0 ≤ k < n-1:Fk ) Fk+1F0 ) F1 ) F2 ) …F0 ) All Dominoes FallPlato: 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 numberAn infinite row, 0, 1, 2, … of dominoes, one domino for each natural number. Knock the first domino over and they all will fall.Proof: Suppose 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.The Infinite Domino PrincipleFk ´ The kth domino will fallAssume we know that for every natural number k,Fk ) Fk+1F0 ) F1 ) F2 ) …F0 ) All Dominoes FallMathematical Induction: statements proved instead of dominoes fallenInfinite sequence of statements: S0, S1, …Fk ´ “Sk proved”Infinite sequence ofdominoes.Fk ´ “domino k fell”Establish 1) F02) For all k, Fk ) Fk+1Conclude that Fk is true for all kInductive Proof / ReasoningTo Prove k 2 , SkEstablish “Base Case”: S0Establish that k, Sk ) Sk+1Assume hypothetically that Sk for any particular k; Conclude that Sk+1k, Sk ) Sk+1Inductive Proof / ReasoningTo Prove k 2 , SkEstablish “Base Case”: S0Establish that k, Sk ) Sk+1“Induction Hypothesis” Sk“Induction Step” Use I.H. to show Sk+1k, 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.Theorem:? 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 ”Assume “Induction Hypothesis”: Sk (for any particular k¸ 1) 1+3+5+…+ (2k-1) = k2Add (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: 8n ≥ 1 SnIn summary:1) Establish base case: S12) Establish domino property: 8k ≥ 0 Sk ) Sk+1By induction on n, we
View Full Document
Unlocking...