15 251 Great Theoretical Ideas in Computer Science Inductive Reasoning Lecture 3 September 4 2007 Dominoes Domino Principle Line up any number of dominos in a row knock the first one over and they will all fall Dominoes Numbered 1 to n Fk 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 1 F1 F2 F3 F1 All Dominoes Fall Standard Notation for all is written Example For all k 0 P k k 0 P k Dominoes Numbered 1 to n Fk The kth domino falls k 0 k n 1 Fk Fk 1 F0 F1 F2 F0 All Dominoes Fall The Natural Numbers N 0 1 2 3 One domino for each natural number 0 1 2 3 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 Theorem An infinite row of dominoes one domino for each natural number Knock over the first domino and they all will fall Plato s Dominoes One for each natural number Theorem An infinite row of dominoes one domino for each natural number Knock over the first domino 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 Mathematical Induction statements proved instead of dominoes fallen Infinite sequence of dominoes Infinite sequence of statements S0 S1 Fk domino k fell Fk Sk proved Establish 1 F0 2 For all k Fk Fk 1 Conclude that Fk is true for all k Inductive Proofs To Prove k N Sk Establish Base Case S0 Establish that k Sk Sk 1 k Sk Sk 1 Assume hypothetically that Sk for any particular k Conclude that Sk 1 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 2k 1 when k 0 Sn is the statement that 1 3 5 2k 1 2n 1 n2 Establishing that n 1 Sn Sn 1 3 5 2k 1 2n 1 n2 Establishing that n 1 Sn Sn 1 3 5 2k 1 2n 1 n2 Establishing that n 1 Sn Sn 1 3 5 2k 1 2n 1 n2 Base Case S1 Domino Property Assume Induction Hypothesis Sk That means 1 3 5 2k 1 k2 1 3 5 2k 1 2k 1 k2 2k 1 Sum of first k 1 odd numbers k 1 2 Theorem The sum of the first n odd numbers is n2 Primes A natural number n 1 is a prime if it has no divisors besides 1 and itself Note 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 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 This shows a technical point about 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 Theorem Every natural number 1 can be factored into primes All Previous Induction To Prove k Sk Establish Base Case S0 Establish Domino Effect Assume j k Sj use that to derive Sk All Previous Induction Also called Strong To Prove k Sk Induction Establish Base Case S0 Establish Domino Effect Assume j k Sj use that to derive Sk All Previous Induction Repackaged As Standard Induction Define Ti j i Sj Establish Base Case S0 Establish Base Case T0 Establish Domino Effect Establish that k Tk Tk 1 Let k be any number Assume Tk 1 Let k be any number Assume j k Sj Prove Sk Prove Tk And there are more ways to do inductive proofs Method of Infinite Descent Show that for any counter example you find a smaller one Pierre de Fermat If a counter example exists there would be an infinite sequence of smaller and smaller counter examples Theorem Every natural number 1 can be factored into primes Let n be a counter example Hence n is not prime so n ab If both a and b had prime factorizations then n would too Thus a or b is a smaller counter example Theorem Every natural number 1 can be factored into primes Let n be a counter example Hence n is not prime so n ab If both a and b had prime factorizations then n would too Thus a or b is a smaller counter example 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 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 We seek to prove that statement S is true of all future worlds Argue that S is true of the initial world Show that if S is true of some world then S remains true after one permissible operation is performed 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 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 Inductive reasoning is the high level idea Standard Induction All Previous Induction Least Counter example Invariants all just different packaging 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 Inductive Definition Example Initial Condition or Base Case F 0 1 Inductive definition of the powers of 2 Inductive Rule For n 0 F n F n 1 F n 1 n 0 1 2 3 F …
View Full Document
Unlocking...