15-251Great Theoretical Ideas in Computer ScienceLecture 3 (September 4, 2007)Inductive ReasoningDominoesDomino Principle: Line up any number of dominos in a row; knock the first one over and they will all fallDominoes Numbered 1 to nFk= “The kthdomino 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+1F1⇒ F2⇒ F3⇒ …F1⇒ All Dominoes FallStandard Notation“for all” is written “∀”Example:For all k>0, P(k)∀ k>0, P(k)=Dominoes Numbered 1 to nFk= “The kthdomino falls”∀k, 0 ≤ k < n-1:Fk⇒ Fk+1F0⇒ F1⇒ F2⇒ …F0⇒ All Dominoes FallThe Natural NumbersOne domino for each natural number:0123…= { 0, 1, 2, 3, . . . }NPlato: 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 numberTheorem: An infinite row of dominoes, one domino for each natural number.Knock over the first domino and they all will fallPlato’s DominoesOne for each natural numberTheorem: An infinite row of dominoes, one domino for each natural number.Knock over the first domino and they all will fallSuppose 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.Proof:Mathematical Inductionstatements proved instead ofdominoes fallenInfinite sequence ofdominoesInfinite sequence of statements: S0, S1, …Fk= “domino k fell” Fk= “Skproved”Conclude that Fkis true for all kEstablish: 1. F02. For all k, Fk⇒ Fk+1Inductive ProofsTo Prove ∀k ∈ N, SkEstablish “Base Case”: S0Establish that ∀k, Sk⇒ Sk+1∀k, Sk⇒ Sk+1Assume hypothetically that Skfor any particular k; Conclude that Sk+1Theorem?The sum of the first n odd numbers is n2Theorem?The sum of the first n odd numbers is n2Check on small values:1= 11+3 = 41+3+5 = 91+3+5+7 = 16Theorem?The sum of the first n odd numbers is n2The kthodd number is (2k – 1), when k > 0Snis the statement that: “1+3+5+(2k-1)+...+(2n-1) = n2”Sn= “1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2”Establishing that ∀n ≥ 1 SnSn= “1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2”Establishing that ∀n ≥ 1 SnSn= “1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2”Establishing that ∀n ≥ 1 SnBase Case: S1Assume “Induction Hypothesis”: SkThat means: 1+3+5+…+ (2k-1) = k21+3+5+…+ (2k-1)+(2k+1) = k2 +(2k+1)Sum of first k+1 odd numbers = (k+1)2Domino Property:TheoremThe sum of the first n odd numbers is n2Primes:Note: 1 is not considered primeA natural number n > 1 is a prime if it has no divisors besides 1 and itselfTheorem?Every natural number > 1 can be factored into primesSn= “n can be factored into primes”Base case:2 is prime ⇒ S2is trueSk-1= “k-1 can be factored into primes”How do we use the fact:Sk= “k can be factored into primes”to prove that:This shows a technical point about mathematical inductionTheorem?Every natural number > 1 can be factored into primesA different approach:Assume 2,3,…,k-1 all can be factored into primesThen show that k can be factored into primesTheorem?Every natural number > 1 can be factored into primesAll Previous InductionTo Prove ∀k, SkEstablish Base Case: S0Establish Domino Effect:Assume ∀j<k, Sjuse that to derive SkAll Previous InductionTo Prove ∀k, SkEstablish Base Case: S0Establish Domino Effect:Assume ∀j<k, Sjuse that to derive SkAlso called “Strong Induction”Let k be any number“All Previous” InductionRepackaged AsStandard InductionEstablish Base Case: S0Establish Domino Effect:Let k be any numberAssume ∀j<k, SjProve SkDefine Ti= ∀j ≤ i, SjEstablish Base Case T0Establish that ∀k, Tk⇒ Tk+1Assume Tk-1Prove TkAnd there are more ways to do inductive proofsMethod of Infinite DescentShow that for any counter-example you find a smaller onePierre de FermatIf a counter-example exists there would be an infinite sequence of smaller and smaller counter-examplesTheorem:Every natural number > 1 can be factored into primesLet n be a counter-exampleHence n is not prime, so n = abIf both a and b had prime factorizations, then n would tooThus a or b is a smaller counter-exampleTheorem:Every natural number > 1 can be factored into primesLet n be a counter-exampleHence n is not prime, so n = abIf both a and b had prime factorizations, then n would tooThus a or b is a smaller counter-exampleInvariant (n): 1. Not varying; constant. 2. Mathematics.Unaffected by a designated operation, as a transformation of coordinates.Yet another way of packaging inductive reasoning is to define “invariants”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 invariantInvariant InductionSuppose we have a time varying world state: W0, W1, W2, …Argue that S is true of the initial worldShow that if S is true of some world –then S remains true after one permissible operation is performedEach state change is assumed to come from a list of permissible operations. We seek to prove that statement S is true of all future worldsOdd/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 shakenStatement: The number of people of odd parity must be evenIf 2 people of the same parity shake, they both change and hence the odd parity count changes by 2 – and remains evenStatement: The number of people of odd parity must be evenInitial case: Zero hands have been shaken at the start of a party, so zero people have odd parityInvariant Argument:If 2 people of different parities shake, then they both swap parities and the odd parity count is unchangedInductive reasoning is the high level idea“Standard” Induction“All Previous” Induction “Least Counter-example”“Invariants”all just different packagingInduction is also how we can define and construct our worldSo many things, from buildings to computers, are built up stage by stage, module by module, each depending on the previous stagesn 01234567F(n)Inductive DefinitionExampleInitial Condition, or Base Case:F(0) = 1Inductive Rule:For n > 0, F(n) = F(n-1) + F(n-1)1 2 4 8 16 32 64 128Inductive definition of the powers of 2!Leonardo FibonacciIn 1202, Fibonacci proposed a problem about the
View Full Document
Unlocking...