115-251Great Theoretical Ideas in Computer Science15-251Proof Techniques for Computer ScientistsLecture 2 (August 28, 2008)Inductive ReasoningInductionThis is the primary way we’llThis is the primary way we’ll1.1. prove theoremsprove theorems2.2. construct and define objectsconstruct and define objects2DominoesDomino Principle: Line up any number of dominos in a row; knock the first one over and they will all falln dominoes numbered 1 to nFFkk≡≡ The The kkththdomino fallsdomino fallsIf If we set them all up in a row then we we set them all up in a row then we know that each one is set up to know that each one is set up to knock over the next one:knock over the next one:For For all 1 ≤ k < n:all 1 ≤ k < n:FFkk⇒⇒ FFk+1k+1n dominoes numbered 1 to nFFkk≡≡ The The kkththdomino fallsdomino fallsFor all 1 ≤ k < n:For all 1 ≤ k < n:FFkk⇒⇒ FFk+1k+1F1⇒ F2⇒ F3⇒ …F1⇒ All Dominoes Falln dominoes numbered 0 to n-1FFkk≡≡ The The kkththdomino fallsdomino fallsFor all 0 ≤ k < nFor all 0 ≤ k < n--1:1:FFkk⇒⇒ FFk+1k+1F0⇒ F1⇒ F2⇒ …F0⇒ All Dominoes Fall3The Natural NumbersNN = { 0, 1, 2, 3, . . .}= { 0, 1, 2, 3, . . .}The Natural NumbersNN = { 0, 1, 2, 3, . . .}= { 0, 1, 2, 3, . . .}One domino for each natural number:One domino for each natural number:0 1 2 3 4 5 ….Plato: 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 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:4Mathematical 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, Sk1. Establish “Base Case”: S02. Establish that ∀∀∀∀k, Sk⇒ Sk+1To proveTo proveTo proveTo prove∀∀∀∀k, Sk⇒ Sk+1Assume hypothetically that Skfor any particular k; Conclude that Sk+1Theorem?The sum of the first n odd numbers is n2Check on small values:Theorem?The sum of the first n odd numbers is n2Check on small values:1 = 11+3 = 41+3+5 = 91+3+5+7 = 165Theorem?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 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 n26Inductive ProofsTo Prove ∀∀∀∀k ∈∈∈∈ N, Sk1. Establish “Base Case”: S02. Establish that ∀∀∀∀k, Sk⇒ Sk+1To proveTo proveTo proveTo prove∀∀∀∀k, Sk⇒ Sk+1Assume hypothetically that Skfor any particular k; Conclude that Sk+1Primes: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 n > 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 induction7Theorem?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 primesAll Previous InductionTo Prove ∀∀∀∀k, SkEstablish Base Case: S0Establish Domino Effect:Assume ∀∀∀∀j<k, Sjuse that to derive SkEstablish Domino Effect:Assume ∀∀∀∀j<k, Sjuse that to derive SkEstablish Base Case: S0All Previous InductionTo Prove ∀∀∀∀k, SkSometimes called “Strong Induction”It’s really a repackaging of regular inductionLet 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 Tk8Regular InductionAll-previous Induction And there are more ways to do inductive proofs Method of Infinite DescentShow that for any counter-example you can find a smaller onePierre de FermatHence, if 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-exampleMethod of Infinite DescentShow that for any counter-example you can find a smaller onePierre de FermatHence, if a counter-example exists there would be an infinite sequence of smaller and smaller counter examples9Regular InductionAll-previous Induction Infinite DescentAnd one more way of packaging induction…InvariantsInvariant (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 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 worlds10Odd/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
View Full Document
Unlocking...