2.2: 3.2.C Examples

Let’s look now at another example of a proof. We set out to prove that the sum of any two rational numbers is rational.

Proof. We start by assuming that x and y are arbitrary rational numbers. Here’s a formal proof that the inference rule

is a valid rule of inference:

So the rule of inference given above is valid. Since x and y are arbitrary rationals, we have proved that the rule is valid for all rationals, and hence the sum of any two rationals is rational.

Again, a more informal presentation that we expect from you during the course would look like:

Proof. Proof by generalisation:

• Let x and y be arbitrary rational numbers.
• By the definition of rational, there are integers a, b $$\neq$$ 0, c, d $$\neq$$ 0 such that $$x=\frac{a}{b}$$ and $$y=\frac{c}{d}$$
• Then $$x+y=\frac{a d+b c}{b d}$$
• We know ad + bc and bd are integers since the sum and product of integers are integers, and we also know bd $$\neq$$ 0 since neither b nor d is 0.
• So we have written x + y as the ratio of two integers, the denominator being nonzero.
• Therefore, by the definition of rational numbers, x + y is rational.
• Since x and y were arbitrary rationals, the sum of any two rationals is rational.

And one more example: we will prove that any 4 -digit number $$d_{1} d_{2} d_{3} d_{4}$$ is divisible by 3 iff the sum of the four digits is divisible by 3 .

Proof. This statement is of the form p q; recall that p q is logically equivalent to $$(p \rightarrow q) \wedge(q \rightarrow p) .$$ So we need to prove for any 4 -digit number $$d_{1} d_{2} d_{3} d_{4}$$ that $$(1)$$ if $$d_{1} d_{2} d_{3} \dot{d}_{4}$$ is divisible by 3 then $$d_{1}+d_{2}+d_{3}+d_{4}$$ is divisible by $$3,$$ and $$(2)$$ if $$d_{1}+d_{2}+d_{3}+$$$$d_{4}$$ is divisible by 3 then $$d_{1} d_{2} d_{3} d_{4}$$ is divisible by $$3 .$$ So let $$d_{1} d_{2} d_{3} d_{4}$$ be an arbitrary 4 -digit number.

(1) Assume $$d_{1} d_{2} d_{3} d_{4}$$ is divisible by $$3,$$ i.e., $$d_{1} d_{2} d_{3} d_{4}=3 k$$ for some integer $$k$$ . The number $$d_{1} d_{2} d_{3} d_{4}$$ is actually $$d_{1} \times 1000+d_{2} \times 100+d_{3} \times 10+d_{4},$$ so we have the equation

$$d_{1} \times 1000+d_{2} \times 100+d_{3} \times 10+d_{4}=3 k$$

Since 1000 = 999 + 1, 100 = 99 + 1, and 10 = 9 + 1, this equation can be rewritten

$$999 d_{1}+d_{1}+99 d_{2}+d_{2}+9 d_{3}+d_{3}+d_{4}=3 k$$

Rearranging gives

$$d_{1}+d_{2}+d_{3}+d_{4}=3 k-999 d_{1}-99 d_{2}-9 d_{3}$$

$$=3 k-3\left(333 d_{1}\right)-3\left(33 d_{2}\right)-3\left(3 d_{3}\right)$$

We can now factor a 3 from the right side to get

$$d_{1}+d_{2}+d_{3}+d_{4}=3\left(k-333 d_{1}-33 d_{2}-d_{3}\right)$$

since $$\left(k-333 d_{1}-33 d_{2}-d_{3}\right)$$ is an integer, we have shown that $$d_{1}+d_{2}+d_{4}+d_{4}$$ is divisible by 3.

(2) Assume $$d_{1}+d_{2}+d_{3}+d_{4}$$ is divisible by $$3 .$$ Consider the number $$d_{1} d_{2} d_{3} d_{4} .$$ As remarked above,

$$d_{1} d_{2} d_{3} d_{4}=d_{1} \times 1000+d_{2} \times 100+d_{3} \times 10+d_{4}$$

so

$$d_{1} d_{2} d_{3} d_{4}=999 d_{1}+d_{1}+99 d_{2}+d_{2}+9 d_{3}+d_{3}+d_{4}$$

$$=999 d_{1}+99 d_{2}+9 d_{3}+\left(d_{1}+d_{2}+d_{3}+d_{4}\right)$$

We assumed that $$d_{1}+d_{2}+d_{3}+d_{4}=3 k$$ for some integer $$k,$$ so we can substitute into the last equation to get

$$d_{1} d_{2} d_{3} d_{4}=999 d_{1}+99 d_{2}+9 d_{3}+3 k=3\left(333 d_{1}+33 d_{2}+3 d_{3}+k\right)$$

since the quantity in parentheses is an integer, we have proved that $$d_{1} d_{2} d_{3} d_{4}$$ is divisible by 3.

In $$(1)$$ and $$(2)$$ above, the number $$d_{1} d_{2} d_{3} d_{4}$$ was an arbitrary 4 -digit integer, so we have proved that for all 4 -digit integers, $$d_{1} d_{2} d_{3} d_{4}$$ is divisible by 3 iff the sum of the four digits is divisible by 3.

Now suppose we wanted to prove the statement "For all integers $$n, n^{2}$$ is even if and only if n is even.” We have already proved half of this statement (“For all integers n, if n is even then $$n^{2}$$ is even" $$),$$ so all we need to do is prove the statement "For all integers $$n,$$ if $$n^{2}$$ is even then $$n$$ is even" and we'll be done. Unfortunately, this is not as straightforward as it seems: suppose we started in our standard manner and let n be an arbitrary integer and assumed that n2 = 2k for some integer k. Then we’d be stuck! Taking the square root of both sides would give us $$n$$ on the left but would leave a $$\sqrt{2 k}$$ on the right. This quantity is not of the form 2$$k^{\prime}$$ for any integer $$k^{\prime} ;$$ multiplying it by $$\frac{\sqrt{2}}{\sqrt{2}}$$ would give 2$$\frac{\sqrt{k}}{\sqrt{2}}$$ but there is no way for us to prove that $$\frac{\sqrt{k}}{\sqrt{2}}$$ is an integer. So we've hit a dead end.

What do we do now?
The answer is that we need a different proof technique. The proofs we have written

so far are what are called direct proofs: to prove p q you assume p is true and prove that the truth of q follows. Sometimes, when a direct proof of p q fails, an indirect proof will work. Recall that the contrapositive of the implication p q is the implication¬q → ¬p, and that this proposition is logically equivalent to p q. An indirect proof of p q, then, is a direct proof of the contrapositive ¬q → ¬p. In our current example, instead of proving “if $$n^{2}$$ is even then n is even” directly, we can prove its contrapositive “if n is not even (i.e., n is odd) then $$n^{2}$$ is not even (i.e., $$n^{2}$$ is odd.)” We call this method a proof by contrapositive. The proof of this contrapositive is a routine direct argument which we leave to the exercises.

Alternatively we sometimes need a proof by division into cases. Consider for instance that we want to prove that $$3 |\left(n^{3}+3 n^{2}+2 n\right)$$ for all integers $$n .$$ What we can do is split our proof into three different case based on the divisibility by 3. Recall from the definition of divisibility that every number can be written as either n = 3k, n = 3k + 1, or n = 3k + 2. In a proof by division into cases, we prove that the claim holds for all of these cases and thereby prove the claim holds for all numbers.

We have also created a pencast about several of the different proof techniques outlined in this chapter. This includes one in which we prove that $$3 |\left(n^{3}+3 n^{2}+2 n\right)$$ using a proof by division into cases, found here: youtu.be/4OHyyGY_WpI

Exercises

1. Find a natural number n for which $$n^{2}+n+41$$ is not prime.
2. Show that the propositions p q and (¬p) → q are logically equivalent.
3. Show that the proposition (p q) → r is equivalent to (p r) ∧ (q r).
4. Determine whether each of the following statements is true. If it true, prove it. If it is false, give a counterexample.

a) Every prime number is odd.
b) Every prime number greater than 2 is odd.

c) If x and y are integers with x < y, then there is an integer z such that x < z < y.
d) If x and y are real numbers with x < y, then there is a real number z such that x < z < y.

5. Suppose that r, s, and t are integers, such that r evenly divides s and s evenly divides t. Prove

that r evenly divides t.

6. Prove that for all integers $$n,$$ if $$n$$ is odd then $$n^{2}$$ is odd.
7. Prove that an integer $$n$$ is divisible by 3 iff $$n^{2}$$ is divisible by $$3 .$$ (Hint. give an indirect proof of "if $$n^{2}$$ is divisible by 3 then $$n$$ is divisible by 3$$" )$$
8. Prove or disprove each of the following statements. Remember that to disprove a statement we always expect a counterexample!

a) The product of two even integers is even.
b) The product of two integers is even only if both integers are even.

c) The product of two rational numbers is rational.
d) The product of two irrational numbers is irrational.
e) For all integers n, if n is divisible by 4 then n2 is divisible by 4.

f) For all integers n, if n2 is divisible by 4 then n is divisible by 4.Proof by Contradiction