Skip to main content
⚡ Calmops
🤖 AI 🏗️ Architecture 🌐 Web 🗃️ Database ⚙️ DevOps 🌍 Network 💻 Programming 🧮 Algorithms 📐 Software Eng. ☁️ Cloud 🔒 Security 📈 Finance More →

Proof by Cases: Dividing the Problem into Manageable Parts

Created: December 19, 2025 10 min read

Introduction

Proof by cases (also called case analysis) is a proof technique where you divide a problem into exhaustive cases and prove the statement for each case separately. If the statement is true in all cases, it’s true overall.

Understanding proof by cases is essential for:

  • Mathematics: Proving statements with multiple conditions
  • Computer Science: Analyzing algorithms with different inputs
  • Logic: Handling disjunctive premises
  • Formal Verification: Proving properties under different conditions
  • Problem Solving: Breaking complex problems into simpler parts

This comprehensive guide explores proof by cases, its structure, and applications.

What is Proof by Cases?

Definition

A proof by cases is a proof that:

  1. Identifies all possible cases that cover the situation
  2. Proves the statement for each case
  3. Concludes that the statement is true overall

Structure

Goal: Prove P

Identify cases: The situation falls into cases C₁, C₂, ..., Cₙ

Case 1: Assume C₁
  [Prove P under assumption C₁]

Case 2: Assume C₂
  [Prove P under assumption C₂]

...

Case n: Assume Cₙ
  [Prove P under assumption Cₙ]

Conclusion: Since P is true in all cases, P is true overall

Why It Works

Proof by cases works because:

  • Exhaustiveness: The cases cover all possibilities
  • Disjunctive Syllogism: If C₁ ∨ C₂ ∨ … ∨ Cₙ and each implies P, then P
  • Logical Necessity: If P is true in every possible scenario, P must be true

Classic Examples

Example 1: Absolute Value

Theorem: |x| ≥ 0 for all real numbers x

Proof:

Case 1: x ≥ 0
  Then |x| = x ≥ 0 ✓

Case 2: x < 0
  Then |x| = -x > 0 ≥ 0 ✓

Since x is either ≥ 0 or < 0, and |x| ≥ 0 in both cases,
|x| ≥ 0 for all real numbers x.

Example 2: Product of Consecutive Integers

Theorem: The product of two consecutive integers is even

Proof:

Let n and n+1 be two consecutive integers.

Case 1: n is even
  Then n = 2k for some integer k
  So n(n+1) = 2k(n+1) = 2(k(n+1))
  Since k(n+1) is an integer, n(n+1) is even ✓

Case 2: n is odd
  Then n+1 is even, so n+1 = 2k for some integer k
  So n(n+1) = n·2k = 2(nk)
  Since nk is an integer, n(n+1) is even ✓

Since n is either even or odd, and n(n+1) is even in both cases,
the product of two consecutive integers is always even.

Example 3: Maximum of Two Numbers

Theorem: max(a, b) + min(a, b) = a + b

Proof:

Case 1: a ≥ b
  Then max(a, b) = a and min(a, b) = b
  So max(a, b) + min(a, b) = a + b ✓

Case 2: a < b
  Then max(a, b) = b and min(a, b) = a
  So max(a, b) + min(a, b) = b + a = a + b ✓

Since a ≥ b or a < b, and the equation holds in both cases,
max(a, b) + min(a, b) = a + b for all real numbers a and b.

Example 4: Divisibility by 3

Theorem: For any integer n, n(n+1)(n+2) is divisible by 3

Proof:

Any integer n can be written as 3k, 3k+1, or 3k+2 for some integer k.

Case 1: n = 3k
  Then n(n+1)(n+2) = 3k(3k+1)(3k+2)
  Since 3k is divisible by 3, the product is divisible by 3 ✓

Case 2: n = 3k+1
  Then n+2 = 3k+3 = 3(k+1)
  So n(n+1)(n+2) = (3k+1)(3k+2)·3(k+1)
  Since the product contains factor 3, it's divisible by 3 ✓

Case 3: n = 3k+2
  Then n+1 = 3k+3 = 3(k+1)
  So n(n+1)(n+2) = (3k+2)·3(k+1)·(3k+4)
  Since the product contains factor 3, it's divisible by 3 ✓

Since every integer falls into one of these three cases,
n(n+1)(n+2) is divisible by 3 for all integers n.

Logical Proofs by Cases

Example 1: Disjunctive Syllogism

Theorem: From (p ∨ q) and (p → r) and (q → r), we can conclude r

Proof:

Assume (p ∨ q), (p → r), and (q → r).

Case 1: p is true
  From p and (p → r), we get r (by Modus Ponens) ✓

Case 2: q is true
  From q and (q → r), we get r (by Modus Ponens) ✓

Since (p ∨ q) means at least one of p or q is true,
and r is true in both cases, r must be true.

Example 2: Prove a Conditional

Theorem: If n is an integer, then n² ≡ 0 or 1 (mod 4)

Proof:

Any integer n is either even or odd.

Case 1: n is even
  Then n = 2k for some integer k
  So n² = 4k² ≡ 0 (mod 4) ✓

Case 2: n is odd
  Then n = 2k+1 for some integer k
  So n² = (2k+1)² = 4k² + 4k + 1 = 4(k² + k) + 1 ≡ 1 (mod 4) ✓

Therefore, n² ≡ 0 or 1 (mod 4) for all integers n.

When to Use Proof by Cases

Good Candidates for Proof by Cases

1. Statements with Disjunctive Conditions

  • “If x > 0 or x < 0, then x² > 0”
  • “Either n is even or n is odd”

2. Statements About Absolute Values

  • “|x| ≥ 0”
  • “|x + y| ≤ |x| + |y|”

3. Statements with Multiple Conditions

  • “If a ≥ b or b ≥ a, then…”
  • “For any real number x, either x ≥ 0 or x < 0”

4. Modular Arithmetic

  • “n(n+1) is even”
  • “n(n+1)(n+2) is divisible by 3”

Poor Candidates for Proof by Cases

1. Too Many Cases

  • If there are infinitely many cases, use a different technique
  • If there are hundreds of cases, consider a more general approach

2. Cases Are Not Exhaustive

  • Make sure the cases cover all possibilities
  • Make sure the cases don’t overlap (or handle overlaps carefully)

3. Simpler Techniques Available

  • If direct proof works, use it
  • If induction works, use it

Common Mistakes

Mistake 1: Missing Cases

Wrong:

Case 1: n is even
  [Prove P]
Conclusion: Therefore P is true

Correct: Must cover all cases (e.g., n is odd too)

Mistake 2: Overlapping Cases

Wrong:

Case 1: x > 0
Case 2: x ≥ 0
[Prove P in both cases]
Conclusion: Therefore P is true

Correct: Cases should be mutually exclusive or handle overlaps

Mistake 3: Not Proving Each Case

Wrong:

Case 1: n is even
  [Assume P]
Case 2: n is odd
  [Assume P]
Conclusion: Therefore P is true

Correct: Must prove P in each case, not assume it

Mistake 4: Assuming Cases Are Exhaustive

Wrong:

Case 1: x > 0
Case 2: x < 0
Conclusion: Therefore P is true for all x

Correct: Must include x = 0 if it’s in the domain

Proof by Cases vs. Other Techniques

Cases vs. Direct Proof

Direct Proof: Assume premises, derive conclusion directly

Cases: Divide into cases, prove each case

When to use cases: When the problem naturally divides into cases

Example: Prove |x| ≥ 0

  • Direct proof: Difficult without cases
  • Cases: Natural (x ≥ 0 or x < 0)

Cases vs. Induction

Induction: Prove base case, then inductive step

Cases: Divide into exhaustive cases

When to use cases: When cases are finite and natural

When to use induction: When proving about all natural numbers

Cases vs. Contradiction

Contradiction: Assume negation, derive contradiction

Cases: Divide into cases, prove each

When to use cases: When cases are natural

When to use contradiction: When negation is easier to work with

Practice Problems

Problem 1: Absolute Value

Theorem: |x - y| ≤ |x| + |y| for all real numbers x and y

Solution:

Case 1: x ≥ 0 and y ≥ 0
  Then |x - y| = |x - y|, |x| = x, |y| = y
  We need to show |x - y| ≤ x + y
  If x ≥ y: |x - y| = x - y ≤ x + y ✓
  If x < y: |x - y| = y - x ≤ x + y ✓

Case 2: x ≥ 0 and y < 0
  Then |x| = x, |y| = -y
  |x - y| = |x - y| = x - y = x + |y| ≤ x + |y| ✓

Case 3: x < 0 and y ≥ 0
  Then |x| = -x, |y| = y
  |x - y| = |x - y| = -(x - y) = -x + y = |x| + y ≤ |x| + |y| ✓

Case 4: x < 0 and y < 0
  Then |x| = -x, |y| = -y
  |x - y| = |x - y| ≤ -x + (-y) = |x| + |y| ✓

Therefore, |x - y| ≤ |x| + |y| for all real numbers x and y.

Problem 2: Parity

Theorem: If n is an integer, then n² + n is even

Solution:

Case 1: n is even
  Then n = 2k for some integer k
  n² + n = (2k)² + 2k = 4k² + 2k = 2(2k² + k)
  Since 2k² + k is an integer, n² + n is even ✓

Case 2: n is odd
  Then n = 2k + 1 for some integer k
  n² + n = (2k+1)² + (2k+1) = 4k² + 4k + 1 + 2k + 1
         = 4k² + 6k + 2 = 2(2k² + 3k + 1)
  Since 2k² + 3k + 1 is an integer, n² + n is even ✓

Therefore, n² + n is even for all integers n.

Problem 3: Modular Arithmetic

Theorem: For any integer n, n³ ≡ n (mod 3)

Solution:

Any integer n can be written as 3k, 3k+1, or 3k+2.

Case 1: n = 3k
  n³ = (3k)³ = 27k³ = 3(9k³)
  n³ ≡ 0 ≡ 3k ≡ n (mod 3) ✓

Case 2: n = 3k+1
  n³ = (3k+1)³ = 27k³ + 27k² + 9k + 1
     = 3(9k³ + 9k² + 3k) + 1
  n³ ≡ 1 ≡ 3k+1 ≡ n (mod 3) ✓

Case 3: n = 3k+2
  n³ = (3k+2)³ = 27k³ + 54k² + 36k + 8
     = 3(9k³ + 18k² + 12k + 2) + 2
  n³ ≡ 2 ≡ 3k+2 ≡ n (mod 3) ✓

Therefore, n³ ≡ n (mod 3) for all integers n.

Online Learning Platforms

Interactive Tools

  • “How to Prove It” by Daniel J. Velleman - Comprehensive proof guide
  • “Introduction to Logic” by Irving M. Copi and Carl Cohen - Classic textbook
  • “A Concise Introduction to Logic” by Patrick J. Hurley - Accessible introduction
  • “forall x: An Introduction to Formal Logic” by P.D. Magnus - Free online textbook

Academic Journals

  • Journal of Symbolic Logic - Leading journal on mathematical logic
  • Studia Logica - International journal on logic and philosophy
  • Logic and Logical Philosophy - Open access journal

Software Tools

  • Prolog - Logic programming language
  • Coq - Interactive theorem prover
  • Isabelle - Generic proof assistant
  • Z3 - SMT solver

Glossary of Key Terms

  • Case Analysis: Dividing into exhaustive cases
  • Disjunctive Syllogism: Reasoning with disjunctions
  • Exhaustive Cases: Cases that cover all possibilities
  • Mutually Exclusive: Cases that don’t overlap
  • Proof by Cases: Proving by considering all cases

Conclusion

Proof by cases is a powerful technique for breaking complex problems into manageable parts. By mastering proof by cases, you develop the ability to:

  • Prove statements with multiple conditions
  • Handle disjunctive premises
  • Reason about absolute values and modular arithmetic
  • Divide complex problems into simpler parts
  • Construct rigorous mathematical proofs

The next article in this series will explore Common Proof Strategies and Patterns, learning how to combine different proof techniques effectively.

What’s your favorite proof by cases? Have you used case analysis in your work? Share your examples in the comments below!

Comments