Proofs and Examples

Proofs

Simple Example: Odd Numbers

• Claim: If $n$ is odd, then $n^2$ is odd.
• Proof:
  • Assume $n$ is odd.
  • Then, we can write $n = 2k + 1$ for some integer $k$ (universal quantifier implied).
  • It follows that: $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$
  • Note that since $k$ is an integer, $2k^2 + 2k$ is also an integer.
  • Hence, $n^2$ is one more than twice an integer, so $n^2$ is odd.
• The square symbol ($\blacksquare) or QED are commonly used as end-of-proof symbols.

More Complicated Example: Perfect Cubes

• Claim: Every perfect cube is one more or one less than a multiple of 9.
  • (a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3
• Proof:
  • Every integer n is one of the following:
    • A multiple of 3.
    • One more than a multiple of 3.
    • Two more than a multiple of 3.

Case 1: n is a multiple of 3

• n = 3k$for some integer$k$(i.e.,$n \mod 3 = 0).
• n^3 = (3k)^3 = 27k^3 = 9(3k^3)
• Since 3k^3$is an integer,$n^3 is a multiple of 9.

Case 2: n is one more than a multiple of 3

• n = 3k + 1$for some integer$k$(i.e.,$n \mod 3 = 1).
• n^3 = (3k + 1)^3 = 27k^3 + 27k^2 + 9k + 1 = 9(3k^3 + 3k^2 + k) + 1
• Since 3k^3 + 3k^2 + k$is an integer,$n^3 is one more than a multiple of 9.

Case 3: n is two more than a multiple of 3

• n = 3k + 2$for some integer$k$(i.e.,$n \mod 3 = 2).
• n^3 = (3k + 2)^3 = 27k^3 + 54k^2 + 36k + 8 = 27k^3 + 54k^2 + 36k + 9 - 1 = 9(3k^3 + 6k^2 + 4k + 1) - 1
• Since 3k^3 + 6k^2 + 4k + 1$is an integer,$n^3 is one less than a multiple of 9.

Comment on Case Structures

• The proof was broken into cases based on the remainder when n$$ is divided by 3.
• When faced with such problems, ask yourself, "How would I know to try this?"
• The intuition about what case structure will work often develops this semester.
  • Start by trying odd/even (i.e., remainder when we divide by 2).
  • If that doesn't work, try others.