4.5 Treating Similar Cases

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-11-06 Teacher: Prof. Musacchio

Direct Proof

Example

• Proposition If two integers have opposite parity, then their sum is odd.

  • Proof. Suppose m and n are two integers with opposite parity. We need to show that m + n is odd. This is done in two cases, as follows.
  • Case 1.
    • Suppose $m$ is even and n is odd.
    • Thus $m=2a$ and $n=2b+1$for some integers $a$ and $b$.
    • Therefore $m+n=2a+2b+1=2(a+b)+1$, which is odd (by Definition 4.2).
  • Case 2.
    • Suppose $m$ is odd and $n$ is even.
    • Thus $m=2a+1$ and $n=2b$ for some integers $a$ and $b$.
    • Therefore $m+n=2a+1+2b=2(a+b)+1$, which is odd (by Definition 4.2).

• The phrase “Without loss of generality…” is a common way of signaling that the proof is treating just one of several nearly identical cases.