COMP 61: Discrete Math

Lecture 7: Week 4, Thursday, February 6

• Covered: Proof by smallest counterexample
• Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
  • 61-7-condensed.pdf
  • 61-7-full.pdf
• Textbook sources
  • Scheinerman: chapter 4, section 21.
• Links
  • Fibonacci numbers
    • Fibonacci rabbits.
    • TED talk.
    • wiki. (see sections 13-15).
    • xkcd 587
  • Proof by smallest counterexample requires that you are able to "pick a smallest", meaning you have to be able to order your set of (counter)examples. This is what the well ordering principle is about (note that you will find that discussed in your book). If you have trouble providing an order to all potential instances of a problem, then trying proof by counterexample is not a good idea. On the other hand, you could try "proof by intimidation" as in: xkcd 982 (make sure to mouse-over for an explanation). The actual use of "proof by intimidation" is given here. A special case is the famous Chewbacca defense.
• Further comments
  • As mentioned in class, the main lesson of this week was how to set up a proof (by contradiction, or smallest counterexample). Getting the algebra to work in the last steps is (slightly) less important. Also, by no means are you required to learn how to prove theorems that require geometric thinking. We'll get to similar things in April though.
  • When you do prove something by contradiction, on your homework, an exam, whenever, state so at the beginning of your proof. Something like "Assume, for sake of contradiction, that (bla)". Or, "We will use proof by contradiction. Assume that the claim is not true. Then (bla)...".