MATH 1800
A direct proof begins with assumptions followed by a sequence of statements, each of which is logically deduced from previous statements or assumptions, that ends with the desired conclusion.
\(2^{1800} + 1\) is not a prime.
Proof. (We can classify this statement as form 1 according to our classification.)
Note that \(2^{1800} + 1 = (2^{600})^3 + 1 ^3 = (2^{600}+1) (2^{1200} - 2^{600} + 1)\).
Since both factors \(2^{600}+1\) and \(2^{1200} - 2^{600} + 1\) are integers greater than \(1\), \(2^{1800} + 1\) is not a prime.
For every even integer \(n\), \((-1)^n = 1\).
Proof.
(We can classify this statement as form 3 according to our classification.)
Let \(n\) be an even integer. Then by definition of an even integer, there exists an integer \(k\) such that \(n = 2k\). Thus, \[(-1)^n = (-1)^{2k} = ((-1)^2)^k = 1^k = 1.\]
There exists a real number \(x\) such that \(\cos(x) = x^2\).
Proof.
(We can classify this statement as form 2 according to our classification.)
Let \(f(x)\) denote the function \(\cos(x) - x^2\). It suffices to show that \(f(x)\) has a real root. Note that \(f(0) = \cos(0) - 0^2 = 1 > 0\) and \(f(\pi) = \cos(\pi) - \pi^2 = 0 - \pi^2 < 0\).
As \(f\) is a continuous function and \(f(0) > 0 > f(\pi)\), by the intermediate value theorem (from first-year calculus), there exists a real number \(c\) with \(0 < c < \pi\) such that \(f(c) = 0\).
Remark. The proof given above is called a nonconstructive proof in the sense that we have only shown that a desired object must exist yet we have not demonstrated a way to construct such an object. Sometimes, proving statements of form 2 could be accomplished by direct construction as the next example shows.
There exists a positive integer \(n\) such that \(n^5 < n!\).
Proof. Take \(n = 8\). Then \(n^5 = 32768 < 40320 = n!\).
If \(r\) is a root to the quadratic polynomial \(at^2 + bt + c\) where \(a\), \(b\), \(c\) are real numbers with \(a \neq 0\), then \(at^2 + bt + c\) can be written as \(a(t-r)(t-s)\) for some real number \(s\).
Proof.
(We can classify this statement as form 2 according to our classification.)
Let \(p(t)\) denote the given polynomial \(at^2 + bt + c\). Then, \[\begin{align} p(t) & = p(t) - 0 \\ & = p(t) - p(r) \\ & = at^2 + bt + c - ar^2 - br \\ & = a(t^2-r^2) + b(t - r) \\ & = a(t-r)(t+r) + b(t - r) \\ & = a(t-r)(t+r) + b(t - r) \\ & = a(t-r)\left(t+r+\frac{b}{a}\right)\\ & = a(t-r)(t-s) \end{align}\] where \(s = -r -\frac{b}{a}\).
(Adapted from COMC 2016) Given a sequence of integers \(a\), \(b\), \(c\), let \(d_1\) be the number added to \(b\) so that the result is an arithmetic sequence and let \(d_2\) be the number added to \(c\) so that the result is an arithmetic sequence. (For example, if the three term sequence is 2, 9, 13, then \(d_1 = -2\) and \(d_2 = 4\).) Prove that \(2\lvert d_1 \rvert = \lvert d_2 \rvert\).
Proof. Recall that \(a\), \(b\), \(c\) form an arithmetic sequence if and only if \(b-a = c-b\).
Suppose that \(d_1\) is such that \(a\), \(b+d_1\), \(c\) is an arithmetic sequence. Then \(b+d_1-a = c - (b+d_1)\), implying that \(d_1 = \frac{c - 2b + a}{2}\).
Suppose that \(d_2\) is such that \(a\), \(b\), \(c+d_2\) is an arithmetic sequence. Then \(c+d_2-b = b -a\), implying that \(d_2 = -c+2b - a = -(c-2b+a)\).
Hence, \(\lvert d_2\rvert = \lvert c-2b + a\rvert = 2 \lvert \frac{c-2b+a}{2}\rvert = 2 \lvert d_1 \rvert\) as desired.
To further illustrate direct proofs, we will obtain some useful inequalities involving real numbers. But before we discuss any proofs, we first specify properties of inequalities that we can take for granted.
If \(a\) is a positive real number, we write \(a > 0\).
If \(a\) is a real number that is 0 or positive, we write \(a \geq 0\).
If \(a\) is a negative real number, we write \(a < 0\).
If \(a\) is a real number that is 0 or negative, we write \(a \leq 0\).
\(a > b\) is another way of writing \(a - b > 0\)
\(a \geq b\) is another way of writing \(a - b \geq 0\)
\(a < b\) is another way of writing \(a - b < 0\)
\(a \leq b\) is another way of writing \(a - b \leq 0\)
We now prove a few results.
Let \(a\), \(b\), and \(c\) be real numbers. If \(a > b\), then \(a + c > b + c\).
Proof.
Since \(a > b\), we have \(a - b > 0\), implying that \(a + c - c - b > 0\). Now, \(a + c - c - b = (a+c) - (c+b) = (a+c) - (b+c)\). It follows that \((a+c) - (b+c) > 0\), giving \(a + c > b + c\).
Remark. This result justifies adding the same real number to both sides of an inequality.
Let \(a\), \(b\), and \(c\) be real numbers. If \(a \geq b\) and \(c \geq 0\), then \(ac \geq bc\).
Proof.
Note that \(a \geq b\) and \(c \geq 0\) means that \(a - b\) and \(c\) are nonnegative real numbers. Thus, \(c(a-b)\) is also a nonnegative real number, giving \(c(a-b) \geq 0\). But \(c(a-b) = ac - bc\). It follows that \(ac - bc \geq 0\), giving \(ac \geq bc\).
Remark. This result justifies multiplying to both sides of an inequality by the same nonnegative real number. What happens if \(c < 0\)?
If \(a\) and \(b\) are nonnegative real numbers such that \(a^2 \geq b^2\), then \(a \geq b\).
Proof.
(We can classify this statement as form 3 since it can be written as \(\forall a, \forall b, a^2 \geq b^2 \Rightarrow a \geq b\) where the universe of discourse is the set of nonnegative real numbers.)
The given statement clearly holds when both \(a\) and \(b\) are zero.
Therefore, we may assume that at least one of \(a\) and \(b\) is positive. Thus, \(a + b > 0\).
Note that \(a^2 \geq b^2\) implies that \(a^2 - b^2 \geq 0\). Factoring the left-hand side gives \((a-b)(a+b) \geq 0\). Since \(a+b\) is positive, by the previous example, we can multiply both sides of the inequality by \(\frac{1}{a+b}\) to obtain \(a-b \geq 0\), giving \(a \geq b\).
Let \(a\) and \(b\) be nonnegative real numbers. Then \(\frac{a+b}{2} \geq \sqrt{ab}.\)
Proof.
Note that \[\begin{align} \left(\frac{a+b}{2}\right)^2 - ab & = \frac{a^2 + 2ab + b^2}{4} - ab \\ & = \frac{a^2 + 2ab + b^2 - 4ab}{4} \\ & = \frac{a^2 - 2ab + b^2}{4} \\ & = \left(\frac{a - b}{2}\right)^2 \\ \end{align}\] Since \(\left(\frac{a - b}{2}\right)^2\) is the square of a real number, its value is at least \(0\). Hence, \(\left(\frac{a+b}{2}\right)^2 - ab \geq 0\), implying that \(\left(\frac{a+b}{2}\right)^2 \geq ab\). As \(\frac{a+b}{2}\) and \(ab\) are nonnegative real numbers, by the previous example, we have \(\left(\frac{a+b}{2}\right)\geq \sqrt{ab}\).
Remark. The inequality \(\frac{a+b}{2} \geq \sqrt{ab}\) is often called the arithmetic mean-geometric mean inequality (or AM-GM inequality for short).
Prove that the square of an even integer is also an even integer.
Prove that there exists a natural number \(n \geq 4\) such that \(\binom{n}{2}+2\) is a prime number.
Let \(a\), \(b\), and \(c\) be real numbers. Prove that if \(a > b\) and \(c < 0\), then \(ac < bc\).
Let \(a\), \(b\), and \(c\) be real numbers. Prove that if \(a \geq b\) and \(b \geq c\), then \(a \geq c\).
Prove that if \(a,b,c,d \in \mathbb{R}\), then \((a^2+b^2)(c^2+d^2) \geq (ac + bd)^2\).
Prove that if \(a\) and \(b\) are positive real numbers, then \(\displaystyle\frac{a+b}{2} \geq \frac{2}{\frac{1}{a} + \frac{1}{b}}\).
Let \(a\) and \(b\) be positive real numbers. Let \(k\) be a positive integer. Prove that if \(a^k > b^k\), then \(a > b\).