3.1 Direct proofs of universal statements
If you form the product of four consecutive numbers, the result will be one less than a perfect square. Try it!
\[\begin{align*} 1 \cdot 2 \cdot 3 \cdot 4 = 24 = 5^2 - 1, \\ 2 \cdot 3 \cdot 4 \cdot 5 = 120 = 11^2 - 1, \\ 3 \cdot 4 \cdot 5 \cdot 6 = 360 = 19^2 - 1. \end{align*}\]It always works!
The three calculations that we’ve carried out above constitute an inductive argument in favour of the result. If you like, we can try a bunch of further examples,
\[\begin{gather*} 13 \cdot 14 \cdot 15 \cdot 16 = 43680 = 209^2 - 1,\\ 14 \cdot 15 \cdot 16 \cdot 17 = 571200 = 239^2 - 1. \end{gather*}\]But really, no matter how many examples we produce, we haven’t proved the statement — we’ve just given evidence.
Generally, the first thing to do in proving a universal statement like this is to rephrase it as a conditional. The resulting statement is a Universal Conditional Statement or a UCS. The reason for taking this step is that the hypotheses will then be clear — they form the antecedent of the UCS. So, while you won’t have really made any progress in the proof by taking this advice, you will at least know what tools you have at hand. Taking the example we started with, and rephrasing it as a UCS we get
\[ \forall a,b,c,d \in {\mathbb Z}, (\mbox{a,b,c,d consecutive}) \implies \exists k \in {\mathbb Z}, a{\cdot}b{\cdot}c{\cdot}d = k^2 -1 \]
The antecedent of the UCS is that \(a,b,c\) and \(d\) must be consecutive. By concentrating our attention on what it means to be consecutive, we should quickly realize that the original way we thought of the problem involved a red herring. We don’t need to have variables for all four numbers; because they are consecutive, \(a\) uniquely determines the other three. Finally, we have a version of the statement that we’d like to prove that should lend itself to our proof efforts.
Theorem 3.1 \[ \forall a \in {\mathbb Z}, \exists k \in {\mathbb Z}, a(a+1)(a+2)(a+3) = k^2 - 1. \]
In this simplistic example, the only thing we need to do is come up with a value for \(k\) given that we know what \(a\) is. In other words, a “proof” of this statement involves doing some algebra.
Without further ado…
Proof. Suppose that \(a\) is a particular but arbitrarily chosen integer. Consider the product of the four consecutive integers, \(a\), \(a+1\), \(a+2\) and \(a+3\). We would like to show that this product is one less than the square of an integer \(k\). Let \(k\) be \(a^2+3a+1\).
First, note that
\[ a(a+1)(a+2)(a+3) = a^4 + 6a^3 + 11a^2 + 6a. \]
Then, note that
\[\begin{gather*} k^2 - 1 = (a^2 + 3a +1)^2 - 1 \\ = (a^4 + 6a^3 + 11a^2 + 6a + 1) - 1 \\ = a^4 + 6a^3 + 11a^2 + 6a. \end{gather*}\]
Now, if you followed the algebra above, the proof stands as a completely valid argument showing the truth of our proposition, but this is very unsatisfying! All the real work was concealed in one stark little sentence: “Let \(k\) be \(a^2+3a+1\).” Where on earth did that particular value of \(k\) come from? The answer to that question should hopefully convince you that there is a huge difference between devising a proof and writing one. A good proof can sometimes be somewhat akin to a good demonstration of magic, a magician doesn’t reveal the inner workings of his trick, neither should a mathematician feel guilty about leaving out some of the details behind the work! Heck, there are plenty of times when you just have to guess at something, but if your guess works out, you can write a perfectly correct proof.
In devising the proof above, we multiplied out the consecutive numbers and then realized that we’d be done if we could find a polynomial in \(a\) whose square was \(a^4 + 6a^3 + 11a^2 + 6a + 1\). Now, obviously, we’re going to need a quadratic polynomial, and because the leading term is \(a^4\) and the constant term is \(1\), it should be of the form \(a^2 + ma + 1\). Squaring this gives \(a^4 + 2ma^3 + (m^2+2)a^2 + 2ma + 1\) and comparing that result with what we want, we pretty quickly realize that \(m\) had better be 3. So it wasn’t magic after all!
This seems like a good time to make a comment on polynomial arithmetic. Many people give up (or go searching for a computer algebra system) when dealing with products of anything bigger than binomials. This is a shame because there is an easy method using a table for performing such multiplications. As an example, in devising the previous proof we needed to form the product \(a(a+1)(a+2)(a+3)\), now we can use the distributive law or the infamous F.O.I.L rule to multiply pairs of these, but we still need to multiply \((a^2+a)\) with \((a^2+5a+6)\). Create a table that has the terms of these two polynomials as its row and column headings.
\[\begin{array}{c|ccc} & a^2 & 5a & 6 \\ \hline a^2 & & & \\ a & & & \\ \end{array}\]
Now, fill in the entries of the table by multiplying the corresponding row and column headers.
\[\begin{array}{c|ccc} & a^2 & 5a & 6 \\ \hline a^2 & a^4 & 5a^3 & 6a^2 \\ a & a^3 & 5a^2 & 6a \\ \end{array}\]
Finally, add up all the entries of the table, combining any like terms.
You should note that the F.O.I.L rule is just a mnemonic for the case when the table has two rows and two columns.
Okay, let’s get back to doing proofs. We are going to do a lot of proofs involving the concepts of elementary number theory. So, as a convenience, all of the definitions that were made in Chapter 1 are gathered below:
Definition 3.7 (Prime) \[\forall \, p \, \in {\mathbb Z}, p \text{ is prime} \iff (p>1) \land (\forall x,y \in {\mathbb Z}_{> 0}, \; p=xy \; \implies \; x=1 \, \lor \, y=1)\]
In this section, we are concerned with direct proofs of universal statements. Such statements come in two flavours — those that appear to involve conditionals, and those that don’t:
These two forms can readily be transformed one into the other, so we will always concentrate on the latter. A direct proof of a UCS always follows a form known as “generalizing from the generic particular.” We are trying to prove that \(\forall x \in U, P(x) \implies Q(x)\). The argument (in skeletal outline) will look like:
Okay, so this outline is pretty crappy. It tells you how to start and end a direct proof, but those obnoxious dot-dot-dots in the middle are where all the real work has to go. If I could tell you (even in outline) how to fill in those dots, that would mean mathematical proof isn’t really a very interesting activity to engage in. Filling in those dots will sometimes (rarely) be obvious, more often it will be extremely challenging; it will require great creativity, loads of concentration, you’ll call on all your previous mathematical experiences, and you will most likely experience a certain degree of anguish. Just remember that your sense of accomplishment is proportional to the difficulty of the puzzles you attempt. So let’s attempt another…
Recall Definition 3.4 of the floor of a real number:
\[ y = \lfloor x \rfloor \; \iff \; (y \in \mathbb Z \; \land \; y \leq x < y+1).\]
There is a sad tendency for people to apply old rules in new situations just because of a chance similarity in the notation. The brackets used in notating the floor function look very similar to ordinary parentheses, so the following “rule” is often proposed
\[ \lfloor x + y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor \]
Exercise 3.1 Find a counterexample to the previous “rule.”
What is (perhaps) surprising is that if one of the numbers involved is an integer then the “rule” really works.
Theorem 3.2 \[ \forall x \in {\mathbb R}, \, \forall n \in {\mathbb Z}, \, \lfloor x + n \rfloor = \lfloor x \rfloor + \lfloor n \rfloor \]
Since the floor of an integer is that integer, we could restate this as \(\lfloor x + n \rfloor = \lfloor x \rfloor + n\).
Now, let’s try rephrasing this theorem as a UCS: If \(x\) is a real number and \(n\) is an integer, then \(\lfloor x + n \rfloor = \lfloor x \rfloor + n\). This is bad…it appears that the only hypotheses that we can use involve what kinds of numbers \(x\) and \(n\) are — our hypotheses aren’t particularly potent. Your next most useful allies in constructing proofs are the definitions of the concepts involved. The quantity \(\lfloor x \rfloor\) appears in the theorem, let’s make use of the definition:
\[ a = \lfloor x \rfloor \; \iff \; a \in {\mathbb Z}\; \, \land \; \, a \leq x < a+1. \]
The only other floor function that appears in the statement of the theorem (perhaps even more prominently) is \(\lfloor x + n\rfloor\), here, the definition gives us
\[ b = \lfloor x + n \rfloor \; \iff \; b \in {\mathbb Z}\; \, \land \; \, b \leq x + n < b+1. \]
These definitions are our only available tools so we’ll certainly have to make use of them, and it’s important to notice that that is a good thing; the definitions allow us to work with something well-understood (the inequalities that appear within them) rather than with something new and relatively suspicious (the floor notation). Putting the proof of this statement together is an exercise in staring at the two definitions above and noting how one can be converted into the other. It is also a testament to the power of naming things.
As we’ve seen in the examples presented in this section, coming up with a proof can sometimes involve a bit of ingenuity. But, sometimes, there is a “follow your nose” sort of approach that will allow you to devise a valid argument without necessarily displaying any great leaps of genius! Here are a few pieces of advice about proof-writing:
- Before anything else, determine precisely what hypotheses you can use.
- Jot down the definitions of anything in the statement of the theorem.
- There are 26 letters at your disposal (and even more if you know Greek) (and you can always throw on subscripts!) don’t be stingy with letters. The nastiest mistake you can make is to use the same variable for two different things.
- Please write a rough draft first. Write two drafts! Even if you can write beautiful, lucid prose on the first go around, it won’t fly when it comes to organizing a proof.
- The statements in a proof are supposed to be logical statements. That means they should be Boolean (statements that are either true or false). An algebraic expression all by itself doesn’t count, an inequality or an equality does.
- Don’t say “if” when you mean “since.” Really!
If you start a proof about rational numbers like so:
Proof. Suppose that \(x\) is a particular but arbitrary rational number. If \(x\) is a rational number, it follows that…people are going to look at you funny. What’s the point of supposing that \(x\) is rational, then acting as if you’re in doubt of that fact by writing “if”? You mean “since.”
- Mark off the beginning and the end of your proofs as a hint to your
readers. In this book, we use the following template:
(Beginning of proof.) \[\vdots\] (End of proof.)Instead of a square at the end, some authors use the abbreviation Q.E.D.27
We’ll close this section with a word about axioms. The axioms in any given area of math are your most fundamental tools. Axioms don’t need to be proved — we are supposed to just accept them! A very common problem for beginning proof writers is telling the difference between statements that are axiomatic and statements that require some proof. For instance, in the exercises for this section, there is a problem that asks us to prove that the sum of two rational numbers is rational. Doesn’t this seem like it might be one of the axioms of rational numbers? Is it really something that can be proved?
Well, we know how the process of adding rational numbers works: we put the fractions over a common denominator and then just add numerators. Do you see how adding fractions really rests on our ability to add the numerators (which are integers). So, in doing that exercise, you can use the fact (indeed, you’ll need to use the fact) that the sum of two integers is an integer. So how about that statement? Is it necessary to prove that adding integers produces an integer?
As a matter of fact it is necessary since the structure of the integers rests on a foundation known as the Peano axioms for the naturals — and the Peano axioms don’t include one that guarantees that the sum of two naturals is also a natural. If you are tempted to trace this whole thing back, to “find out how deep the rabbit hole goes,” I commend you. But, if you just want to be able to get on with doing your homework problems, I sympathize with that sentiment too. Let’s agree that integers behave the way we’ve come to expect — if you add or multiply integers the result will be an integer.
3.1.1 Exercises
Every prime number greater than 3 is of one of the two forms \(6k+1\) or \(6k+5\). What statement(s) could be used as hypotheses in proving this theorem?
Prove that 129 is odd.
Prove that the sum of two rational numbers is a rational number.
Prove that the sum of an odd number and an even number is odd.
Prove that if the sum of two integers is even, then so is their difference.
Prove that for every real number \(x\), \(\frac{2}{3} < x < \frac{3}{4} \; \implies \; \lfloor 12x \rfloor = 8\).
Prove that if \(x\) is an odd integer, then \(x^2\) is of the form \(4k+1\) for some integer \(k\).
Prove that for all integers \(a\) and \(b\), if \(a\) is odd and \(6 \!\mid\!(a+b)\), then \(b\) is odd.
Prove that \(\forall x\in{\mathbb R}, \, x\not\in{\mathbb Z}\, \implies \, \lfloor x\rfloor+\lfloor-x\rfloor=-1\).
Define the evenness of an integer \(n\) by:
\[ \mbox{evenness} (n) = k \; \iff \; 2^k \!\mid\!n \, \land \, 2^{k+1} \nmid n \]
State and prove a theorem concerning the evenness of products.
Suppose that \(a\), \(b\) and \(c\) are integers such that \(a \!\mid\!b\) and \(b \!\mid\!c\). Prove that \(a \!\mid\!c\).
Suppose that \(a\), \(b\), \(c\) and \(d\) are integers with \(a \neq c\). Further, suppose that \(x\) is a real number satisfying the equation \[ \frac{ax+b}{cx+d} = 1. \] Show that \(x\) is rational. Where is the hypothesis \(a \neq c\) used?
Show that if two positive integers \(a\) and \(b\) satisfy \(a \!\mid\!b\) and \(b \!\mid\!a\) then they are equal.
Quod erat demonstrandum or “(that) which was to be demonstrated.” some authors prefer placing a small rectangle at the end of their proofs, but Q.E.D. seems more pompous.↩