Section 4.1 Direct proofs
You have seen several proofs in this book already. Now, it is time to learn to write your own. In this chapter, we will explore a couple of different types of proof techniques while we write proofs about integers. We will keep the material of the proofs simple while we learn the act of writing.
In this book we will take two pieces of advice about proofwriting to heart. The first is Cathy O'Neil's position that proofs are social constructs. She says, “If I’m trying to prove something to you and you remain unconvinced, then it is no proof, even if I’ve used the same argument before successfully.” Some mathematicians believe that elegance, brevity, and cool tricks are important to proofs. While those are worthwhile goals to pursue, the most important thing is making yourself understood to your audience.
The second piece of advice is from Garth Margenhi: “I know writers who use subtext, and they're all cowards.” We will be explicit about what we mean to the point of over-explanation. It is better to be understood than to look intelligent.
So, as we've seen, a proof of a mathematical theorem is a sequence of statements that begin in a set of assumptions and known facts, and end in the conclusion of the theorem. Each statement must flow logically from the prior one. Let's start with a type of proof you will be able to write by the end of the chapter.
Theorem 4.1.1.
Let \(n\) be an integer. If \(n\) is even, then \(n^2\) is also even.We will prove this theorem by starting with the assumption that there is an even integer, \(n\text{.}\) Then we will have to use the definition of what an even integer is. Then, we will turn our attention to \(n^2\) to see if it is even as well.
We need to know what an even integer is, so let's define even and odd numbers.
Definition 4.1.2.
An integer \(n\) is even if there exists an integer \(m\) such that \(n = 2m\text{.}\) An integer \(n\) is odd if there exists an integer \(m\) such that \(n=2m+1\text{.}\)
Example 4.1.3.
The integer \(16\) is even, since we can write \(16=2 \times 8\text{.}\) The integer \(-87\) is odd, because we can write \(-87= 2 \times (-44) + 1\text{.}\)
Notice that this definition is precise, and most importantly useful as you will see in the proof. (You should write this, and the other proofs in the chapter, down!)
Proof.
Let \(n\) be an even integer. By definition, there exists an integer \(m\) such that \(n=2m\text{.}\)
In that case,
Since \(2m^2\) is an integer, we have shown \(n^2\) can be written as \(2\) times an integer. Therefore, if \(n\) is even, them \(n^2\) is even.
Notice that in the above proof we started by assuming the sentence to be proven and working one step at a time until we reached the conclusion. Then, we end the proof by restating the theorem. A proof of \(p\to q\) where we start by assuming \(p\) and making sequential inferences until we conclude \(q\) is called a direct proof.
We must never do the following:
Assume that the theorem to be proven is true. So above, we could not assume \(n^2\) was even. We can assume any premises, but not the conclusion.
Prove an universal statement with an example. It is absolutely wrong to prove every even integer has an even square by just looking at \(2\) and \(4\text{.}\) How do we know about \(6\text{?}\) We must work generally.
Let's see two more examples of direct proofs.
Example 4.1.4.
Prove that if \(n\) is odd, then \(4n^2 + 3n - 10\) is odd.
Start by declaring our assumptions: \(n\) is an odd integer.
Next, unpack any definitions in those assumptions. Since \(n\) is odd, that means there exists an integer \(m\) where \(n=2m+1\text{.}\)
Now that we have said all that we can say about \(n\text{,}\) we turn our attention to \(4n^2+3n\text{.}\) Substitue \(n=2m+1\text{,}\) and prove that the result can be written as twice an integer plus one. Sums, differences, and products of integers are integers.
Try writing the proof yourself, and then open the proof below to see mine. Our wording may be different, but as long as your proof is understandable to your peer and logically and mathematically valid, it is correct.
Proof.
Let \(n\) be an odd integer. By definition, there exists an integer \(m\) such that \(n=2m+1\text{.}\) Then,
Since \(4n^2 + 3n - 10\) can be written in the form \(2k+1\) for an integer \(k\text{,}\) that means \(4n^2 + 3n - 10\) is odd. Therefore, if \(n\) is odd, then \(4n^2 + 3n - 10\) is odd.
You may be thinking you can stop at \(16m^2+22m - 3\text{.}\) Technically, yes, any even number plus any odd number is odd. However, if you are using \(2m+1\) as your definition of an odd number and you are writing to a novice (you are!) you should try to be as clear as possible. So, we break the \(-3\) into \(-4+1\) and write the entire expression as twice an integer plus one.
In our last direct proof we will prove a fact about divisibility.
Definition 4.1.5.
The integer \(n\) is divisible by a nonzero integer \(a\) if there exists an integer \(m\) such that \(n=am\text{.}\) The notation \(a|n\) means “\(a\) divides \(n\text{.}\)”
Note very carefully that \(a|n\text{,}\) the sentence “\(a\) divides \(n\text{,}\)” is not the same notation as \(n/a\text{,}\) the “number” “\(n\) divided by \(a\text{.}\)”
Example 4.1.6.
The number \(27\) is divisible by \(9\) since \(27 = 9 \times 3\text{.}\) So, \(9|27\text{.}\)
The number \(-44\) is divisible by \(11\) since \(-44 = 11 \times (-4)\text{.}\) Therefore, \(11|(-44)\text{.}\)
The number \(25\) is not divisible by \(6\) because there is no integer \(k\) that satisfies the equation \(25 = 6k\text{.}\) (The solution, \(25/6\text{,}\) is not an integer.) In that case, \(6\nmid 25\text{.}\)
Example 4.1.7.
Prove that if \(n\) is divisible by \(5\text{,}\) that \(15\) divides \(3n^2 - 6n + 30\text{.}\)
Again, try writing the proof yourself first. Remember that you are going to write \(n\) as \(5m\) for some integer \(m\text{,}\) and try to factor a \(15\) out of the resulting expression.
Proof.
Suppose that \(n\) is an integer that is divisible by \(5\text{.}\) That means there exists an integer \(m\) such that \(n=5m\text{.}\) In that case,
so if \(5|n\text{,}\) then \(15|(3n^2-6n+30)\text{.}\)