Proof by Cases

Proof by cases becomes useful when the available representation changes with parity, sign, or another finite classification. Each branch proves the same target under an additional assumption. The logical obligation is to cover every allowed input, not merely the inputs that make the calculation convenient [1][1] Z. Abel, B. Chapman, and E. Demaine, “Lecture 03: Casework and Strong Induction,” 2024. MIT 6.1200J/18.062J, Mathematics for Computer Science; revised February 14, 2024. https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec03.pdf.

What a case split must establish

Suppose the original hypotheses imply that at least one of $C_1,\ldots,C_r$ holds. If the target $Q$ follows under each corresponding case assumption, then $Q$ follows under the original hypotheses. A complete proof therefore gives the coverage argument, proves every branch, and finally combines them.

The cases need not be disjoint. Splitting real numbers into $x\ge0$ and $x\le0$ is exhaustive despite overlap at zero; splitting into $x>0$ and $x<0$ misses zero. In a conditional theorem, retain the original hypotheses in every branch. For example, a theorem about nonzero $x$ legitimately needs only the two strict-sign cases.

These branches may each contain a direct argument, a contradiction, or a smaller case split. They are not separate theorems with unrelated conclusions. A finite split can cover infinitely many inputs because a branch such as “$n$ is even” represents all even integers.

Worked example: parity determines the useful factor

PropositionConsecutive integers have an even product

For every integer $n$, the product $n(n+1)$ is even.

Proof

Every integer is even or odd, so the following cases are exhaustive.

If $n$ is even, write $n=2k$ with $k\in\mathbb Z$. Then

$$n(n+1)=2\bigl(k(2k+1)\bigr).$$

If $n$ is odd, write $n=2k+1$ with $k\in\mathbb Z$. Then

$$n(n+1)=2\bigl((2k+1)(k+1)\bigr).$$

In either case, the quantity in parentheses is an integer, so the product is even. The cases include zero and negative integers as well.

The split is useful because it identifies which factor supplies the factor $2$. When practising, vary the property being proved and check which part of the reasoning makes each new split exhaustive.

Remainder cases and negative integers

For every integer $n$ and positive integer $d$, division with remainder gives $n=dk+r$ with integers $k,r$ and $0\le r<d$. Thus the $d$ remainder classes cover every integer, including negative ones. For example, $-1=3(-1)+2$ belongs to the remainder-$2$ case modulo $3$.

Among $n-1,n,n+1$, one number is divisible by $3$: if $n$ has remainder $0$, it is $n$; with remainder $1$, it is $n-1$; with remainder $2$, it is $n+1$. This supplies the supporting fact used in Direct Proof.

However, not every divisibility problem benefits from a split. The sum of three consecutive integers is simply

$$n+(n+1)+(n+2)=3(n+1).$$

That single direct identity already handles every input. Case analysis remains valid, but adds no useful distinction here. Prefer a split when its branches reveal information that a uniform calculation does not.

Boundary cases and symmetry

ExampleThe absolute-value definition changes at zero

Prove $|x|\ge x$ for every real $x$. If $x\ge0$, then $|x|=x$. If $x<0$, then $|x|=-x>x$ because $-2x>0$. These cases cover all real numbers, and equality occurs exactly when $x\ge0$.

The phrase “without loss of generality” is justified only by a symmetry preserving both the hypotheses and target. To show that $ab$ is even when at least one of integers $a,b$ is even, one may choose the even factor to be called $a$: swapping the names leaves the product and assumption unchanged. An asymmetric condition such as $a<b$ cannot be ignored by swapping names without checking what else changes.

Exercises

ExerciseSquares modulo three

Show that the square of an integer has remainder $0$ or $1$ when divided by $3$.

Show solution

Solution

Write $n=3k+r$ with $r\in\{0,1,2\}$. Then $n^2=3(3k^2+2kr)+r^2$. For $r=0,1,2$, the values of $r^2$ are $0,1,4$, whose remainders are $0,1,1$. Exhaustiveness follows from division with remainder.

ExerciseCheck a claim before proving it

The original notes asked for a parity-based proof that $n^2+4$ is composite for every integer $n>1$. Decide whether the claim is true. If it is false, identify a valid restricted version.

Show solution

Solution

At $n=3$, the expression is $13$, which is prime. Thus the universal claim is false. For even $n>1$, write $n=2k$ with $k\ge1$: then $n^2+4=4(k^2+1)$, a product of integers greater than one, so this restricted claim is true. The old proposed factorization for odd $n$ was invalid: $(2k+1)^2+4=4k^2+4k+5$, while $(2k+1)(2k+3)=4k^2+8k+3$.

ExerciseSeparate divisibility obligations from cases

Prove $30\mid n^5-n$ for every integer $n$. You may use the fact that divisibility by pairwise coprime integers $2,3,5$ implies divisibility by their product. Treat each divisibility claim as a goal, not as an alternative input case.

Show solution

Solution

For divisor $2$, the residues $r=0,1$ give $r^5-r=0$ modulo $2$. For divisor $3$, use representatives $r=0,1,-1$; again $r^5-r=0$ modulo $3$. For divisor $5$, use $r=0,1,-1,2,-2$. The corresponding values of $r^5-r$ are $0,0,0,30,-30$, all divisible by $5$.

These residue checks apply to $n$ because if $n-r$ is divisible by $d$, the identity

$$n^5-r^5=(n-r)(n^4+n^3r+n^2r^2+nr^3+r^4)$$

shows that $n^5-r^5$ is divisible by $d$ as well. Thus $n^5-n$ and $r^5-r$ have the same remainder. We have established all three divisibility goals, and the stated coprimality fact yields divisibility by $30$. The product conclusion would not hold for arbitrary non-coprime divisors: $2\mid4$ and $4\mid4$ do not imply $8\mid4$.

ExerciseMake a piecewise formula explicit

For real $x$, evaluate $|x-1|+|x+1|$ by splitting at the points where the expressions inside the absolute values change sign.

Show solution

Solution

Use $x<-1$, $-1\le x\le1$, and $x>1$. In these cases the sum respectively equals $-2x$, $2$, and $2x$:

$$|x-1|+|x+1|= \begin{cases} -2x,&x<-1,\\ 2,&-1\le x\le1,\\ 2x,&x>1. \end{cases}$$

The middle case includes both boundary points, where the neighboring formulas agree. Each branch follows by replacing the absolute values according to their signs.

The next choice

A good split has an explicit coverage reason and gives each branch a useful additional fact. If negating the desired conclusion gives a more useful assumption than splitting the original inputs, move to Indirect Proof. If the statement is indexed by arbitrarily large natural numbers and smaller instances support larger ones, Mathematical Induction supplies the appropriate principle.

References

1. [1] Z. Abel, B. Chapman, and E. Demaine, “Lecture 03: Casework and Strong Induction,” 2024. MIT 6.1200J/18.062J, Mathematics for Computer Science; revised February 14, 2024. https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec03.pdf ↩