Proof by Exhaustion

A split that covers everything

The claim: $n^2+n$n² + n is even for every whole number n. There are infinitely many whole numbers, so checking them one at a time never finishes. Proof by exhaustion splits them into a finite list of cases and proves the claim in each case.

The split has to cover everything. Dividing a whole number by 2 leaves a remainder of 0 or 1, so every whole number is even or odd, and there is no third possibility. Two cases, n even and n odd, cover all of them.

Case 1: n is even

If n is even, then n = 2k for some whole number k. So $n^2+n={\left(2k\right)}^2+2k=4k^2+2k=2\left(2k^2+k\right)$n² + n = (2k)² + 2k = 4k² + 2k = 2(2k² + k). Since $2k^2+k$2k² + k is a whole number, $n^2+n$n² + n is 2 times a whole number, which makes it even.

Case 2: n is odd

If n is odd, then n = 2k + 1 for some whole number k, and $n^2={\left(2k+1\right)}^2=4k^2+4k+1$n² = (2k + 1)² = 4k² + 4k + 1. Adding n gives $n^2+n=4k^2+4k+1+2k+1=4k^2+6k+2=2\left(2k^2+3k+1\right)$n² + n = 4k² + 4k + 1 + 2k + 1 = 4k² + 6k + 2 = 2(2k² + 3k + 1). Again this is 2 times a whole number, so it is even.

The odd case needs its own algebra. It lands on the same conclusion as the even case by a different route, and a proof that called it “similar” without doing it would have a gap.

Why two cases are enough

Every whole number is in case 1 or case 2, and the claim holds in each case, so it holds for every whole number. The coverage is what makes this a proof: two cases that left some number out would prove the claim only for the numbers they covered.

The same fact can be seen another way. $n^2+n=n\left(n+1\right)$n² + n = n(n + 1), the product of two consecutive whole numbers, and of any two consecutive whole numbers one is even. That argument hides the same two cases: either n is even, or n + 1 is.

n from 0 to 7. Even and odd n take turns, and $n^2+n$n² + n is even in every row. The rows are examples; the two cases above are the proof.

Splits that leave a case out

“n is prime or composite” looks like a split of the whole numbers, but 1 is neither prime nor composite, and neither is 0. “n is positive or negative” misses 0. A proof built on either split has a hole exactly where the missing number is.

Splitting by remainder is the safe way to build cases. Dividing by 3 leaves a remainder of 0, 1 or 2, and every whole number has exactly one of them, so the three cases n = 3k, n = 3k + 1 and n = 3k + 2 cover everything. Treating only the first two leaves out every number of the form 3k + 2, such as 2, 5 and 8.

Three cases: squares divided by 3

The claim: the square of a whole number leaves a remainder of 0 or 1 when divided by 3, never 2. Split n by its own remainder on division by 3.

If n = 3k, then $n^2=9k^2=3\left(3k^2\right)$n² = 9k² = 3(3k²), so the remainder is 0.

If n = 3k + 1, then $n^2=9k^2+6k+1=3\left(3k^2+2k\right)+1$n² = 9k² + 6k + 1 = 3(3k² + 2k) + 1, so the remainder is 1.

If n = 3k + 2, then $n^2=9k^2+12k+4=3\left(3k^2+4k+1\right)+1$n² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1, so the remainder is 1.

The three cases cover every whole number, and none of them gives a remainder of 2, so no square leaves a remainder of 2.

n from 0 to 8, with the remainder each square leaves on division by 3. The remainders run 0, 1, 1 and repeat, one for each of the three cases, and 2 never appears.

The usual mistakes

Checking values instead of proving cases. n = 0 to 7 all work, and that proves nothing about n = 8. Two cases, each with its algebra, cover every n.

Leaving a case out. A split by the remainder on division by 3 needs all three remainders, not two.

Using a split that misses numbers. Prime or composite misses 0 and 1; positive or negative misses 0.

Ride tickets in strips of 3 and 5

In the application below, a club buys ride tickets only in strips of 3 and strips of 5. Every group size from 8 up is shown to be possible by exhaustion over the remainder on division by 3: settle the smallest size in each of the three cases, then add strips of 3. The sizes below 8 are then checked one at a time.