3.2: Direct Proofs

To show that a statement \(q\) is true, follow these steps:

• Either find a result that states \(p \Rightarrow q\), or prove that \(p\Rightarrow q\) is true.
• Show or verify that \(p\) is true.
• Conclude that \(q\) must be true.

The logic is valid because if \(p \Rightarrow q\) is true and \(p\) is true, then \(q\) must be true. Symbolically, we are saying that the logical formula \[[(p \Rightarrow q) \wedge p ] \Rightarrow q\] is a tautology (we can easily verify this with a truth table). Symbolically, we present the argument as \[\begin{array}{cl} & p \Rightarrow q \\ & p \\ \hline \therefore & q \end{array}\] Such an argument is called modus ponens or the law of detachment.

Example \(\PageIndex{1}\label{eg:directpf-01}\)

The argument

	\(b^2>4ac \Rightarrow ax^2+bx+c=0\) has two real solutions.
	\(x^2-5x+6\) satisfies \(b^2>4ac\).
\(\therefore\)	\(x^2-5x+6=0\) has two real solutions.

is an example of modus ponens.

It is clear that implications play an important role in mathematical proofs. If we have a sequence of implications, we could join them “head to tail” to form another implication: \[\begin{array}{cl} & p \Rightarrow q \\ & q \Rightarrow r \\ \hline \therefore & p \Rightarrow r \end{array}\] This is called the law of syllogism.

.

Example \(\PageIndex{2}\label{eg:directpf-02}\)

The argument

	German shepherds are dogs.
	Dogs are mammals.
	Mammals are vertebrates.
\(\therefore\)	German shepherds are vertebrates.

is valid because of the law of syllogism.

The big question is, how can we prove an implication? The most basic approach is the direct proof:

Assume \(p\) is true.

Deduce from \(p\) that \(q\) is true.

The important thing to remember is: use the information derived from \(p\) to show that \(q\) is true. This is how a typical direct proof may look:

Proof: Assume \)p\) is true. Then . . .

Because of \(p\), we find . . .

. . . Therefore \(q\) is true.

Example \(\PageIndex{3}\label{eg:directpf-03}\)

Prove that if an \(m\times n\) chessboard can be fully covered by non-overlapping dominoes, then \(mn\) must be even.

Solution

Assume the chessboard can be covered by non-overlapping dominoes, and let \(t\) be the number of dominoes that cover the chessboard. Then the chessboard must contain \(2t\) squares. Hence \(mn=2t\), which means \(mn\) must be an even number.

Before we continue with more examples, we would like to introduce the formal definition of even and odd integers.

Definition

An integer is even if it can be written as \(2q\) for some integer \(q\), and odd if it can be written as \(2q+1\) for some integer \(q\).

We do not have to use \(q\) to denote the integer that, when multiplied by 2, produces an even integer. Any letter will work, provided that we mention it is an integer. For example, if \(n\) is an even integer, then we can write \(n=2t\) for some integer \(t\). The notion of even integers can be further generalized.

Definition

Let \(m\) be a nonzero integer. An integer is said to be a multiple of \(m\) if it can be written as \(mq\) for some integer \(q\).

We are now ready to study more examples.

Example \(\PageIndex{4}\label{eg:directpf-04}\)

Show that the square of an odd integer is odd.

Solution

Let \(n\) be an odd integer. Then \(n=2t+1\) for some integer \(t\), and \[n^2 = (2t+1)^2 = 4t^2+4t+1 = 2(2t^2+2t)+1,\] where \(2t^2+2t\) is an integer. Hence, \(n^2\) is odd.

hands-on exercise \(\PageIndex{1}\label{he:directpf-01}\)

Let \(n\) be an integer. Show that if \(n\) is odd, then \(n^3\) is odd.

Example \(\PageIndex{5}\label{eg:directpf-05}\)

Show that the product of two odd integers is odd.

Solution

Let \(x\) and \(y\) be two odd integers. We want to prove that \(xy\) is odd. Then \(x=2s+1\) and \(y=2t+1\) for some integers \(s\) and \(t\), and \[xy = (2s+1)(2t+1) = 4st+2s+2t+1 = 2(2st+s+t)+1,\] where \(2st+s+t\) is an integer. Therefore, \(xy\) is odd.

In this proof, we need to use two different quantities \(s\) and \(t\) to describe \(x\) and \(y\) because they need not be the same. If we write \(x=2s+1\) and \(y=2s+1\), we are in effect saying that \(x=y\). We have to stress that \(s\) and \(t\) are integers, because just saying \(x=2s+1\) and \(y=2t+1\) does not guarantee \(x\) and \(y\) are odd. For instance, the even number 4 can be written as \(2\cdot\frac{3}{2}+1\), which is of the form \(2s+1\). It is obvious that 4 is not odd. Even though we can write a number in the form \(2s+1\), it does not necessarily mean the number must be odd, unless we know with certainty that \(s\) is an integer. This example illustrates the importance of paying attention to the details in our writing.

.

Example \(\PageIndex{6}\label{directpf-06}\)

Show that if \(x^3-7x^2+x-7=0\), then \(x=7\).

Solution

Assume \(x^3-7x^2+x-7=0\). Since \[x^3-7x^2+x-7 = x^2(x-7)+(x-7) = (x^2+1)(x-7),\] if it is equal to zero, we need either \(x^2+1=0\), or \(x-7=0\). Since \(x^2+1\) can never be zero, we must have \(x-7=0\); thus \(x=7\).

hands-on exercise \(\PageIndex{2}\label{he:directpf-02}\)

Show that if \(x^3+6x^2+12x+8=0\), then \(x=-2\).

The last example demonstrates a technique called proof by cases. There are two possibilities, namely, either (i) \(x^2+1=0\), or (ii) \(x-7=0\). The final conclusion is drawn after we study these two cases separately.

Example \(\PageIndex{7}\label{eg:directpf-07}\)

Show that if an integer \(n\) is not divisible by 3, then \(n^2-1\) must be a multiple of 3.

Remark

The letter \(n\) has been used to identify the integer of interest to us, and it appears in the hypothesis of the implication that we want to prove. Nonetheless, many authors would start their proofs with the familiar phrase “Let \(n\) be … .”

Answer

Let \(n\) be an integer that is not divisible by 3. When it is divided by 3, the remainder is 1 or 2. Hence, \(n=3q+1\) or \(n=3q+2\) for some integer \(q\).

Case 1: If \(n=3q+1\) for some integer \(q\), then \[n^2-1 = 9q^2+6q = 3 (3q^2+2q),\] where \(3q^2+2q\) is an integer.

Case 2: If \(n=3q+2\) for some integer \(q\), then \[n^2-1 = 9q^2+12q+3 = 3(3q^2+4q+1),\] where \(3q^2+4q+1\) is an integer.

In both cases, we have shown that \(n^2-1\) is a multiple 3.

hands-on exercise \(\PageIndex{3}\label{he:directpf-03}\)

Show that \(n^3+n\) is even for all \(n\in\mathbb{N}\).

hands-on exercise \(\PageIndex{4}\label{he:directpf-04}\)

Show that \(n(n+1)(2n+1)\) is divisible by 6 for all \(n\in\mathbb{N}\).

Hint

One of the two integers \(n\) and \(n+1\) must be even, so we already know that the product \(n(n+1)(2n+1)\) is a multiple of 2. Hence, it remains to show that it is also a multiple of 3. Consider three cases: \(n=3q\), \(n=3q+1\), or \(n=3q+2\), where \(q\) is an integer.

We close our discussion with two common fallacies (logical errors). The first one is the fallacy of the inverse or the denial of the antecedent: \[\begin{array}{cl} & p \Rightarrow q \\ & \overline{p} \\ \hline \therefore & \overline{q} \end{array}\] This in effect proves the inverse \(\overline{p}\Rightarrow \overline{q}\), which we know is not logically equivalent to the original implication. Hence, this is an incorrect method for proving an implication.

.

Example \(\PageIndex{8}\label{eg:directpf-08}\)

Is the following argument

	Dictionaries are valuable.
	This book is not a dictionary.
\(\therefore\)	This book is not valuable.

valid? Why?

Another common mistake is known as the fallacy of the converse or the affirmation of the consequence: \[\begin{array}{cl} & p \Rightarrow q \\ & q \\ \hline \therefore & p \end{array}\] This only proves the converse \(q\Rightarrow p\). Since the converse is not logically equivalent to the original implication, this is an incorrect way to prove an implication.

.

Example \(\PageIndex{9}\label{eg:directpf-09}\)

Is this argument

	No medicine tastes good.
	This drink tastes bad.
\(\therefore\)	This must be medicine.

a valid argument? Why?

Summary and Review

• To prove an implication \(p\Rightarrow q\), start by assuming that \(p\) is true. Use the information from this assumption, together with any other known results, to show that \(q\) must also be true.
• If necessary, you may break \(p\) into several cases \(p_1, p_2, \ldots\,\), and prove each implication \(p_i\Rightarrow q\) (separately, one at a time) as indicated above.
• Be sure to write the mathematical expressions clearly. Use different variables if the quantities involved may not be the same.
• To get started, write down the given information, the assumption, and what you want to prove.
• In the next step, use the definition if necessary, and rewrite the information in mathematical notations. The point is, try to obtain some mathematical equations or logical statements that we can manipulate.

.

Exercise \(\PageIndex{1}\label{ex:directpf-01}\)

Prove or disprove: \(2^n+1\) is prime for all nonnegative integer \(n\).

Exercise \(\PageIndex{2}\label{ex:directpf-02}\)

Show that for any integer \(n\geq5\), the integers \(n\), \(n+2\) and \(n+4\) cannot be all primes.

Hint

If \(n\) is a multiple of 3, then \(n\) itself is composite, and the proof will be complete. So we may assume \(n\) is not divisible by 3. Then what would \(n\) look like, and, what can you say about \(n+2\) and \(n+4\)?

Exercise \(\PageIndex{3}\label{ex:directpf-03}\)

Let \(n\) be an integer.

1. Show that if \(n\) is odd, then \(n^2\) is also odd.
2. Show that if \(n\) is odd, then \(n^4\) is also odd.
3. A corollary is a result that can be derived easily from another result. Derive (b) as a corollary of (a).
4. Show that if \(m\) and \(n\) are odd, then so is \(mn\).
5. Show that if \(m\) is even, and \(n\) is odd, then \(mn\) is even.

Exercise \(\PageIndex{4}\label{ex:directpf-04}\)

Prove that, for any odd integer \(n\), the number \(2n^2+5n+4\) must be odd.

Exercise \(\PageIndex{5}\label{ex:directpf-05}\)

Let \(n\) be an integer.

1. Prove that if \(n\) is a multiple of 3, then \(n^2\) is also a multiple of 3.
2. Prove that if \(n\) is a multiple of 7, then \(n^3\) is also a multiple of 7.

Exercise \(\PageIndex{6}\label{ex:directpf-06}\)

Prove that if \(n\) is not a multiple of 3, then \(n^2\) is also not a multiple of 3.

Hint

If \(n\) is not a multiple of 3, then \(n=3q+1\) or \(n=3q+2\) for some integer \(q\).

Exercise \(\PageIndex{7}\label{ex:directpf-07}\)

Use the facts that

\(\sqrt{2}\) is irrational, and

if \(x\) is irrational, then \(\sqrt{x}\) is also irrational,

to prove that \(\sqrt[8]{2}\) is irrational.

Exercise \(\PageIndex{8}\label{ex:directpf-08}\)

Recall that we can use a counterexample to disprove an implication. Show that the following claims are false:

1. If \(x\) and \(y\) are integers such that \(x^2>y^2\), then \(x>y\).
2. If \(n\) is a positive integer, then \(n^2+n+41\) is prime.

Exercise \(\PageIndex{9}\label{ex:directpf-09}\)

Explain why the following arguments are invalid:

1. Let \(n\) be an integer. If \(n^2\) is odd, then \(n\) is odd. Therefore, \(n\) must be odd.
2. Let \(n\) be an integer. If \(n\) is even, then \(n^2\) is also even. As an integer, \(n^2\) could be odd. Hence, \(n\) cannot be even. Therefore, \(n\) must be odd.

Exercise \(\PageIndex{10}\label{ex:directpf-10}\)

Analyze the following reasoning:

1. Let \(S\) be a set of real numbers. If \(x\) is in \(S\), then \(x^2\) is in \(S\). But \(x\) is not in \(S\), hence \(x^2\) is not in \(S\).
2. Let \(S\) be a set of real numbers. If \(x\) is in \(S\), then \(x^2\) is in \(S\). Therefore, if \(x^2\) is in \(S\), then \(x\) is in \(S\).