Proof by Cases

Proof by Cases: In proving a mathematical statement \(P(x) \implies Q(x)\) where \(x \in \mathbb{S}\), sometimes \(x\) has more than one dijoint property. It may be helpful to separately prove \(P(x) \implies Q(x)\) for each different property of \(x\). This is called Proof by Cases.

Examples:

  • For \(n \in \mathbb{Z}\), \(n\) is even or \(n\) is odd.
  • For \(x, y \in \mathbb{R}, x \neq 0, y \neq 0\), \(xy > 0\) or \(xy < 0\).
    • alternatively..
    • \((x > 0 \text{ and } y > 0)\) or \((x < 0 \text{ and } y < 0)\) or \((x > 0 \text{ and } y < 0)\) or \((x < 0 \text{ and } y > 0)\)

Result 3.15: If \(n \in \mathbb{Z}\), then \(n^2 + 3n+5\) is odd.

Proof: Assume \(n \in \mathbb{Z}\).

  • Notice that \(n\) can only be even or odd. If we prove the theorem for both cases, we've proven the theorem generally. Let the conclusion guide you!
  • The parity of \(n\) is relevant only because the parity of an expression depending on \(n\) is relevant.
  • Case 1: \(n\) is even, so \(n = 2k, k \in \mathbb{Z}\). \[ \begin{align} n^2 + 3n + 5 &= (2k)^2+3(2k)+4+1\\ &= 2(2k^2+3k+2)+1 \end{align} \]
    • So \(n^2+3n+5\) is odd.
  • Case 2: \(n\) is odd, so \(n = 2k+1, k \in \mathbb{Z}\). \[ \begin{align} n^2 + 3n + 5 &= (2k+1)^2+3(2k+1)+5\\ &= 4k^2 + 4k + 1 + 6k + 3 + 5\\ &= 4k^2 + 10k + 9\\ &= 2(2k^2 + 5k + 4) + 1 \end{align} \]
    • So \(n^2+3n+5\) is odd. \(\blacksquare\)

An even-ness - oddness tale:

Parity: Let \(x, y \in \mathbb{Z}\). \(x\) and \(y\) are of the same parity if both are even or both are odd. Otherwise, \(x\) and \(y\) are of opposite parity.

Theorem 3.16: let \(x, y \in \mathbb{Z}\). \(x\) and \(y\) are of the same parity \(\iff x+y\) is even.

  • If you're trying to prove a theorem based on \(x\) and \(y\) and it doesn't matter which is which, this is referred to as the theorem being symmetric in \(x\) and \(y\). This means we can swap \(x\) and \(y\) and the conclusion doesn't change. We refer to this as "Without Loss of Generality", or "WLOG".

Theorem 3.17: let \(a, b \in \mathbb{Z}\). \(ab\) is even \(\iff a\) even or \(b\) even.

  • Backwards: Assume \(a\) is even or \(b\) is even.
  • We want to show that \(ab = 2a, a \in \mathbb{Z}\).
  • WLOG, assume \(a\) is even.
    • So \(a = 2k, k \in \mathbb{Z}\).
    • Observe: \(ab = (2k)b = 2(kb)\).
    • So \(ab\) is even.
  • Forwards (by contrapositive): Assume \(a\) is odd and \(b\) is odd.
  • \(a = 2k+1, b=2j+1, k, j \in \mathbb{Z}\).
  • Observe: \[ \begin{align} ab &= (2k+1)(2j+1)\\ &= 4kj + 2k + 2j + 1\\ &= 2(2kj+k+j)+1 \end{align} \]
  • So \(ab\) is odd. \(\blacksquare\)