CompSci 102 © Michael Frank8.1Today’s topics••Mathematical reasoningMathematical reasoning– More proof techniques– Sequences– Summations••Reading: Sections 3.1-3.2Reading: Sections 3.1-3.2••UpcomingUpcoming––InductionInductionCompSci 102 © Michael Frank8.2Forward Reasoning••Have premises Have premises pp, and want to prove , and want to prove qq..––Find a Find a ss11 such that such that ppss11••Then, modus Then, modus ponens ponens gives you gives you ss11..––Then, find an Then, find an ss22 (such that)(such that) ss11ss22..••Then, modus Then, modus ponens ponens gives you gives you ss22..––And hope to eventually get to an And hope to eventually get to an ssnn ssnnqq..••The problem with this method isThe problem with this method is……––It can be tough to see the path looking from It can be tough to see the path looking from pp..CompSci 102 © Michael Frank8.3Backward Reasoning••It can often be easier to see the It can often be easier to see the very same pathvery same path if you just if you juststart looking from the conclusion start looking from the conclusion qq instead instead……––That is, That is, firstfirst find an find an ss11 such that such that ss11qq..––ThenThen, find an , find an ss22 ss22ss11, and so on, and so on……––Working back to an Working back to an ssnn ppssnn..••Note we Note we stillstill are using are using modus modus ponensponens to propagate truth to propagate truthforwardsforwards down the chain from down the chain from pp to to ssnn to to …… toto ss11 to to qq!!––We are We are findingfinding the chain the chain backwardsbackwards, but , but applyingapplying it it forwardsforwards..––This is not quite the same thing as an indirect proofThis is not quite the same thing as an indirect proof……••In that, we would use In that, we would use modus modus tollenstollens and ¬ and ¬qq to prove ¬ to prove ¬ss11, , etc.etc.––However, it However, it itit similar. similar.CompSci 102 © Michael Frank8.4Backward Reasoning Example••Theorem:Theorem:aa>0,>0,bb>0,>0,aabb: (: (aa++bb)/2 > ()/2 > (abab))1/21/2..••Proof:Proof:––Notice it is not obvious how to go from theNotice it is not obvious how to go from thepremises premises aa>>00, , bb>0>0, , aabb directly forward to the directly forward to theconclusion conclusion ((aa++bb)/2 > ()/2 > (abab))1/21/2..––So, letSo, let’’s work s work backwardsbackwards from the conclusion, from the conclusion,((aa++bb)/2 > ()/2 > (abab))1/21/2 !!Example 1CompSci 102 © Michael Frank8.5Stone Game Example••Game rules:Game rules:––There are 15 stones in a pile. Two players take turnsThere are 15 stones in a pile. Two players take turnsremoving either 1, 2, or 3 stones. Whoever takes theremoving either 1, 2, or 3 stones. Whoever takes thelast stone wins.last stone wins.••Theorem:Theorem: There is a strategy for the first player There is a strategy for the first playerthat guarantees him a win.that guarantees him a win.••How do we prove this? Constructive proofHow do we prove this? Constructive proof……––Looks complicatedLooks complicated…… How do we pick out the winning How do we pick out the winningstrategy from among all possible strategies?strategy from among all possible strategies?••Work backwards from the endgame!Work backwards from the endgame!Example 2CompSci 102 © Michael Frank8.6Working Backwards in the Game••Player 1 wins if it is player 2Player 1 wins if it is player 2’’s turn and there ares turn and there areno stonesno stones……••P1 can arrange this ifP1 can arrange this ifit is his turn, and thereit is his turn, and thereare 1, 2, or 3 stonesare 1, 2, or 3 stones……••This will be true asThis will be true aslong as player 2 hadlong as player 2 had4 stones on his turn4 stones on his turn……••And so onAnd so on……9, 10, 119, 10, 111212885, 6, 75, 6, 74413, 14, 1513, 14, 151, 2, 31, 2, 300Player 2Player 2Player 1Player 1CompSci 102 © Michael Frank8.7“Forwardized” version••Theorem.Theorem. Whoever moves first can always force a win. Whoever moves first can always force a win.––Proof.Proof. Player 1 can remove 3 stones, leaving 12. After player 2 Player 1 can remove 3 stones, leaving 12. After player 2moves, there will then be either 11, 10, or 9 stones left. In any ofmoves, there will then be either 11, 10, or 9 stones left. In any ofthese cases, player 1 can then reduce the number of stones to 8.these cases, player 1 can then reduce the number of stones to 8.Then, player 2 will reduce the number to 7, 6, or 5. Then, playerThen, player 2 will reduce the number to 7, 6, or 5. Then, player1 can reduce the number to 4. Then, player 2 must reduce them to1 can reduce the number to 4. Then, player 2 must reduce them to3, 2, or 1. Player 1 then removes the remaining stones and wins.3, 2, or 1. Player 1 then removes the remaining stones and wins.CompSci 102 © Michael Frank8.8Proof by Cases Example••Theorem:Theorem: nnZZ ¬(¬(2|2|nn 3 3|n|n) ) 24|(24|(nn2211))––Proof:Proof: Since Since 2·3=62·3=6, the value of , the value of nn mod 6 mod 6 is sufficient is sufficientto tell us whether to tell us whether 2|2|nn or or 3|3|nn. If . If ((nn mod 6) mod 6){0,3}{0,3} then then3|3|nn; if it is in ; if it is in {0,2,4}{0,2,4} then then 2|2|nn. Thus . Thus ((nn mod 6) mod 6){1,5}{1,5}..••Case #1: Case #1: If If nn mod 6 = 1 mod 6 = 1, then , then ((kk) ) nn=6=6kk+1+1..nn22=36=36kk22+12+12kk+1+1, so , so nn2211=36=36kk22+12+12kk = 12(3 = 12(3kk+1)+1)kk. Note. Note2|(32|(3kk+1)+1)kk since either since either kk or or 33kk+1+1 is even. Thus is even. Thus 24|(24|(nn2211))..••Case #2:Case #2: If If nn mod 6 = 5 mod 6 = 5, then , then nn=6=6kk+5+5. . nn2211 = ( = (nn11)·()·(nn+1)+1)= (6= (6kk+4)·(6+4)·(6kk+6) = 12·(3+6) = 12·(3kk+2)·(+2)·(kk+1)+1). Either . Either kk+1+1 or or 33kk+2+2 is iseven. Thus, even. Thus, 24|(24|(nn2211))..Example 3CompSci 102 © Michael Frank8.9Proof by Examples?••A universal statement can A universal statement can nevernever be proven be provenby using examples, by using examples, unlessunless the universe can the
View Full Document
Unlocking...