3.1: An Introduction to Proof Techniques

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 \(1.3.1\) and \(1.3.2\) in Section 1.3.
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. 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.

Some proofs only require direct computation.

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

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\).

Solution

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\). Then \[\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} \nonumber\] is clearly a rational number because \(mq+2np\) and \(3np\) are integers, and \(3nq\neq0\). Since \(a<b\), we know \(b-a>0\). It follows that \[\left(\frac{1}{3}\,a+\frac{2}{3}\,b\right) - a = \frac{2}{3}\,(b-a) > 0, \nonumber\] which means \(\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{1}\label{he:pfintro-01}\)

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\).

Sometimes, we can use a constructive proof when a proposition claims that certain values or quantities exist.

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

Prove that every positive integer can be written in the form of \(2^e t\) for some nonnegative integer \(e\) and some odd integer \(t\).

Solution

The problem statement only says “every positive integer.” It often helps if we assign a name to the integer; it will make it easier to go through the discussion. Consequently, we customarily start a proof with the phrase “Let \(n\) be … ”

Let \(n\) be a positive integer. Keep dividing \(n\) by 2 until an odd number \(t\) remains. Let \(e\) be the number of times we factor out a copy of 2. It is clear that \(e\) is nonnegative, and we have found \(n=2^e t\).

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

Given any positive integer \(n\), show that there exist \(n\) consecutive composite positive integers.

Solution

For each positive integer \(n\), we claim that the \(n\) integers \[(n+1)!+2, \quad (n+1)!+3, \quad \ldots \quad (n+1)!+n, \quad (n+1)!+(n+1) \nonumber\] are composite. Here is the reason. For each \(i\), where \(2\leq i\leq n+1\), the integer \[\begin{aligned} (n+1)!+i &=& 1\cdot2\cdot3\,\cdots(i-1)i(i+1)\cdots\,(n+1)+i \\ &=& i\,[\,1\cdot2\cdot3\,\cdots(i-1)(i+1)\cdots\,(n+1)+1\,] \end{aligned} \nonumber\] is divisible by \(i\) and greater than \(i\), and hence is composite.

hands-on Exercise \(\PageIndex{3}\label{he:pfintro-03}\)

Construct five consecutive positive integers that are composite. Verify their compositeness by means of factorization.

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

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. 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\). 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.

hands-on Exercise \(\PageIndex{4}\label{he:pfintro-04}\)

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]\).

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

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\).

Sometimes a non-constructive proof can be used to show the existence of a certain quantity that satisfies some conditions. We have learned two such existence theorems from calculus.

Theorem \(\PageIndex{1}\) (Mean Value Theorem)

Let \(f\) be a differentiable function defined over a closed interval \([a,b]\). Then there exists a number \(c\) strictly inside the open interval \((a,b)\) such that \(f'(c) = \frac{f(b)-f(a)}{b-a}\).

Theorem \(\PageIndex{2} \label{thm:IVT}\) (Intermediate Value Theorem)

Let \(f\) be a function that is continuous over a closed interval \([a,b]\). Then \(f\) assumes all values between \(f(a)\) and \(f(b)\). In other words, for any value \(t\) between \(f(a)\) and \(f(b)\), there exists a number \(c\) inside \([a,b]\) such that \(f(c)=t\).

Both results only guarantee the existence of a number \(c\) with some specific property; they do not tell us how to find this number \(c\). Nevertheless, the Mean-Value Theorem plays a very important role in analysis; many of its applications are beyond the scope of this course. We could, however, demonstrate an application of the Intermediate Value Theorem.

Corollary \(\PageIndex{3}\label{cor:IVT}\)

Let \(f\) be a continuous function defined over a closed interval \([a,b]\). If \(f(a)\) and \(f(b)\) have opposite signs, then the equation \(f(x)=0\) has a solution between \(a\) and \(b\).

Proof

According to the Intermediate Value Theorem, \(f(x)\) can take on any value between \(f(a)\) and \(f(b)\). Since they have opposite signs, 0 is a number between them. Hence, \(f(c)=0\) for some number \(c\) between \(a\) and \(b\).

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

The function \(f(x)=5x^3-2x-1\) is a polynomial function, which is known to be continuous over the real numbers. Since \(f(0)=-1\) and \(f(1)=2\), Corollary 3.1.3 implies that there exists a number between 0 and 1 such that \(5x^3-2x-1=0\).

Summary and Review

• Sometimes we can prove a statement by showing how the result can be obtained through a construction, and we can describe the construction in an algorithm.
• Sometimes all we need to do is apply an existence theorem to verify the existence of a certain quantity.