Proof by Exhaustion (Case by Case)

Proof by Exhaustion (Case by Case)

Sometimes the most straight forward, if not the most elegant, way to construct a proof is by checking cases.

Example: Divisibility

Theorem. If n is a positive integer then n7 - n is divisible by 7.

Proof. First we factor n7 - n = n(n6 - 1) = n(n3 - 1)(n3 + 1) = n(n-1)(n2 + n + 1)(n+1)(n2 - n + 1). Now there are 7 cases to consider, depending on n = 7 q + r where r = 0, 1, 2, 3, 4, 5, 6, 7.

Case 1: n = 7q. Then n7 - n has the factor n, which is divisible by 7.

Case 2: n = 7q + 1. Then n7 - n has the factor n-1 = 7q.

Case 3: n = 7q + 2. Then the factor n2 + n + 1 = (7q + 2)2 + (7q+2) + 1 = 49 q2 + 35 q + 7 is clearly divisible by 7.

Case 4: n = 7q + 3. Then the factor n2 - n + 1 = (7q + 3)2 - (7q+3) + 1 = 49 q2 + 35 q + 7 is clearly divisible by 7.

Case 5: n = 7q + 4. Then the factor n2 + n + 1 = (7q + 4)2 + (7q+4) + 1 = 49 q2 + 63 q + 21 is clearly divisible by 7.

Case 6: n = 7q + 5. Then the factor n2 - n + 1 = (7q + 5)2 - (7q+5) + 1 = 49 q2 + 63 q + 21 is clearly divisible by 7.

Case 7: n = 7q + 6. Then the factor n + 1 = 7q +7 is clearly divisible by 7.

q

Exercises

Prove each of the following using a case by case analysis.

  1. The "Triangle Inequality" for real numbers, |a + b| is less than or equal to |a| + |b|. (The cases coorespond to the signs (plus or minus) of a and b.)

Next==>What does Well Defined Mean?

<==Back To Counter Examples

Back to Proofs