PS1, Part 2: Proof Writing and Proof Techniques

Problem Four: Writing Direct Proofs

It’s time to write your first proofs! Over the next three problems, we’ll walk you through three proofs of three different theorems. A key theme throughout these problems is

☞ the structure of a theorem dictates the structure of the proof. ☜

That is, the way the theorem is written gives the high-level structure of how the proof will be written. Indeed, you can make progress toward proving a theorem simply by “unpacking” the statement of the theorem to figure out what needs to happen and when.

In this problem, you will write a direct proof of this theorem:

Theorem: For all integers $n$, if $n$ is odd, then $n^2$ is odd.

For example, we see that $3$ is odd, and $3^2 = 9$ is odd as well.

Remember that the structure of a direct proof is dictated by the sentence structure of the theorem. In this case, our theorem looks like this:

\[\begin{aligned} &\text{For all integers }n, && \text{(a universally-quantified statement)} \\ &\quad\text{if }n\text{ is odd,} && \text{(the antecedent of an implication)} \\ &\quad\quad\text{then }n^2\text{ is odd.} && \text{(the consequent of an implication)} \end{aligned}\]

Take a look back at the Guide to Proofs, the slides from our lecture on mathematical proofs, or the Proofwriting Checklist, for a refresher about how to work with universally-quantified statements and implications.

We want to extract from the sentence structure of our theorem the two foundations of our direct proof. The first is the starting point of the proof, which we call the assume step. Here, you’ll pick an arbitrarily-chosen value meeting the requirements of the antecedent of the implication. The second is the destination of the proof, which we call the want-to-show step. Here, that’s the consequent of the implication.

It is important to note that the want-to-show is not the entire theorem, although that might seem like the obvious thing to say since you clearly do want to show it! Think of the pair as like a start and destination of driving directions, and want-to-show is just the name of the destination.

Write the first sentence of this proof (the assume step).

Ours starts with the word “pick,” but there are other valid options listed in the Guide to Proofs and Proofwriting Checklist.

Write the second sentence of this proof (the want-to-show step).

Ours starts with the words “We want to show that…”

Now complete the proof, using this template as a guide, and copying in the two sentences you wrote above. The sizes of the blanks are not necessarily to scale.

Notice that the first two sentences of a direct proof follow mechanically from the structure of the theorem. The third sentence in this example is also illustrative of a very common pattern for third sentences, which is to expand a definition from the “assume” sentence (in this case, the definition of odd integers).

Theorem: For any integer $n$, if $n$ is odd, then $n^2$ is odd.

Proof: Pick $\blank$. We want to show that $\blank$. Since $n$ is odd, there is an integer $k$ where $\blank$. (Note: When following the direct proof guidelines, the first three sentences are fairly mechanical, but now we need to exercise actual creativity. It helps to look at our want-to-show to remind ourselves of our destination on this journey. It says we want to show something about $n^2$, so we will begin with the expression $n^2$, and then apply algebra to it.) Then we see that
\[\begin{aligned} n^2 & = \blank \\ & = \blank \\ & = \blank. \end{aligned}\]
Therefore, there is an integer $m$ (namely, $\blank$) such that $\blank$, so $\blank$ (write your “Want to Show” statement here to announce that you’ve proved it), as required. ■

In the conclusion of the proof, the template has you using a variable named $m$ to show that $n^2$ is odd. The definition of odd integers from the lecture slides uses a variable $k$ for this purpose. Why did we choose $m$ here instead? Could we have used $k$?

Problem Five: Writing Proofs by Contrapositive

You’ve now written your first direct proof – great job! Let’s move on to our next proof technique, the proof by contrapositive. In this problem, you’ll use a proof by contrapositive to prove this theorem:

Theorem: For all integers $a$, $b$, and $c$, if $a^2 + b^2 = c^2$, then at least one of $a$, $b$, and $c$ is even.

Proof by contrapositive is another technique for theorems with a sentence structure that has the form of an implication. In fact, proof by contrapositive will proceed exactly like a direct proof, with similar “assume” and “want-to-show” steps, but will do so only after taking the contrapositive of the theorem to get a new, equivalent statement to prove.

What is the contrapositive of the theorem?

Since the “for all” part comes before the “if” that begins the implication, the “for all” part remains unchanged by taking the contrapositive. Be very careful how you negate the “at least one of.”

Write the “assume” sentence of your proof, based on the antecedent of the contrapositive.

Write the “want-to-show” sentence of your proof, based on the consequent of the contrapositive.

Complete the proof, using this template as a guide, and copying in the two sentences you wrote above. As before, the sizes of the blanks are not necessarily to scale.

Theorem: For any integers $a$, $b$, and $c$, if $a^2 + b^2 = c^2$, then at least one of $a$, $b$, and $c$ is even.

Proof: We will prove the contrapositive of this statement, namely, $\blank$. To do so, pick $\blank$. We want to show that $\blank$.

Since $a$, $b$, and $c$ are $\blank$, we know by our result from the previous problem that $a^2$, $b^2$, and $c^2$ are $\blank$.

Because $a^2$ and $b^2$ are $\blank$, there exist integers $p$ and $q$ such that $\blank$. This means that $a^2 + b^2 = \blank = \blank$, which means that $a^2 + b^2$ is $\blank$.

However, as mentioned earlier we know that $c^2$ is $\blank$. Therefore, we see that $\blank$ (write your “Want to Show” statement here to announce that you’ve proved it), as required. ■

In the above proof, we expanded the definition of odd for two values that we know are odd, $a^2$ and $b^2$. However, notice that we didn’t expand out the definition of odd for $c^2$ (e.g. "Since $c^2$ is odd, we know there's an integer …"), even though we know that $c^2$ is an odd number. While factually it wouldn’t be incorrect to expand out what it means for $c^2$ to be odd, it would be have been stylistically incorrect, since doing so would violate one of the rules from the Proofwriting Checklist.

What rule from the Proofwriting Checklist would have been violated if we had expanded out the definition of “$c^2$ is odd” in the above proof?

Problem Six: Writing Proofs by Contradiction

We’ve just checked off direct proofs and proofs by contrapositive. That leaves us with proofs by contradiction, which are the focus of this problem.

Your task in this problem is to prove the following theorem:

Theorem: For all integers $m$ and $n$, if $mn$ is even and $m$ is odd, then $n$ is even.

When writing a proof by contradiction, in your “assume” step you’ll simply assume the negation of the theorem to prove.

What is the negation of the above theorem?

Remember: The negation of an implication is not an implication! Refer back to the lecture slides for how to negate an implication. Check the appendix to Lecture 02 for more details.

Once you’ve written the “assume” state in a proof by contradiction, you won’t explicitly articulate a “want-to-show” the way you did for a direct proof or a proof by contrapositive. Rather, by simply informing the reader that you’re going to proceed by contradiction, you’re implicitly telegraphing “oh, and by the way, I’m going to find two contradictory facts that follow from this assumption.” Therefore, rather than explicitly stating a “want to show” sentence like you did in the previous proofs, you’ll simply start exploring from your assumption, then indicate once you’ve reached a contradiction.

Fill in the blanks below to complete this proof by contradiction. As before, the relative sizes of the blanks are not necessarily indicative of how much you need to write.

Theorem: For any integers $m$ and $n$, if $mn$ is even and $m$ is odd, then $n$ is even.

Proof: Assume for the sake of contradiction that $\blank$. Since $m$ is $\blank$, we know that there is an integer $k$ where $\blank$. Similarly, since $n$ is $\blank$, there is an integer $r$ where $\blank$. Then we see that
\[\begin{aligned} mn & = \blank \\ & = \blank \\ & = \blank, \end{aligned}\]
which means that $mn$ is $\blank$, but this is impossible because $\blank$.

We have reached a contradiction, so our assumption must have been wrong. Therefore, if $mn$ is even and $m$ is odd, then $n$ is even. ■