Direct Proofs

Direct Proof: In a direct proof of \(P(x) \implies Q(x)\) we consider an arbitrary element \(x\) for which \(P(x)\) is true and logically deduce that, for this \(x, Q(x)\) is also true.

Familiar Integer Facts We Assume

  • the negation of an integer is an integer
  • the sum, difference, or product of integers is an integer.

Even: An integer \(n\) is even if \(n=2k\) for some \(k \in \mathbb{Z}\)

Odd: An integer \(n\) is odd if \(n=2k+1\) for some \(k \in \mathbb{Z}\)

Result 3.4: If \(n\) is an odd integer, then \(3n+7\) is an even integer.

Proof:

  • Assume \(n\) is an odd integer.
  • So \(n = 2k+1, k \in \mathbb{Z}\).
  • We want to show that \(3n+1 = 2a, where a \in \mathbb{Z}\)
  • Observe (look!): \[ \begin{align} 3n+7 &= 3(2k+1)+7\\ &= 6k+10\\ &= 2(3k+5)\\ \end{align} \]
  • Noting that \(3k+5 \in \mathbb{Z}\), 3n+7 is even. \(\blacksquare\)

General Steps

  1. Begin with the hypotehsis
  2. Deduce what you can from the hypothesis
  3. State your goal/conclusion
  4. PROVE the goal!
    • Be guided by the upcoming conclusion
  5. End with the conclusion.

Result 3.6: If \(n\) is an odd integer, then \(4n^3+2n-1\) is odd.

Proof:

  • Assume \(n\) is an odd integer.
  • So \(n = 2y+1, y \in \mathbb{Z}\).
  • We want to show that \(4n^3+2n-1 = 2a + 1, a \in \mathbb{Z}\).
  • Observe:

\[ \begin{align} 4n^3 + 2n - 1 &= 4(2y+1)^3+2(2y+1)-1\\ &= 2\left[2(2y+1)^3+(2y+1) - 1\right] + 1 \end{align} \]

  • Thus, \(4n^3+2n-1\) is odd. \(\blacksquare\)