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, Q₁, Q₂, ..., Q_n. 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 n³ − n is Even for Any Integer n

Let us consider an example, for any integer n, the expression n³ − 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 n³ − n, we get −

$$\mathrm{n^3 \:-\: n \:=\: (2k)^3 \:-\: 2k \:=\: 8k^3 \:-\: 2k \:=\: 2(4k^3 \:-\: k)}$$

Since 4k³ − k is an integer, the expression is divisible by 2, which means that n³ − 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 n³ − 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 n³ – n is even when n is odd.

Step 3: Conclude

Since n³ – n is even in both cases (here n is even or odd), we conclude that for any integer n, the expression n³ – 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.