Great Theoretical Ideas In Computer Science Victor Adamchik Lecture 2 CS 15 251 Jan 14 2010 Spring 2010 Carnegie Mellon University Inductive Reasoning Homework must be Typeset You may use any typesetting program you wish TeX LaTeX Mathematica We Are Here to help There are many office hours throughout the week Inductive Reasoning If you have problems with the homework don t hesitate to ask for help Raise your hand if you never heard of mathematical induction American Banks Domino Principle Line up any number of dominos in a row knock the first one over and they will all fall 1 Dominoes Numbered 1 to n Plain Induction Dk 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 Dk Dk 1 D1 D2 D3 All Dominoes Fall Inductive Proofs Base Case Show that P 0 holds Induction step Assume that P k holds show that P k 1 also holds In the induction step the assumption that P k holds is called the Induction Hypothesis Suppose we have some property P k that may or may not hold for a natural number n To demonstrate that P k is true for all n is a little problematic Proof by Mathematical Induction In formal notation P 0 n P n P n 1 Instead of attacking a problem directly we only explain how to get a proof for P n 1 out of a proof for P n Theorem Induction Hypothesis The sum of the first n odd numbers is n2 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 1 3 5 2n 1 n2 2 Induction step Assume that P n holds and show that P n 1 also holds Assume 1 3 5 2n 1 n2 Prove 1 3 5 2n 1 n 1 2 1 3 5 2n 1 n2 1 3 5 2n 1 2n 1 n2 2n 1 1 3 5 2n 1 n 1 2 Soundness of Induction Soundness of Induction How do we know that this really works Proof by contradiction Assume that for some assertion P n we can establish the base case and the induction step but nonetheless it is not true that P n holds for all n So for some values of n P n is false Soundness of Induction Let n0 be the least such n Certainly n0 cannot be 0 Soundness of Induction Now by our choice of n0 this means that P n1 holds Thus it must be n0 n1 1 where n1 n0 3 Soundness of Induction Now by our choice of n0 this means that P n1 holds Soundness of Induction But then by Induction Hypothesis P n1 1 also holds because n1 n0 Soundness of Induction But then by Induction Hypothesis P n1 1 also holds Review that proof But that is the same as P n0 and we have a contradiction we can pick n0 to be the least n where P n fails Least Element Principle Every non empty subset of the natural numbers must contain a least element 4 Some Comments We have chosen to describe the induction step as moving from n to n 1 where n 0 Some Comments There is nothing sacred about the base case n 0 we could just as well start at n 11 There is the obvious alternative to change the induction step from n 1 to n where n 0 ATM Machine Proof Suppose an ATM machine has only two dollar and five dollar bills You can type in the amount you want and it will figure out how to divide things up into the proper number of two s and five s Claim The ATM can generate any output amount n 4 Base case n 4 2 two s done Proof Proof Induction step suppose the machine can already handle n 4 dollars How do we proceed for n 1 dollars Case 1 The n dollar output contains a five Case 2 The n dollar output contains only two s Then we can replace the five by 3 two s to get n 1 dollars Since n 4 there must be at least 2 two s Remove 2 and replace them by 1 five Done 5 Theorem Every natural number 1 can be factored into primes Base case 2 is prime P 2 is true This shows a technical point about mathematical induction Inductive hypothesis P n can be factored into primes Theorem Every natural number 1 can be factored into primes A different approach Assume 2 3 n 1 all can be factored into primes Then show that n can be factored into primes Theorem Every natural number n 1 can be factored into primes Base case 2 is prime P 2 is true Inductive hypothesis P j j n can be factored into primes Case 1 n is prime Case 2 n is composite n p q Strong Induction Establish Base Case P 0 Establish Domino Effect Assume j n P j use that to derive P n Faulty Induction Claim 6 n 0 for all n 0 Base step Clearly 6 0 0 Induction step Assume that 6 k 0 for all 0 k n We need to show that 6 n 1 is 0 Write n 1 a b where a b 0 6 n 1 6 a b 6 a 6 b 0 0 0 6 And there are more ways to do inductive proofs Yet another way of packaging inductive reasoning is to define invariants Invariant n 1 Not varying constant 2 Mathematics Unaffected by a designated operation as a transformation of coordinates Invariant n 3 Programming A rule such as the ordering of an ordered list that applies throughout the life of a data structure or procedure Each change to the data structure maintains the correctness of the invariant Statement The number of people of odd parity must be even Initial case Zero hands have been shaken at the start of a party so zero people have odd parity Invariant Argument If 2 people of the same parity shake they both change and hence the odd parity count changes by 2 and remains even If 2 people of different parities shake then they both swap parities and the odd parity count is unchanged 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 Inductive reasoning is the high level idea Standard Induction Strong Induction Least Element Principal Invariants all just different packaging 7 Inductive Definition Induction is also how we can define and construct our world So many things from buildings to computers are built up stage by stage module by module each depending on the previous stages A linked list is either empty list or a node followed by a linked list A binary tree …
View Full Document
Unlocking...