Proof by cases and counterexamples

Sometimes a single argument cannot cover every situation, but a few separate arguments together can. An integer is even or odd; a real number is positive, zero or negative; a remainder on division by 3 is 0, 1 or 2. Proof by cases splits the hypothesis into such pieces and proves the conclusion in each. This lesson also covers the other side of proving: disproving. A general claim is overturned by a single counterexample, and finding good counterexamples is as much a part of mathematics as writing proofs.

The logic of cases

Proof by cases rests on the tautology \(((A \vee B) \wedge (A \implies Q) \wedge (B \implies Q)) \implies Q\). If at least one of \(A\) and \(B\) holds, and each of them leads to \(Q\), then \(Q\) holds. The same works with any finite number of cases. Two things must be checked: that the cases are exhaustive, so that every possibility falls into at least one, and that each case really does lead to the conclusion. The cases do not have to be mutually exclusive, though they usually are.

Theorem. For every integer \(n\), \(n^2 + n\) is even.

Proof. Let \(n\) be an integer. Every integer is even or odd, so there are two cases. Case 1: \(n\) is even, say \(n = 2k\). Then \(n^2 + n = 4k^2 + 2k = 2(2k^2 + k)\), which is even. Case 2: \(n\) is odd, say \(n = 2k + 1\). Then \(n^2 + n = (4k^2 + 4k + 1) + (2k + 1) = 2(2k^2 + 3k + 1)\), which is even. In both cases \(n^2 + n\) is even. \(\blacksquare\)

There is also a slicker proof without cases: \(n^2 + n = n(n + 1)\) is a product of consecutive integers, one of which is even. But that argument itself hides a case split (which of the two factors is even). Cases are often the most honest way to organize a proof, and it is worth knowing how to find the right split.

Choosing the cases

The right cases depend on the problem. For statements about parity, split into even and odd. For divisibility by \(m\), split by remainder: \(n = mq + r\) for \(r = 0, 1, \dots, m - 1\). For absolute values, split by sign. For maxima and minima, split according to which quantity is larger. For a statement about two numbers, sometimes four cases are needed: both even, both odd, and two mixed cases.

In lesson 1 we saw by computer that a sum of two odd squares is never a perfect square. Here is the proof, using cases on remainders modulo 4.

Theorem. If \(a\) and \(b\) are odd integers, then \(a^2 + b^2\) is not a perfect square.

Proof. First, every perfect square leaves remainder 0 or 1 on division by 4 (lesson 4), by cases on whether the number being squared is even or odd. Now let \(a = 2j + 1\) and \(b = 2k + 1\). Then \(a^2 + b^2 = 4(j^2 + j + k^2 + k) + 2\), which leaves remainder 2 on division by 4. A perfect square cannot leave remainder 2, so \(a^2 + b^2\) is not a perfect square. \(\blacksquare\)

Note that the case analysis happened inside the lemma about squares. Breaking a proof into a lemma that uses cases and a main argument that uses the lemma keeps each part short.

Absolute value and the triangle inequality

The absolute value is defined by cases: \(|x| = x\) if \(x \ge 0\) and \(|x| = -x\) if \(x < 0\). Proofs about absolute values therefore tend to use cases on signs. Two facts follow quickly: \(-|x| \le x \le |x|\) for every real \(x\), and \(|xy| = |x||y|\).

Theorem (triangle inequality). For all real numbers \(x\) and \(y\), \(|x + y| \le |x| + |y|\).

Proof. We know \(-|x| \le x \le |x|\) and \(-|y| \le y \le |y|\). Adding these gives \(-(|x| + |y|) \le x + y \le |x| + |y|\). Now consider two cases. If \(x + y \ge 0\), then \(|x + y| = x + y \le |x| + |y|\) by the right-hand inequality. If \(x + y < 0\), then \(|x + y| = -(x + y) \le |x| + |y|\) by the left-hand inequality. In both cases \(|x + y| \le |x| + |y|\). \(\blacksquare\)

The triangle inequality is one of the most used inequalities in analysis. In MATH-241 you will use it in nearly every proof about limits, usually in the form \(|a - c| \le |a - b| + |b - c|\), which says that going from \(a\) to \(c\) directly is never longer than going via \(b\).

Without loss of generality

When two cases are mirror images of each other, mathematicians often prove one and say the other is the same. The phrase is 'without loss of generality', abbreviated WLOG. For example, in a proof about two integers \(a\) and \(b\) where exactly one is even, we may say 'without loss of generality, \(a\) is even and \(b\) is odd', because the case where \(b\) is even and \(a\) is odd is the same argument with the letters swapped.

WLOG is only legitimate when the omitted cases really are symmetric to the one treated. If the statement treats \(a\) and \(b\) differently, as in '\(a\) divides \(b^2\)', swapping the letters changes the problem and WLOG is not allowed. When you use the phrase, make sure a careful reader could see why the other cases follow.

Proving 'or' statements

To prove a statement of the form \(P \implies (Q \vee R)\), a neat trick avoids cases: assume \(P\) and \(\neg Q\), and prove \(R\). This works because \(Q \vee R\) is equivalent to \(\neg Q \implies R\). For example, to prove 'if \(ab = 0\) then \(a = 0\) or \(b = 0\)' for real numbers, assume \(ab = 0\) and \(a \ne 0\); then \(a\) has an inverse and \(b = a^{-1}(ab) = a^{-1} \cdot 0 = 0\).

Counterexamples

A universal statement 'for all \(x\), \(P(x)\)' is false if even one \(x\) fails, and such an \(x\) is a counterexample. To disprove a claim, give the counterexample explicitly and verify that it fails. No further argument is needed; in particular you do not have to explain why the claim seemed plausible.

• Claim: for all integers \(n\), \(n^2 - n + 11\) is prime. Counterexample: \(n = 11\) gives \(121 = 11^2\).

• Claim: if \(a \mid bc\) then \(a \mid b\) or \(a \mid c\). Counterexample: \(a = 6\), \(b = 2\), \(c = 3\). Then \(6 \mid 6\), but \(6 \nmid 2\) and \(6 \nmid 3\). (The claim is true when \(a\) is prime; that is Euclid's lemma.)

• Claim: for all real \(x\), \(\sqrt{x^2} = x\). Counterexample: \(x = -3\) gives \(\sqrt{9} = 3 \ne -3\). The correct identity is \(\sqrt{x^2} = |x|\).

• Claim: if \(f\) and \(g\) are functions with \(f(x) < g(x)\) for all \(x\), then \(f(x)^2 < g(x)^2\). Counterexample: \(f(x) = -2\), \(g(x) = 1\).

Good counterexamples are usually simple and come from the edges of the hypothesis: zero, one, negative numbers, very small or very large values, equal values, or a non-prime where the claim quietly needed a prime. When you suspect a claim is false, try these first.

Be careful about what a counterexample can and cannot do. It disproves a universal statement. It does not disprove an existential statement: 'some prime is even' is not disproved by the prime 3. And it says nothing about a weaker or modified claim, which might still be true. Often the most interesting mathematics happens after a counterexample, when you ask what extra hypothesis would make the claim true.

Searching for counterexamples by computer

A computer search is an efficient way to look for counterexamples before attempting a proof. The code below checks four claims over a range of values. It reports the first counterexample it finds, or says that none turned up. Remember the asymmetry: one counterexample settles a claim, while a clean search only means it might be true.

from fractions import Fraction as F

def is_prime(m):
    return m > 1 and all(m % d for d in range(2, int(m ** 0.5) + 1))

claims = {
    "n^2 - n + 11 is prime":           (range(0, 200), lambda n: is_prime(n * n - n + 11)),
    "n^2 + n is even":                 (range(-200, 200), lambda n: (n * n + n) % 2 == 0),
    "a|bc implies a|b or a|c":         ([(a, b, c) for a in range(2, 20) for b in range(1, 20) for c in range(1, 20)],
                                        lambda t: (t[1] * t[2]) % t[0] != 0 or t[1] % t[0] == 0 or t[2] % t[0] == 0),
    "x^2 >= x for rationals x":        ([F(k, 4) for k in range(-12, 13)], lambda x: x * x >= x),
}

for name, (domain, test) in claims.items():
    bad = next((x for x in domain if not test(x)), None)
    print(f"{name:32s} ->", "no counterexample found" if bad is None else f"counterexample {bad}")

n^2 - n + 11 is prime            -> counterexample 11
n^2 + n is even                  -> no counterexample found
a|bc implies a|b or a|c          -> counterexample (4, 2, 2)
x^2 >= x for rationals x         -> counterexample 1/4

The search for the divisibility claim finds \(a = 4\), \(b = 2\), \(c = 2\): \(4 \mid 4\) but \(4 \nmid 2\). The rational search finds \(x = 1/4\). These are different from the counterexamples above, which is normal: a false claim usually has many counterexamples, and any one of them is enough.