Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 2 CS 15 251 Sept 01 2005 Fall 2005 Carnegie Mellon University Induction One Step At A Time Today we will talk about INDUCTION Induction is the primary way we 1 Prove theorems 2 Construct and define objects Let s start with dominoes Domino 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 n Fk The kth domino falls If 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 1 n dominoes numbered 1 to n Fk The kth domino falls For all 1 k n Fk Fk 1 F1 F2 F3 F1 All Dominoes Fall n dominoes numbered 0 to n 1 Fk The kth domino falls For all 0 k n 1 Fk Fk 1 F0 F1 F2 F0 All Dominoes Fall The 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 to 8k 0 P k n dominoes numbered 0 to n 1 Fk The kth domino falls 8k 0 k n 1 Fk Fk 1 F0 F1 F2 F0 All Dominoes Fall Plato The Domino Principle works for an infinite row of dominoes Aristotle Never seen an infinite number of anything much less dominoes Plato s Dominoes One for each natural number An 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 Principle Fk The kth domino will fall Assume we know that for every natural number k Fk Fk 1 F 0 F 1 F2 F0 All Dominoes Fall Mathematical Induction statements proved instead of dominoes fallen Infinite sequence of dominoes Fk domino k fell Establish Infinite sequence of statements S0 S1 Fk Sk proved 1 F0 2 For all k Fk Fk 1 Conclude that Fk is true for all k Inductive Proof Reasoning To Prove k 2 Sk Establish Base Case S0 Establish k Sk Sk 1 that k Sk Sk 1 Assume hypothetically that Sk for any particular k Conclude that Sk 1 Inductive Proof Reasoning To Prove k 2 Sk Establish Base Case S0 Establish that k Sk Sk 1 Induction Hypothesis Sk k Sk Sk 1 Induction Step Use I H to show Sk 1 Inductive Proof Reasoning To Prove k b Sk Establish Base Case Sb Establish that k b Sk Sk 1 Assume k b Inductive Hypothesis Assume Sk Inductive Step Prove that Sk 1 follows Theorem 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 1 1 3 4 1 3 5 9 1 3 5 7 16 Theorem The sum of the first n odd numbers is n2 The kth odd number is expressed 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 8n 1 Sn Assume Induction Hypothesis Sk for any particular k 1 1 3 5 2k 1 k2 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 2 CONCLUDE Sk 1 Sn The sum of the first n odd numbers is n2 1 3 5 2k 1 2n 1 n2 Trying to establish that 8n 1 Sn In summary 1 Establish base case S1 2 Establish domino property 8k 0 Sk Sk 1 By induction on n we conclude that 8k 0 Sk THEOREM 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 n1 n Let Sn be the statement n n n 1 2 Sn n n n 1 2 Use induction to prove k 0 Sk Establish Base Case S0 0 The sum of the first 0 numbers 0 Setting n 0 the formula gives 0 0 1 2 0 Establish that k 0 Sk Sk 1 Inductive Hypothesis Sk k k k 1 2 k 1 k k 1 k k 1 2 k 1 Using I H k 1 k 2 2 which proves Sk 1 Theorem The sum of the first n numbers is n n 1 Primes A natural number n 1 is called prime if it has no divisors besides 1 and itself n b 1 is not considered prime Theorem Every natural number 1 can be factored into primes Sn n can be factored into primes Base case 2 is prime S2 is true Trying to prove Sk 1 Sk How do we use the fact Sk 1 k 1 can be factored into primes to prove that Sk k can be factored into primes Hmm This illustrates a technical point about using and defining mathematical induction Theorem Every natural number 1 can be factored into primes A different approach Assume 2 3 k 1 all can be factored into primes Then show that k can be factored into primes All Previous Induction To Prove k Sk Establish Base Case S0 Establish that k Sk Sk 1 Let k be any natural number Induction Hypothesis Assume j k Sj Use that to derive Sk Also called Strong Induction All Previous Induction Can Be Repackaged As Standard Induction Define Ti j i Sj Establish Base Case S0 Establish Base Case T0 Establish that k Sk Sk 1 Establish that k Tk Tk 1 Let k be any number Assume j k Sj Let k be any number Assume Tk 1 Prove Tk And there are more ways to do inductive proofs Aristotle s Contrapositive Let S be a sentence of the form A B The Contrapositive of S is the sentence B A A B When A is true B is true B …
View Full Document
Unlocking...