Section 3.3 Proof by Cases
In this section we will learn another proof technique, proof by cases. We will also see an important theorem that can be useful for proof by cases, the Division Algorithm.
Proof by cases is used for statements of the form for all \(x\in D, P(x)\text{,}\) where the set \(D\) can be broken into smaller sets. For example, a statement might be easier to prove for even numbers and odd numbers separately, rather than more general integers.
Every truth table represents all possible cases of true and false for a logical statement. For example, when you use a truth table to determine if an argument is valid, you are really using proof by cases.
Proof by Cases.
To prove for all \(x\in D, P(x)\) by cases, break \(D\) into smaller subsets. Each subset represents a case. Then each case is proven separately. Make sure you state each case, each subset, clearly.
If \(D=D_1\cup D_2\text{,}\)
-
Case 1.
Let \(x\in D_1\text{,}\) Prove \(P(x)\text{.}\)
-
Case 2.
Let \(x\in D_2\text{,}\) Prove \(P(x)\text{.}\)
Important: in choosing your subsets, make sure you cover all the elements of \(D\text{.}\) You can have as many cases as necessary.
Example 3.3.1. Proof by Cases.
Prove given any two consecutive integers, one is even and one is odd.
Proof.
Let \(n\) and \(n+1\) be consecutive integers.
Case 1: Let \(n\) be even. Then \(n=2k\) for some \(k\in\mathbb{Z}\text{.}\) Then \(n+1=2k+1\) for \(k\in\mathbb{Z}\text{.}\) Hence \(n+1\) is odd.
Case 2: Let \(n\) be odd. Then \(n=2k+1\) for some \(k\in\mathbb{Z}\text{.}\) Then \(n+1=2k+2=2(k+1)\) for \(k+1\in\mathbb{Z}\text{.}\) Hence \(n+1\) is even.
Thus, for any two consecutive integers, one is even and one is odd.
Activity 3.3.1. Practice with Proof by Cases.
Prove for every integer \(n\text{,}\) \(n^2+n\) is even.
Activity 3.3.2.
Recall the absolute value function is defined as
\begin{equation*}
|x|=
\begin{cases}
x, \amp\text{if $x\geq 0$;}\\
-x \amp\text{if $x<0$.}
\end{cases}
\end{equation*}
Prove for all \(x\in \mathbb{R}\text{,}\) \(|x|=|-x|\text{.}\) What would appropriate cases be?
Activity 3.3.3.
Prove for all integers \(m\) and \(n\text{,}\) \(m+n\) and \(m-n\) are either both even or both odd.
Hint.There are four cases, depending on whether \(m\) and \(n\) are even or odd.
The next theorem gives us an example of proof by cases, where the cases involve prime and compsite numbers. Although the theorem may seem like a well-known fact, the proof is not entirely simple.
Theorem 3.3.2.
Any integer \(n>1\) is divisible by a prime.Proof.
We will divide this proof into two cases, where \(n\) is prime and where \(n\) is composite.
Case 1: \(n\) is prime. We can see that \(n\mid n\text{.}\) Since \(\text{}\) is prime, \(n\) is divisible by a prime.
Case 2: \(n\) is composite. Then \(n=r_0s_0\) where \(1< r_0 < n\text{,}\) and \(r_0, s_0\in \mathbb{Z}\text{.}\) If \(r_0\) is prime, then \(n\) is divisible by a prime.
If \(r_0\) is not prime, then \(r_0=r_1s_1\) where \(1< r_1 < r_0\text{,}\) and \(r_1, s_1\in \mathbb{Z}\text{.}\) If \(r_1\) is prime, then \(n=r_1s_1s_0\) and \(n\) is divisible by a prime.
Similarly, if \(r_1\) is not prime, then \(r_1=r_2s_2\) where \(1< r_2 < r_1 < r_0\text{,}\) and \(r_2, s_2\in \mathbb{Z}\text{,}\) etc.
We can keep applying this process to get \(n=r_ks_k\cdots s_0\) with \(1< r_k <\cdots< r_1 < r_0\text{,}\) and \(r_k, s_k\in \mathbb{Z}\text{.}\)
If at any point \(r_k\) is prime, then we are done, as we have found a prime divisor of \(n\text{.}\) We know that there cannot be infinitely many non-prime \(r_k\) since there are only finitely many integers between 1 and \(n\text{.}\) Thus, the process must terminate with a prime divisor of \(n\text{.}\) Hence, every integer is divisible by a prime.
In
Section 3.2, we looked at the idea of divisibility. Remember, this is a relationship between two integers, not actual division. We will continue to focus on integers. One of the issues with division of integers is that if you divide two integers, you no longer necessarily have an integer. So what if the only numbers we are allowed to use are integers? Can we still somehow think of division? Well, yes. This is, in fact, how you were probably introduced to division long ago. When you were first learning arithmetic you only knew about integers (probably only positive integers).
Suppose you want to divide 15 by 5. This is easy, \(15\div 5=3\text{.}\) But what if you want to divide 15 by 6? Now 6 does not "go evenly" into 10 (in other words, 6 does not divide 10). In this case, we get a remainder. In particular, 6 “goes into” 15 two times with a remainder of 3. Or, \(15\div 6\) has quotient 2 and remainder 3.
OK, we want to formalize this idea of division, making sure we are only using integers. We know 5 divides 15, since \(15=5(3)\text{.}\) Can we do the same sort of thing for 15 and 6? Almost. In this case, \(15=6(2)+3\text{.}\)
In general, given any integers \(n, d\) with \(d\neq 0\text{,}\) we can find integers \(q, r\) with \(n=dq+r\text{.}\) In general, \(q, r\) are not unique: \(15=6(1)+9\text{,}\) or \(15=6(-2)+27\) or \(15=6(3)-3\text{,}\) for example. But as we noted, we want to think of \(r\) as the remainder. If we are more specific about conditions on the remainder, then \(q\) and \(r\) are unique.
Theorem 3.3.3. The Division Algorithm.
Given any integer \(n\) and any positive integer \(d\text{,}\) there exist unique integers \(q, r\) such that \(n=dq+r\) and \(0\leq r < d\text{.}\)
We say \(q\) is the quotient and \(r\) is the remainder when \(n\) is divided by \(d\text{.}\)
Although this theorem is usually called the Division Algorithm, the name can be confusing. In particular, the Division Algorithm is not really an algorithm.
Some important observations: the remainder MUST be nonnegative. It can be 0. This is what happens when \(d\mid n\text{.}\) Although \(n\) can be ANY integer, we will limit \(d\) to being positive. The Division Algorithm can be extended to any \(d\neq 0\text{,}\) but we will just need \(d>0\) in this class.
Example 3.3.4. Finding Quotients and Remainders.
Let \(n=15, d=7\text{,}\) Find the quotient and remainder \(q, r\text{.}\)
Answer 1. Let \(n=28, d=7\text{,}\) Find the quotient and remainder \(q, r\text{.}\)
Answer 2. Let \(n=9, d=12\text{,}\) Find the quotient and remainder \(q, r\text{.}\)
Answer 3. Let \(n=-17, d=5\text{,}\) Find the quotient and remainder \(q, r\text{.}\)
Answer 4.\(-17=5(-4)+3; q=-4, r=3\)
Let \(n=0, d=7\text{,}\) Find the quotient and remainder \(q, r\text{.}\)
Answer 5.
Activity 3.3.4. Quotients and Remainders.
For the given \(n\) and \(d\text{,}\) find \(q\) and \(r\) as in the Division Algorithm.
(a)
\(n=20\) and \(d=8\)
(b)
\(n=45\) and \(d=9\)
(c)
\(n=8\) and \(d=12\)
(d)
\(n=-15\) and \(d=7\)
We can use the Division Algorithm to find representations of the integers.
For example, if we let \(d=2\text{,}\) what are the possible remainders? In this case, \(r=0\) or \(r=1\text{.}\) Thus, there are two possible forms for \(n\text{:}\) \(n=2q+0\) or \(n=2q+1\text{.}\) We see that these are the two forms corresponding to \(n\) being even or odd. Now, as a corollary of the Division Algorithm, we have that every integer must be even or odd.
We can use the Division Algorithm to get other forms, as well. For example, if \(d=4\text{,}\) the possible forms are \(n=4q+0, n=4q+1, n=4q+2\) or \(n=4q+3\text{.}\) We can use these forms to get different cases for the integers.
Example 3.3.5. More Cases.
Prove that the square of any odd integer has the form \(8m+1\) for some \(m\in \mathbb{Z}\text{.}\)
First let's try to just prove this directly.
Let \(n\) be odd. Then \(n=2k+1, k\in\mathbb{Z}\text{.}\) Thus, \(n^2=(2k+1)^2=4k^2+4k+1\text{.}\) It is not clear this has the form \(8m+1\text{.}\) If we try using some cases, we may get a bit more to work with. We know any integer has the form \(4k, 4k+1, 4k+2,\) or \(4k+3\text{.}\) But only \(4k+1\) and \(4k+3\) are odd.
Proof.
Let \(n\) be odd.
Case 1: Let \(n=4k+1\) for some \(k\in\mathbb{Z}\text{.}\) Then
\begin{align*}
n^2&=(4k+1)^2\\
&=16k^2+8k+1\\
&=8(2k^2+k)+1
\end{align*}
for some \(2k^2+k\in\mathbb{Z}\text{.}\) Let \(m=2k^2+k\text{.}\) Then \(n\) has the form \(8m+1, m\in \mathbb{Z}\text{.}\)
Case 2: Let \(n=4k+3\) for some \(k\in\mathbb{Z}\text{.}\) Then
\begin{align*}
n^2&=(4k+3)^2\\
&=16k^2+24k+9\\
&=8(2k^2+3k)+9\\
&=8(2k^2+3k)+8+1\\
&=8(2k^2+3k+1)+1
\end{align*}
for some \(2k^2+3k+1\in\mathbb{Z}\text{.}\) Let \(m=2k^2+3k+1\text{.}\) Then \(n\) has the form \(8m+1, m\in \mathbb{Z}\text{.}\)
Thus, any odd integer has the form \(8m+1\text{.}\)
Note, what this theorem really says is that the square of an odd integer must have remainder 1 when divided by 8. That might be a little surprising.
Activity 3.3.5. Dividing by 3.
Use the Division Algorithm to find the possible forms of an integer when \(d=3\text{.}\)
Hint.What are the possible values for \(r\text{?}\)
Activity 3.3.6. Consecutive Integers.
Prove the product of any two consecutive integers has the form \(3k\) or \(3k+2\) for some integer \(k\text{.}\)
Exercises Exercises
1.
For the given \(n\) and \(d\text{,}\) find \(q\) and \(r\) such that \(n=dq+r\) with \(0\leq r<d\) (as in the Division Algorithm).
\(n=36\) and \(d=40\)
\(n=-45\) and \(d=11\)
2.
Prove for all integers \(n\text{,}\) \(n^2-n+3\) is odd.
3.
Prove the square of of any integer has the form \(4k\) or \(4k+1\) for some integer \(k\text{.}\)
4.
Prove that the product of any two consecutive integers is even.
5.
Prove that the square of any integer has the form \(3k\) or \(3k+1\) for some integer \(k\text{.}\)
6.
Prove that for any integer \(n\text{,}\) \(n(n^2-1)(n+2)\) is divisible by 4.
