Great Theoretical Ideas In Computer Science Steven Rudich CS 15 251 Lecture 1 Jan 11 2005 Spring 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 Computer Scientists don t start numbering things at 1 they start at 0 YOU will spend a career doing this so GET USED TO IT NOW 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 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 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 The Infinite Domino Principle Fk The kth domino falls Suppose F0 Suppose for each natural number k Fk Fk 1 Then All Dominoes Fall F 0 F 1 F2 The Infinite Domino Principle Fk The kth domino falls Suppose F0 Suppose for each natural number k Fk Fk 1 Then All Dominoes Fall Proof If they do not all fall there must be a least numbered domino d 0 that did not fall Hence Fd 1 and not Fd Fd1 Fd Hence domino d fell and did not fall Contradiction Mathematical Induction statements proved instead of dominoes fallen Infinite sequence of dominoes Fk domino k falls Establish 1 F0 Infinite sequence of statements S0 S1 Fk Sk proved 2 8 k Fk Fk 1 Conclude that Fk is true for all k Inductive Proof Reasoning To Prove k Sk Establish Base Case S0 Establish Domino Property k Sk Sk 1 k Sk Sk 1 Assume hypothetically that Sk for any particular k Conclude that Sk 1 Inductive Proof Reasoning To Prove k Sk Establish Base Case S0 Establish Domino Property k Sk Sk 1 Induction Hypothesis Sk k Sk Sk 1 Use I H to show Sk 1 Inductive Proof Reasoning To Prove k b Sk Establish Base Case Sb Establish Domino Property k b Sk Sk 1 Assume k b Assume Inductive Hypothesis Sk Theorem The sum of the first n odd numbers is n2 Theorem The sum of the first n odd numbers is n2 CHECK IT OUT 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 k n 2k 1 1 3 5 2k 1 2n1 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 Base case S1 is true The sum of the first 1 odd numbers is 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 Assume Induction Hypothesis Sk for any particular k 1 1 3 5 2k 1 k2 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 CONCLUSE 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 Established base case S1 Established domino property 8 k 1 Sk Sk 1 By induction of n we conclude that 8n 1 Sn THEOREM The sum of the first n odd numbers is n2 Theorem The sum of the first n numbers is n n 1 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 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 n Let Sn 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 Domino Property 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 THEOREM The sum of the first n numbers is n n 1 A natural number n 1 is prime if it has no divisors besides 1 and itself N B 1 is not considered prime Easy theorem Every natural number 1 can be factored into primes N B It is much more subtle to argue for the existence of a unique prime factorization Easy theorem Every natural number 1 can be factored into primes Sn n can be factored into primes S2 is true because 2 is prime Every natural number 1 can be factored into primes Base case 2 Assume 2 3 k 1 all can be factored into primes Show k can be factored into primes Assume 2 3 k 1 all can be factored into primes Show k can be factored into primes If k is prime we are done If not k ab where 1 a b k hence a and b can be factored into primes Thus k is the product of the factors of a and the factors of b This illustrates a technical point about using and defining mathematical induction 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 Derive Sk Strong Induction To Prove …
View Full Document
Unlocking...