
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Proof by Cases in Discrete Mathematics
Proof by Cases is a common technique used in Discrete Mathematics to prove statements that may be True in different scenarios. This method helps in breaking down the problem into separate cases and showing that the statement holds true in each one or not. By covering all possible cases, the proof guarantees the truth of the statement for all possible situations. This technique is useful when a statement can be approached in multiple ways, depending on the given conditions.
In this chapter, we will explain the concept of proof by cases, its structure, and go through examples for a better understanding.
What is Proof by Cases?
Proof by cases is simpler than other methods. The goal is to prove a statement P, but instead of proving P directly, we divide the problem into several cases, Q1, Q2, ..., Qn. For each case, we proved that the statement P holds. Since one of the cases must always be true. So proofing the statement for all cases guarantees that P is universally true.
The structure of a Proof by Cases is as follows −
- Identify all the cases − These are the different conditions or scenarios under which the problem can occur.
- Prove each case − For each individual case, show that the statement holds.
- Conclude − Since one of the cases must be true, the overall statement is true.
This method is interesting and quite useful when the problem involves logical "or" conditions, or when a value can take different forms, such as being even or odd, positive or negative.
Why Use Proof by Cases?
Proof by Cases is helpful when the problem is complex and cannot be easily addressed with a single argument. Sometimes, different conditions lead to different approaches. For example, in number theory, a number can be even or odd, and proving the same statement for both conditions may require separate reasoning.
After breaking down the problem, Proof by Cases provides clarity and ensures that every possible situation is covered. This method is exhaustive, and it ensures there are no gaps in the proof.
Example 1: Proving n3 − n is Even for Any Integer n
Let us consider an example, for any integer n, the expression n3 − n is always even.
Step 1: Identify the cases
The key observation here is that every integer n is either even or odd. So that, we can divide the problem into two cases −
- Case 1 − n is even
- Case 2 − n is odd
Step 2: Prove Each Case
Case 1: n is even − If n is even, we can write it like n = 2k for some integer k. Then substituting n = 2k into the expression n3 − n, we get −
$$\mathrm{n^3 \:-\: n \:=\: (2k)^3 \:-\: 2k \:=\: 8k^3 \:-\: 2k \:=\: 2(4k^3 \:-\: k)}$$
Since 4k3 − k is an integer, the expression is divisible by 2, which means that n3 − n is even when n is even.
Case 2: n is odd − If n is odd, we can write n = 2k + 1 for some integer k. Substituting n = 2k + 1 into n3 − n, we get:
$$\mathrm{n^3 \:-\: n \:=\: (2k \:+\: 1)^3 \:-\: (2k \:+\: 1)}$$
Expanding the cubic term, we get −
$$\mathrm{(2k \:+\: 1)^3 \:=\: 8k^3 \:+\: 12k^2 \:+\: 6k \:+\: 1}$$
Thus,
$$\mathrm{n^3 \:-\: n \:=\: (8k^3 \:+\: 12k^2 \:+\: 6k \:+\: 1) \:-\: (2k \:+\: 1) \:=\: 8k^3 \:+\: 12k^2 \:+\: 4k}$$
Factoring out 2,
$$\mathrm{n^3 \:-\: n \:=\: 2(4k^3 \:+\: 6k^2 \:+\: 2k)}$$
Again, the expression is divisible by 2, which means that n3 – n is even when n is odd.
Step 3: Conclude
Since n3 – n is even in both cases (here n is even or odd), we conclude that for any integer n, the expression n3 – n is always even.
Example 2: Sum of Odd Numbers
Let us see another example. This one is another interesting problem. Prove the statement −
"If a + b is odd, then a is odd or b is odd."
Step 1: Identify the cases
We can handle this by considering the two possible scenarios for A and B:
- Case 1 − Both a and b are even.
- Case 2 − Both a and b are odd.
Step 2: Prove Each Case
Case 1: Both a and b are even − If both a and b are even, then we can write a = 2m and b = 2n for some integers m and n. Adding them together −
$$\mathrm{a \:+\: b \:=\: 2m \:+\: 2n \:=\: 2(m \:+\: n)}$$
Since a + b is divisible by 2, the sum is even, contradicting the assumption that a + b is odd. Therefore, this case does not hold.
Case 2: Both a and b are odd – If both a and b are odd, we can write a = 2m + 1 and b = 2n + 1 for some integers m and n. Adding them together −
$$\mathrm{a \:+\: b \:=\: (2m \:+\: 1) \:+\: (2n\: +\: 1)\: =\: 2(m \:+\: n \:+\: 1)}$$
This sum is again even, which contradicts the assumption that a + b is odd. Therefore, this case also does not hold.
Step 3: Conclude
We have shown that if a + b is odd, then at least one of a or b must be odd, as the statement requires.
Example 3: Proof by Cases in Geometry
Let us see the third example in geometry. Consider the following statement −
"For any triangle, the sum of the interior angles is 180 degrees."
Step 1: Identify the cases
We can consider different types of triangles:
- Case 1 − The triangle is acute (all angles are less than 90 degrees).
- Case 2 − The triangle is right (one angle is 90 degrees).
- Case 3 − The triangle is obtuse (one angle is greater than 90 degrees).
Step 2: Prove each case
Case 1: Acute Triangle − In an acute triangle, all angles are less than 90 degree. Regardless of the specific angle measures, the geometric properties of triangles ensure that the sum of the angles always equal to 180 degrees.
Case 2: Right Triangle − In a right triangle, one angle is exactly 90 degrees. The other two angles must sum to 90 degrees, ensuring that the total sum of the interior angles is 180 degrees.
Case 3: Obtuse Triangle − In an obtuse triangle, one angle is greater than 90 degrees, and the other two angles must be the sum to less than 90 degrees. Again, the total sum of the angles in the triangle will always be 180 degrees.
Step 3: Conclude
Since the interior angles of a triangle sum to 180 degrees in all possible cases, the statement is universally true for all triangles.
Conclusion
In this chapter, we explained the concept of Proof by Cases in Discrete Mathematics. We understood how this method works by breaking a problem into separate scenarios and proving the statement in each one. Through examples, we established how Proof by Cases is a powerful tool for tackling problems involving different conditions.