3.1: An Introduction to Proof Techniques

Initial Suggestions

A proof is a logical argument that verifies the validity of a statement. A good proof must be correct, but it also needs to be clear enough for others to understand. In the following sections, we want to show you how to write mathematical arguments. It takes practice to learn how to write mathematical proofs; you have to keep trying! We would like to start with some suggestions.

1. Write at the level of your peers. A common question asked by many students is: how much detail should I include in a proof? One simple guideline is to write at the level that your peers can understand. Although you can skip the detailed computation, be sure to include the major steps in an argument.

2. Use symbols and notations appropriately. Do not use mathematical symbols as abbreviations. For example, do not write “\(x\) is a number \(>4\).” Use “\(x\) is a number greater than 4” instead. Do not use symbols excessively either. It is often clearer if we express our idea in words. Finally, do not start a sentence with a symbol, as in “Suppose \(xy>0\). \(x\) and \(y\) have the same signs.” It would look better if we combine the two sentences, and write “Suppose \(xy>0\), then \(x\) and \(y\) have the same signs.”

3. Display long and important equations separately. Make the key mathematical results stand out by displaying them separately on their own. Be sure to center these expressions. Number them if you need to refer to them later. See Examples 3.3.1 and 3.1.2.

4. Write in complete sentences, with proper usage of grammar and punctuation. A proof is, after all, a piece of writing. It should conform to the usual writing rules. Use complete sentences, and do not forget to check the grammar and punctuation.

5. Anticipate any questions your reader might have and answer them as part of your proof.

6. Start with a draft. Prepare a draft. When you feel it is correct, start revising it: check the accuracy, remove redundancy, and simplify the sentence structure. Organize the argument into short paragraphs to enhance the readability of a proof. Go over the proof and refine it further.

Definitions and Properties

Here is information, some of which was introduced in section 1.5, that will be important for proof writing.

Closure

We will assume the set of integers is closed under addition, subtraction and multiplication.

(Closure of a set under an operation was defined in section 1.5.)

Note: closure of other sets under any operations cannot be assumed. So, for example the statement "the set of rational numbers is closed under multiplication" cannot be used as a reason, unless you prove this within your proof.

 

Definition: Rational numbers 

Here is the definition of rational numbers.

A rational number is a real number which can be written as a fraction, \(\frac{a}{b}\) where \(a,b\) are integers and \( b \neq 0\).

In symbols:

\(n \in \mathbb{Q} \Leftrightarrow \exists a,b \in \mathbb{Z} (n=\frac{a}{b} \wedge b \neq 0)\)

 

Definition: Even & Odd

Here is the definition of even and odd numbers.

Given n is an integer, 

n is even \(\leftrightarrow \exists k \in \mathbb{Z} (n=2k)\)

n is odd \(\leftrightarrow \exists m \in \mathbb{Z} (n=2m+1)\)

 

Terminology: The condition of being even or odd is the parity of an integer. 

Here's a property about the parity of integers which we will prove later in this chapter.

Parity Property

Every integer is either even or odd and not both.

 

 

Zero Product Property

\(\forall a,b \in \mathbb{R}, \qquad ab=0\rightarrow a=0\vee b=0\)

You have used the Zero Product Property for solving quadratic equations by factoring.

\[(x-6)(x+4)=0\]

Since these two binomials mulitply to zero, one must be zero.

\[x-6=0 \vee x+4=0\]

 

In proofs, you may need the contrapositive of the Zero Product Property:

\(a \neq0\wedge b\neq0\rightarrow ab \neq 0\).

You may refer to this as the Zero Product Property as well.

 

Examples

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

Show that the product of two odd integers is odd.

Proof

Let \(x\) and \(y\) be any two odd integers. We want to prove that \(xy\) is odd. We can say \(x=2s+1\) and \(y=2t+1\) for some integers \(s\) and \(t\) by definition of odd. By substitution, \[xy = (2s+1)(2t+1).\] By algebra, \[xy = 4st+2s+2t+1 = 2(2st+s+t)+1,\] where \(2st+s+t\) is an integer since the integers are closed under addition and multiplication. Therefore, \(xy\) is odd by definition of odd. Thus the product of two odd integers is odd. QED.

 

Question 1

Why didn't we use \(2s+1\) for both \(x\) and \(y\) ??

 

Question 2

Why did we need to show \(2st+s+t\) is an integer ??

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.

.

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.

 

Some proofs basically require direct computation.

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

Let \(a\) and \(b\) be two rational numbers such that \(a<b\). Show that the weighted average \(\frac{1}{3}\,a+\frac{2}{3}\,b\) is a rational number between \(a\) and \(b\).

Proof

Since \(a\) and \(b\) are rational numbers, we can write \(a=\frac{m}{n}\) and \(b=\frac{p}{q}\) for some integers \(m\), \(n\), \(p\), and \(q\), where \(n,q\neq0\) by definition of rational numbers. Then using algebra \[\frac{1}{3}\,a+\frac{2}{3}\,b = \frac{1}{3}\cdot\frac{m}{n} + \frac{2}{3}\cdot\frac{p}{q} = \frac{mq+2np}{3nq}.\]  \(\frac{mq+2np}{3nq}\) is a rational number since \(mq+2np\) and \(3np\) are integers because the integers are closed under addition and multiplication, and \(3nq\neq0\) by the Zero Product Property since \(3\neq0 \wedge n\neq0 \wedge q\neq0 \) . Since \(a<b\), we know \(b>a\). Using algebra, it follows that \[b-a>0\] \[\frac{2}{3}\,(b-a) > 0,\]  
\[\frac{2}{3}\,b-\frac{2}{3}\,a > 0,\] 
\[\frac{2}{3}\,b+\frac{1}{3}\,a-\,a> 0,\] \[\left(\frac{1}{3}\,a+\frac{2}{3}\,b\right) - a > 0\]   \[\frac{1}{3}\,a+\frac{2}{3}\,b > a\]. In a similar fashion, we also find \(\frac{1}{3}\,a+\frac{2}{3}\,b < b\). Thus, \(\frac{1}{3}\,a+\frac{2}{3}\,b\) is a rational number between \(a\) and \(b\).

hands-on Exercise \(\PageIndex{2}\label{he:pfintro-02}\)

Show that \(\frac{1}{3}\,a+\frac{2}{3}\,b\) is closer to \(b\) than to \(a\).

Hint

Compute the distance between \(a\) and \(\frac{1}{3}\,a+\frac{2}{3}\,b\), and compare it to the distance between \(\frac{1}{3}\,a+\frac{2}{3}\,b\) and \(b\).

 

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

Let \(m\) and \(n\) be positive integers. Show that, if \(mn\) is even, then an \(m\times n\) chessboard can be fully covered by non-overlapping dominoes.

Remark

This time, the names \(m\) and \(n\) have already been assigned to the two positive integers. Thus, we can refer to them in the proof without an introduction.

Solution

Since \(mn\) is even, one of the two integers \(m\) and \(n\) must be even (this actually needs a proof, but we will assume it to be true for now). Without loss of generality (since the other case is similar), we may assume \(m\), the number of rows, is even. Then \(m=2t\) for some integer \(t\) by definition of even. Each column can be filled with \(m/2=t\) non-overlapping dominoes placed vertically. As a result, the entire chessboard can be covered with \(nt\) non-overlapping vertical dominoes.

Exercises 

Exercise \(\PageIndex{1}\)

Show that, between any two rational numbers \(a\) and \(b\), where \(a<b\), there exists another rational number.

Hint

Try the midpoint of the interval \([a,b]\).

Proof

Since \(a\) and \(b\) are rational numbers, we can write \(a=\frac{p}{q}\) and \(b=\frac{j}{k}\) for some integers \(p\), \(q\), \(j\), and \(k\), where \(q \neq0 \text{ and } k\neq0\) by definition of rational numbers; also \(\frac{p}{q} < \frac{j}{k}\). Then choose \(m=\frac{1}{2}\big(a+b\big)=\frac{1}{2}\big(\frac{p}{q}+\frac{j}{k}\big)=\frac{kp+jq}{2kq}.\)
First we show \(m\) is a rational number:  \(kp+jq\) and \(2kq\) are integers because the integers are closed under addition and multiplication, and \(2kq\neq0\) by the Zero Product Property since \(2\neq0 \wedge k\neq0 \wedge q\neq0 \) .

Next, we must show \(a<m \text { and } m<b.\)
Since \(\frac{p}{q} < \frac{j}{k}\), \[\frac{1}{2}\Big (\frac{p}{q}+\frac{j}{k}\Big)<\frac{1}{2}\Big(\frac{j}{k}+\frac{j}{k}\Big)=\frac{j}{k}=b.\]

In other words, \[m<b.\]

Since \(\frac{p}{q} < \frac{j}{k}\), \[a=\frac{1}{2}\Big (\frac{p}{q}+\frac{p}{q}\Big)<\frac{1}{2}\Big(\frac{p}{q}+\frac{j}{k}\Big)=m.\]

In other words, \[a<m.\]

Thus, \(\frac{1}{2}\big(a+b\big)\) is a rational number between \(a\) and \(b\).

 

Question

Why did we NOT just say "\(\frac{1}{2}\big(a+b\big)\) is a rational number since the rational numbers are closed under addition and multiplication"??

Exercise \(\PageIndex{2}\)

Prove the rational numbers are closed under addition.

 

Exercise \(\PageIndex{3}\)

Show that, between any two rational numbers \(a\) and \(b\), where \(a<b\), there exists another rational number closer to \(b\) than to \(a\).

Hint

Use a weighted average of \(a\) and \(b\).

 

Answer

Answer is not here yet.

 

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

Prove: the sum of two odd integers is a even.

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

Show that there is a rational number between 1 and 5 whose distance from 5 is seven times as long as its distance from 1.

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

Prove the square of an even integer is even.

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

State the parity of each of these numbers & explain:

(a) -11    (b)  0.8    (c) 502

Solution

(a) -11 is odd because -11 = 2(-6)+1 and -6 is an integer
(b) 0.8 has no parity since it is not an integer
(c) 502 is even because 502 = 2(251) and 251 is an integer

Exercise \(\PageIndex{8}\)

Show that given any rational number \(x\), there exists an integer \(y\) such that \(x^2y\) is an integer.

Hint

Since \(x\) is rational, we can write \(x=\frac{m}{n}\) for some integers \(m\) and \(n\), where \(n\neq0\). All you need to do is to describe \(y\) in terms of \(m\) and \(n\).

 

Exercise \(\PageIndex{9}\)

The natural numbers are closed under subtraction.  True or False? Prove your answer.

Answer

False, the natural numbers are not closed under subtraction.  Here is a counterexample.  Consider 5 and 8. 5 and 8 are natural numbers.  However, 5 - 8 is not a natural number, hence the natural numbers are not closed under subtraction.

Exercise \(\PageIndex{10}\)

Show that given any rational number \(x\), and any positive integer \(k\), there exists an integer \(y\) such that \(x^ky\) is an integer.