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.</li> </ul> <h4 id="morecomplicatedexampleperfectcubes">More Complicated Example: Perfect Cubes</h4> <ul> <li><strong>Claim:</strong> Every perfect cube is one more or one less than a multiple of 9.<ul> <li>$(a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$</li></ul></li> <li><strong>Proof:</strong><ul> <li>Every integer$n$is one of the following:<ul> <li>A multiple of 3.</li> <li>One more than a multiple of 3.</li> <li>Two more than a multiple of 3.</li></ul></li></ul></li> </ul> <h5 id="case1ddnddisamultipleof3">Case 1:$n$is a multiple of 3</h5> <ul> <li>$n = 3k$for some integer$k$(i.e.,$n \mod 3 = 0$).</li> <li>$n^3 = (3k)^3 = 27k^3 = 9(3k^3)$</li> <li>Since$3k^3$is an integer,$n^3$is a multiple of 9.</li> </ul> <h5 id="case2ddnddisonemorethanamultipleof3">Case 2:$n$is one more than a multiple of 3</h5> <ul> <li>$n = 3k + 1$for some integer$k$(i.e.,$n \mod 3 = 1$).</li> <li>$n^3 = (3k + 1)^3 = 27k^3 + 27k^2 + 9k + 1 = 9(3k^3 + 3k^2 + k) + 1$</li> <li>Since$3k^3 + 3k^2 + k$is an integer,$n^3$is one more than a multiple of 9.</li> </ul> <h5 id="case3ddnddistwomorethanamultipleof3">Case 3:$n$is two more than a multiple of 3</h5> <ul> <li>$n = 3k + 2$for some integer$k$(i.e.,$n \mod 3 = 2$).</li> <li>$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$</li> <li>Since$3k^3 + 6k^2 + 4k + 1$is an integer,$n^3$is one less than a multiple of 9.</li> </ul> <h5 id="commentoncasestructures">Comment on Case Structures</h5> <ul> <li>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.