Case Analysis

The Central Idea

Suppose every object under consideration must satisfy at least one of the conditions

If we prove

and so on through

then \(P\) holds in every possible situation.

Symbolically,

Why Case Analysis Works

A proof by cases does not prove the theorem by inspecting examples.

Instead, it partitions the entire logical domain into categories and proves the result for every category.

The essential requirement is

If even one possible situation is omitted, the proof is incomplete.

Exhaustive Cases

A collection of cases is exhaustive when the cases cover all possible situations relevant to the claim.

For integers, the division

or

is exhaustive.

Every integer belongs to exactly one of these categories.

Disjoint Cases

Cases are disjoint when no object can belong to more than one case.

Even and odd integers are disjoint because no integer can be both even and odd.

Disjointness is useful because it prevents overlap, but it is not always required.

Exhaustiveness is the essential requirement.

Cases May Overlap

Suppose a proof uses:

• Case 1: \(x\ge0\);
• Case 2: \(x\le0\).

These cases overlap at

That overlap does not invalidate the proof.

The cases still cover every real number.

The Basic Procedure

1. Identify the full domain of possibilities.
2. Choose cases that collectively cover the domain.
3. State why the cases are exhaustive.
4. Assume the condition for the first case.
5. Prove the desired conclusion in that case.
6. Repeat for every remaining case.
7. Conclude that the theorem holds in all cases.

Example: The Square of an Integer Is Congruent to \(0\) or \(1\) Modulo \(4\)

Every integer is either even or odd.

We prove:

We divide the proof into two cases.

Case 1: \(n\) Is Even

If \(n\) is even, then

for some integer \(k\).

Therefore,

Hence

Case 2: \(n\) Is Odd

If \(n\) is odd, then

for some integer \(k\).

Then

Therefore,

Since every integer is either even or odd,

Case Analysis through Remainders

The division algorithm gives natural case structures.

For any integer \(n\) and positive integer \(m\), there is a unique remainder

such that

Therefore residue classes modulo \(m\) create an exhaustive set of cases.

Example: Every Integer Square Is \(0\), \(1\), or \(4\) Modulo \(8\)

Every integer is congruent modulo \(4\) to exactly one of

We examine these four cases.

Case 1: \(n=4k\)

Therefore,

Case 2: \(n=4k+1\)

Therefore,

Case 3: \(n=4k+2\)

Therefore,

Case 4: \(n=4k+3\)

Reducing modulo \(8\),

Therefore every integer square is congruent to

Case Analysis with Absolute Value

The definition of absolute value is itself piecewise:

Proofs involving absolute value often naturally divide into sign cases.

Example: \(|x|\ge x\)

Prove that for every real number \(x\),

We use two cases.

Case 1: \(x\ge0\)

Then

Therefore,

holds with equality.

Case 2: \(x<0\)

Then

Since \(x<0\),

Thus

Therefore,

for every real number \(x\).

Example: \(|xy|=|x||y|\)

One way to prove

is to divide according to the signs of \(x\) and \(y\).

There are four sign combinations:

Case 1: Both Nonnegative

If \(x\ge0\) and \(y\ge0\), then \(xy\ge0\).

and

Hence the two sides are equal.

Case 2: \(x\ge0\) and \(y<0\)

Then \(xy\le0\), so

Also,

Therefore the identity holds.

Case 3: \(x<0\) and \(y\ge0\)

Then \(xy\le0\), so

Also,

Again the identity holds.

Case 4: Both Negative

If \(x<0\) and \(y<0\), then \(xy>0\).

Meanwhile,

Therefore,

in all four cases.

Cases from Logical Alternatives

Sometimes the hypotheses themselves provide a disjunction.

Suppose we know

To prove \(R\), we may prove

and

Since at least one of \(P\) or \(Q\) holds, \(R\) follows.

Example: A Product Is Zero

Suppose

Over the real numbers,

Therefore any statement that follows from either alternative can be proved by cases.

Example: If \(ab=0\), Then \(a^2b+ab^2=0\)

Case 1:

Then

Case 2:

Again,

Therefore the result holds in every possible case.

Cases from Order Relations

Two real numbers \(a\) and \(b\) satisfy exactly one of

Example: \(\max(a,b)+\min(a,b)=a+b\)

We prove

for all real \(a,b\).

If \(a\ge b\), then

and

Thus the sum is \(a+b\).

If \(a \[ \max(a,b)=b \]

and

Again the sum is \(a+b\).

Case Analysis with Parity

Parity gives one of the most common discrete case splits:

Many expressions behave differently under these two forms:

versus

Example: \(n(n+1)\) Is Always Even

Let \(n\) be any integer.

Case 1: \(n\) is even.

Then \(n(n+1)\) contains the even factor \(n\), so the product is even.

Case 2: \(n\) is odd.

Then \(n+1\) is even, so \(n(n+1)\) contains the even factor \(n+1\).

Therefore,

A Shorter Structural Observation

The previous theorem can also be proved without explicitly labeling two cases by observing that consecutive integers always have opposite parity.

Therefore one of

is even.

This illustrates that a case-based fact may sometimes be compressed once its structure is familiar.

Case Analysis with Modular Classes

For any integer \(n\), exactly one of the following holds:

These three residue classes can support a complete three-case proof.

Example: \(n(n+1)(n+2)\) Is Divisible by \(3\)

Let \(n\) be any integer.

Case 1:

Then \(3\mid n\).

Case 2:

Then

Case 3:

Then

In every case, one of

is divisible by \(3\).

Hence

Case Analysis with Set Membership

Set statements may naturally split according to whether an element belongs to a particular set.

For any element \(x\),

If the desired conclusion behaves differently in these two situations, a case proof may be appropriate.

Case Analysis in Algorithms

Algorithms frequently branch according to conditions.

A correctness proof may mirror those branches:

• Case 1: the condition is true;
• Case 2: the condition is false.

If every possible execution enters one of the branches and the desired property holds in each branch, the algorithm is correct for that step.

Case Analysis in Piecewise Functions

A piecewise function already divides its domain into cases.

For example,

Any global statement about \(f\) may require analyzing both pieces.

Case Analysis and Proof by Contradiction

Proof methods can be combined.

A proof by cases may contain a contradiction argument inside one of its cases.

For example:

1. split into even and odd cases;
2. handle the even case directly;
3. assume a subclaim fails in the odd case;
4. derive a contradiction.

The outer structure remains case analysis.

Case Analysis and Induction

An inductive step may itself require cases.

For example, while proving \(P(k+1)\), the argument might depend on whether

is even or odd.

The induction supplies the overall proof structure, while case analysis resolves different forms inside the inductive step.

Cases Should Reflect Real Structure

A good case split reduces complexity.

Useful distinctions often come from:

• parity;
• sign;
• remainder classes;
• membership or nonmembership;
• zero versus nonzero;
• prime versus composite;
• relative order;
• branches in a definition or algorithm.

Arbitrary case splits can make a proof longer without making it clearer.

Common Error: Cases Are Not Exhaustive

Suppose a proof about real \(x\) uses only:

• Case 1: \(x>0\);
• Case 2: \(x<0\).

The case

has been omitted.

Unless the theorem excludes \(x=0\), the proof is incomplete.

Common Error: Cases Are Examples Instead of Categories

Checking

does not constitute the “even case.”

A genuine parity case begins with an arbitrary even integer:

Cases must represent entire classes of objects.

Common Error: Proving Different Conclusions in Different Cases

The purpose of case analysis is to establish the same final theorem in every case.

If Case 1 proves \(P\) but Case 2 proves only an unrelated statement \(Q\), the proof has not established \(P\) universally.

Each case must return to the same required conclusion.

Common Error: Introducing Impossible Cases

A case split should respect the hypotheses.

If the theorem already assumes

then a case

is impossible and adds nothing to the proof.

Build cases from possibilities that actually remain after all hypotheses are considered.

Common Error: Overlapping Cases without Recognizing the Overlap

Overlap is not automatically wrong, but it can create confusion.

For example,

and

both include \(x=0\).

If the proof depends on cases being mutually exclusive, the boundaries must be chosen carefully.

Common Error: Too Many Cases

A proof may be valid but inefficient if it divides the problem more finely than necessary.

For example, if only parity matters, splitting integers into residue classes modulo \(8\) may create eight cases when two would suffice.

Prefer the coarsest case structure that still makes the proof work.

Common Error: Case Labels Do Not Match the Algebra

If a case says

then the algebraic representation should be

Writing \(n=3k+1\) would analyze the wrong case.

Each symbolic form must match the stated condition exactly.

Common Error: Forgetting the Final Exhaustiveness Statement

After proving every case, connect them back to the full domain.

A useful ending is:

These cases exhaust all possibilities. Therefore the desired conclusion holds for every permitted object.

That sentence closes the logical structure of the proof.

A Reliable Procedure for Case Analysis

1. State the theorem and identify the domain.
2. Find a structural distinction that covers the domain.
3. List all cases explicitly.
4. Verify that the cases are exhaustive.
5. Note whether overlap matters.
6. Choose an arbitrary object satisfying the first case.
7. Prove the required conclusion in that case.
8. Repeat for every remaining case.
9. Check that every case proves the same final claim.
10. Conclude that the theorem holds because all possibilities were covered.

Example: Full Case-Analysis Workflow

Prove that for every integer \(n\),

is even.

Step 1: Choose exhaustive cases.

Every integer is either even or odd.

Case 1: \(n\) is even.

Write

Then

so \(n^2+n\) is even.

Case 2: \(n\) is odd.

Write

Then

so \(n^2+n\) is even.

Step 3: Conclude.

The even and odd cases exhaust all integers. Therefore,

Practice 1: Parity

Prove by cases that for every integer \(n\),

Practice 2: Consecutive Product

Prove by cases that

is even for every integer \(n\).

Practice 3: Three Consecutive Integers

Prove by cases modulo \(3\) that

for every integer \(n\).

Practice 4: Absolute Value

Prove by cases that

for every real \(x\).

Practice 5: Maximum and Minimum

Prove by cases:

Practice 6: Exhaustiveness

A proof about real numbers uses the cases

and

Explain what is missing.

Practice 7: Modular Cases

List the exhaustive residue classes for an integer \(n\) modulo \(5\).

Practice 8: Product Zero

Suppose \(ab=0\). Prove by cases that

Practice 9: Overlap

Are the cases

and

exhaustive? Are they disjoint?

Practice 10: Identify the Error

A student claims to prove a statement for all integers by checking only the cases

and

Explain why the proof is incomplete.

Practice Answers

Practice 1

If \(n=2k\), then

If \(n=2k+1\), then

These cases exhaust all integers.

Practice 2

If \(n\) is even, then \(n\) is an even factor of the product.

If \(n\) is odd, then \(n+1\) is even.

Therefore \(n(n+1)\) is even in both cases.

Practice 3

Every integer satisfies exactly one of

If \(n\equiv0\), then \(3\mid n\).

If \(n\equiv1\), then \(3\mid(n+2)\).

If \(n\equiv2\), then \(3\mid(n+1)\).

Therefore the product of the three consecutive integers is divisible by \(3\).

Practice 4

If \(x\ge0\), then \(|x|=x\).

If \(x<0\), then \(|x|=-x>x\).

Hence \(|x|\ge x\) for every real \(x\).

Practice 5

If \(a\ge b\), then

If \(a \[ \max(a,b)=b,\qquad \min(a,b)=a. \]

In either case, the sum is \(a+b\).

Practice 6

The case

is missing. The two stated cases are not exhaustive over the real numbers.

Practice 7

The exhaustive residue classes are

Practice 8

Since \(ab=0\), either \(a=0\) or \(b=0\).

If \(a=0\), then

If \(b=0\), then

Therefore the result holds in all cases.

Practice 9

The cases are exhaustive because every real number satisfies at least one of them.

They are not disjoint because

belongs to both.

Practice 10

The residue class

has been omitted.

Therefore the cases do not cover all integers, so the proof is incomplete.

What to Remember

Case analysis proves a theorem by covering the full domain with manageable alternatives:

together with

• cases must be exhaustive;
• cases may overlap unless disjointness is specifically needed;
• each case should represent a full category, not a few examples;
• every case must establish the same final claim;
• parity, sign, remainders, order, and set membership often provide natural case structures;
• proof methods can be nested inside individual cases;
• use the smallest useful number of cases.

The strategic question is: What finite set of possibilities covers every object in the problem while making each branch easier to analyze?

Where We Go Next

Case analysis handles a problem by separating possibilities. Another class of discrete proofs instead tracks a quantity or property that remains fixed or changes in only one direction while a process evolves.

The next lesson, Invariants and Monovariants, develops those ideas for analyzing repeated moves, transformations, algorithms, and state changes.