Guide to Proofs

Writing mathematical proofs is a skill that combines both creative problem-solving and standardized, formal writing. When you’re first learning to write proofs, this can seem like a lot to take in. However, there are certain patterns in proof writing that, once internalized, make the whole endeavor a lot easier. This page covers those patterns and is designed to help you take your first steps into Theoryland.

Direct Proofs: Implications

Implications are one of the most common types of statements you’ll encounter when writing mathematical proofs. As a reminder, an implication is a statement of the form

If $P$ is true, then $Q$ is true.

As a reminder, the antecedent of this implication is the statement “$P$ is true,” and the consequent of this implication is the statement “$Q$ is true.” For example, all of the following are implications:

If $n$ is an even integer, then $n^2$ is even.

If $m \in \mathbb{N}$, then there is a positive integer $n$ where $m^2 + mn$ is a perfect square.

If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.

Take a minute to confirm that you can identify the antecedents and consequents of these implications.

Because implications are so common, writing direct proofs of implications is fairly common as well. While the particulars of how to prove any individual implication vary, the good news is that all these proofs more or less follow the same basic structure. Specifically, you assume the antecedent is true, and then you prove the consequent is true. And indeed, that’s so core to how to prove implications using a direct proof that you can actually make progress on writing a proof of any implication even if you have no idea why the implication is true.

For example, let’s take the following (nonsense) implication:

If $x$ is a pizkwat, then $x$ is a squigglebah.

Even if we have no idea what a pizkwat or squigglebah are (spoiler: these aren’t real things), we could still start off a proof of this statement. Here’s what one might look like:

How do we know to do this? Well, if we want to prove this implication via a direct proof, we need to tell the reader to (1) we’re assuming the antecedent is true, and (2) we’re going to somehow establish that the consequent is true.

We call the first part of this proof (“Assume that $x$ is a pizkwat”) the assume step and the second part of this proof (“We need to show that $x$ is a squigglebah”) the want-to-show. The idea is that we’re making some assumption in the assume step, and our want-to-show now becomes the thing we need to prove with the rest of the argument.

When you’re first getting started writing proofs, we recommend wording things along the lines of what we’ve shown above. However, there are other equivalent ways of expressing this same idea. Here are some alternatives. Make sure you see why each of these says the same thing as what we’ve written above.

But regardless of what specific wording you use, the important thing is to

1. clearly state to your reader that you are assuming the antecedent is true, and
2. that you are going to prove that the consequent is true.

As in the case of this silly implication with pizkwats and squigglebahs, this applies even in the case where the implication is sufficiently complex that you don’t yet know why it’s true.

After we’ve written out the assume and want-to-show steps, we need to provide some line of reasoning that proves the want-to-show is true. In the case of the silly proof about pizkwats and squigglebahs, we’d need to show that x is indeed a squigglebah. Once we’ve done that, we can just tell the reader “hey, I did the thing I said I was going to do” and call it a day. That might look like this:

This last sentence therefore closes off the narrative arc. Our want-to-show told the reader that we’re done once we show $x$ is a squigglebah. Therefore, once we’ve done that, we can say “just like I promised!” and call it a day. Of course, the specific wording here isn’t required. Here’s another way we could do this:

To summarize, to prove an implication, do the following:

1. Write your assume step. This is where you assume the antecedent is true.
2. Write your want-to-show step. This is where you say that you will show the consequent is true.
3. Write the actual reasoning. Manipulate what you’re given in your assume step until you arrive at the claim you made in your want-to-show step. This is the creative part of the proof.
4. Return to your want-to-show. Indicate to the reader that you ended up where you said you were going to end up, and end the proof with a nice ■ symbol.

Exercises

As an (optional, not graded) exercise, try applying this rule to start off proofs of the following statements. As in the above cases, your goal isn’t to write the full proof. Instead, just write the first sentence or two, along with the last sentence.

1. If the Riemann Hypothesis is true, then P = NP. (These are real mathematical terms. We have no reason to believe that they’re related.)

   Solution

   We might start the proof like this:

   Proof: Assume the Riemann Hypothesis is true. We need to show that $\plangs = \nplangs \text{.}$

   ---

2. If every peganil number is also a retract, then each requint is wobbly. (These are nonsense terms. I made them up because they sound funny.)

   Solution

   We might start the proof like this:

   Proof: Assume all peganil numbers are retracts. We need to prove that every requint is wobbly. To do so, choose a requint $r\text;$ we need to prove that $r$ is wobbly.

   ---

3. If $M$ is a TM that halts on a string $w$, then $U_{TM}$ accepts $\langle M, w \rangle$. (You'll know what this means later in the quarter!)

   Solution

   We might start the proof like this:

   Proof: Let $M$ be a TM that halts on a string $w\text.$ We need to show that $U_{TM}$ accepts $\langle M, w \rangle\text{. }$

   ---

Direct Proofs: Universally-Quantified Statements

A universally-quantified statement is a statement that makes a claim about all objects of some type. Here are some examples:

For any integer $n$, the number $n(n + 1)$ is even.

For every set $S$, we have $\vert S \vert \lt \vert \wp(S) \vert$.

This first statement says something about all integers, and the second statement talks about all sets.

You might notice that these statements give a name to one of the objects being discussed. That first one talks about “for any integer $n$” and then goes on to use $n$ as a placeholder meaning “some integer,” while the second one talks about “for every set $S$,” allowing $S$ later on to refer back to some set. More generally, each universally-quantified statement will consist of two parts:

• A placeholder variable representing an object of some type.
• A claim about that placeholder variable that is true regardless of the choice made.

In some cases, you might not explicitly see a placeholder variable. For example, consider this universally-quantified statement:

Every natural number can be written as the sum of four perfect squares.

While this version doesn’t have a placeholder, we can easily add one in:

Every natural number $n$ can be written as the sum of four perfect squares.

The general pattern for proving a universally-quantified statement with a direct proof is as follows:

1. Instruct the reader to pick an arbitrary object of the appropriate type and give it a name.
2. Prove the object the reader has picked necessarily has the required property.

For example, let’s look at the most recent universally-quantified statement, the one about sums of four perfect squares. We could start off a proof of that result like this:

Let’s break down why this is written this way. We’ll begin with the first sentence (“Pick a natural number $n$.”) Why are we asking the reader to pick a natural number $n$? This convention has two purposes. First, it indicates that you, the person writing the proof, are not actually selecting any specific natural number to reason about. Instead, you’re telling the person reading your proof that they have full control here. They could choose $n$ to be whatever it is that they want it to be, with the tacit understanding that it’s not going to matter and that you’ll prove $n$ has some nice property regardless of that choice. Second, it gives a concrete meaning to the variable name $n$. In the statement of the theorem, the variable $n$ doesn’t actually refer to anything. It’s a placeholder for “whatever number you want it to be.” Therefore, to use $n$ in the proof, we need to ensure that $n$ is given some specific meaning so that its value can’t change from sentence to sentence.

As a note, “pick a natural number $n$” is not the only way to write this out. All of the following work just as well here:

• Consider a natural number $n$.
• Let $n \in \mathbb{N}$ be an arbitrary natural number.
• Fix some $n \in \mathbb{N}$. (Note: “fix” here means “pin down,” not “repair.”)
• Choose some $n \in \mathbb{N}$.

Now, let’s look at the next sentence (“We want to show that […]”). This sentence articulates what our new goal is – all we have to do to get the proof to work is show that this value $n$ that the reader picked can be written as the sum of four squares. Although the statement we’re proving, as written, isn’t an implication, this sentence functions as a “want-to-show” step for the rest of the proof. Once you have established the claim you’ve made here, you’re done, and the proof is over. So, for example, the general shape of the proof here should look like this:

To summarize, a proof of a universally-quantified statement proceeds in these steps:

1. Tell the reader to make an arbitrary choice. This is where you introduce a variable representing some value that the reader gets to pick. Importantly, state what the name of the variable is, and clearly indicate that you as the proof writer aren’t telling the reader which specific choice to make.
2. State your want-to-show. This will be that the variable introduced in the previous sentence has some specific property.
3. Write the actual reasoning. This is where you use properties common to the type of object being chosen to arrive at the destination. It’s the creative step of the proof.
4. Call back to your want-to-show. Once you’ve arrived at the statement you said you were going to arrive at, you’re done! Point that out and draw a nice box.

The general shape of your proof will look like this even if you don’t know the specifics of why it’s true.

Exercises

As another (optional, not graded) exercise, take the statements shown here and sketch out what the shape of the proof might look like.

1. For every NFA $N$, there is a DFA $D$ where ${\scr{L}}(N) = {\scr{L}}(D)\text.$ (You'll learn what this means later this quarter!)

   Solution

   We might start the proof like this:

   Proof: Pick some NFA $N\text.$ We need to show that there is a DFA $D$ where ${\scr{L}}(N) = {\scr{L}}(D)\text.$

   ---

2. For every integer $n$, there are integers $r$ and $s$ where $r^2 - s^2 = 4n$. (Great exercise!)

   Solution

   We might start the proof like this:

   Proof: Let $n$ be an arbitrary integer. We need to show that there are integers $r$ and $s$ where $r^2 - s^2 = 4n\text.$

   ---

3. Every Siegel field has a cofinal attractor. (These are mathy-sounding terms I made up. They aren’t real things.)

   Solution

   Remember that if you don’t see a named variable in the universally-quantified statement, it’s probably a good idea to rewrite the statement to add one.

   Proof: Let $S$ be a Siegel field. We need to prove that $S$ has a cofinal attractor.

   ---

Unpacking Compound Statements

It’s common to see statements that combine together a universally-quantified statement and an implication. For example, take this statement:

For any integer $n$, if $n$ is even, then $n^2$ is even.

This statement is a mix of a universally-quantified statement on the outside and an implication on the inside. You can see this here:

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

So – how should we prove this? If we follow the template for a universally-quantified statement, we’d write out the following:

Notice that our want-to-show here is itself an implication, and our goal is now to prove the want-to-show. So we can then ask – how do you prove an implication? Well, we saw that earlier as well: you assume the antecedent and prove the consequent. That looks like this:

Notice what we did here. Immediately after our initial want-to-show, we said that we are going to assume $n$ is even (assuming the antecedent of our implication) and then show that $n^2$ is even (making the consequent of our implication the new want-to-show). From this point, all we have to do is prove that $n^2$ is even, and we’re done.

This pattern – writing out an initial want-to-show and then expanding that out into another want-to-show – is something we call unpacking. You can think of it as breaking a larger problem down into some simpler pieces. The original, big goal is “prove a universally-quantified statement.” We simplified that to “prove an implication.” We’ve reduced further to “prove $n^2$ is even.” We’re therefore “unpacking” our want-to-show statement to reveal the smaller pieces it’s made of.

In the specific case of a universally-quantified implication (“for any $x$, if $P$ is true, then $Q$ is true”), it’s often a bit easier to combine the introduction of the variable from the quantified bit and the assumption from the antecedent. For example, the above proof could also be written in the following way:

This means exactly the same thing as what was shown above, since in both cases we end up with $n$ being (1) an integer (2) whose value we don’t control and (3) that is even.

As another example, consider this (nonsense) implication:

For any woozle $x$, if $x$ is cretacular, then $x$ is whiphithi.

We could unpack this as follows:

Take a minute to look back at the statement of the theorem. How did we get from there to our assume step? How did we get from there to our want-to-show step? And, importantly, note that we don’t have to have even the faintest inkling of what these terms mean to get to this point in the reasoning.

Exercises

Based on what you’ve seen here, try setting up proofs of the following statements. Again, you aren’t required to do so, and it’s not graded, but it is great practice.

1. For all languages $L$, if $L$ is regular, then $\bar{L}$ is regular. (You’ll understand this by Week 7.)

   Solution

   Here's one option:

   Proof: Let $L$ be a regular language. We need to prove that $\bar{L}$ is regular.

   ---

2. For any rectible integer $x$, if $x$ is Egan-prime, then $G[x, 2]$ is unobserved. (These are mathy-sounding terms that I made up and have no basis in reality.)

   Solution

   Here's one option:

   Proof: Choose a rectible integer $x$ that is Egan-prime. We need to prove that $G[x, 2]$ is unobserved.

   ---

3. For any integers $x$, $y$, and $z$, if $x^2 + y^2 = z^2$, then $(x+1)^2 + (y+1)^2 \ne (z + 1)^2$. (This is actually a great problem to try on your own!)

   Solution

   Here's one option:

   Proof: Pick integers $x\text,$ $y\text,$ and $z$ where $x^2 + y^2 = z^2\text.$ We need to prove that $(x+1)^2 + (y+1)^2 \ne (z+1)^2\text.$

   ---

Direct Proofs: Existentially-Quantified Statements

An existentially-quantified statement is one that states that there is at least one object with some property. As opposed to universal statements, which say that something is always true, an existential statement just says that it’s true at least once.

For example, here are some sample existential statements:

There is a positive integer $n$ equal to the sum of all smaller positive integers. There is a one-state NFA $N$ that does not accept all strings.

As with universally-quantified statements, an existentially-quantified statement consists of two pieces:

• A placeholder variable representing an object of some type.
• A claim about that placeholder variable that is true for at least one choice of that variable.

As with universally-quantified statements, some existentially-quantified statements don’t explicitly include a variable. In that case, you can just add one in. For example, take this (nonsense) statement:

There is a swipestone that is edurable.

We could rewrite this as

There is a swipestone $x$ such that $x$ is edurable.

Because existentially-quantified statements claim that some object exists with some property, the general pattern for proving an existentially-quantified statement with a direct proof is to simply find what that object is and then prove it indeed has the needed properties. You typically do this by writing something to this effect:

The key difference between this style of proof and a proof of a universally-quantified statement is that, in this case, we are specifically telling the reader what object we’re picking. We very specifically do not want to tell the reader “pick anything you’d like here,” because chances are the claim isn’t going to be true for most choices!

Things get most interesting when you combine together a universally-quantified statement and an existentially-quantified statement. For example, consider this statement:

For any integer $n$, there are integers $r$ and $s$ where $r^2 - s^2 = 4n$.

Notice how this is structured:

\[\begin{aligned} &\text{For all integers }n, && \text{(a universally-quantified statement)} \\ &\quad \text{there are integers }r\text{ and }s\text{ where }r^2 - s^2 = 4n && \text{(an existentially-quantified statement)} \end{aligned}\]

Since we have one statement nested inside another, we will have to unpack as we go. We’ll begin by writing out our general template for a universally-quantified statement:

Now, what will that actual logic look like? This is where we need to get creative and actually find choices of $r$ and $s$ that work here. But even if we don’t know what the ultimate choices of $r$ and $s$ will be, we can still outline the rest of the proof. It will look something like this:

A great exercise: what choices of $r$ and $s$ should you make here?

Direct Proofs: Biconditionals

A biconditional is a statement of the form

$P$ is true if and only if $Q$ is true.

In other words, it's a statement that says "whenever $P$ is true $Q$ is true, and whenever $Q$ is true $P$ is true." For example, we might have something like one of these statements:

If $n$ is an integer, then $n$ is even if and only if $n^2$ is even.

There is a DFA $D$ for a language $L$ if and only if there is an NFA $N$ for language $L$.

Statements like these say that two things are equivalent to one another - the expression on the right means the exact same thing as the expression on the left.

How do you prove a biconditional statement? Well, if you think about it, a biconditional consists of two separate implications. The statement

$P$ is true if and only if $Q$ is true

is equivalent to

If $P$ is true then $Q$ is true, and if $Q$ is true then $P$ is true.

Because a biconditional essentially boils down to two separate and smaller implications, the general strategy for proving a biconditional is to write out two separate proofs, one for each of the two implications.

To see what this looks like, let's take this (nonsense) biconditional:

For any $x$, $x$ is spirocontractive if and only if $x$ is chiroshrinking.

Here's how we might set up a proof of that result:

In other words, it's basically two proofs of two separate implications, essentially glued together one after the other.

Proof by Contrapositive

(Covered in Lecture 02)

Sometimes, when proving an implication, you’ll find that your reasoning via a direct proof is getting messy and complicated, or you’ll just flat-out get stuck and unable to make progress. If that happens, save what you have somewhere, and then try instead to write a proof by contrapositive.

In a proof by contrapositive, instead of proving the original implication, you'll prove a different implication. Specifically, instead of proving the statement

If $P$ is true, then $Q$ is true,

you'll prove the statement

If $Q$ is false, then $P$ is false.

This second statement is called the contrapositive of the first statement, hence “proof by contrapositive.”

When writing a proof by contrapositive, we recommend structuring the proof as follows:

1. Start off by announcing that you're going to prove the contrapositive of the statement you wish to prove. For example, you could say something like “We will prove the contrapositive of this statement, namely, that …” or “By contrapositive; we will instead prove that …”

   Don't skip this step! It's important for several reasons. First, it communicates to the reader what they should expect in the proof: you're not going to prove the original statement, and instead that you're going to prove the contrapositive. Second, it forces you to write out the contrapositive of the statement that you're trying to prove, reducing the likelihood that you accidentally take the contrapositive incorrectly.

2. Using any proof technique you'd like, prove the contrapositive of the statement. Often, you'll prove the contrapositive of the statement using a direct proof. Overall, this means that if you want to prove the statement “If P is true, then Q is true,” you'll start off by assuming that Q is false and will prove that P is false.

Proof by contrapositive is useful for proving implications, but can also be used to prove certain other results that don't necessarily look like implications. For example, consider this (nonsense) statement:

All omnesiacs are amniscient.

This statement doesn't look like an implication, but it can actually be thought of as one. Specifically, it's equivalent to the statement

For all $x$, if $x$ is an omnesiac, then $x$ is amniscient.

Now, it's clearer that there's an implication here, so if we chose to do so, we could prove it using a proof by contrapositive. That proof might start out like this:

Proof by Contradiction

(Covered in Lecture 02)

One of the most common and most powerful forms of indirect proof is the proof by contradiction. In a proof by contradiction, to prove that some statement $X$ is true, you instead assume that $X$ is false, then proceed to derive an impossible statement (a contradiction). This means that $X$ cannot be false, and therefore $X$ has to be true.

We recommend writing proofs by contradiction along these lines:

1. Start off by saying that you're going to write a proof by contradiction. For example, you could write “Assume for the sake of contradiction that …” or “By contradiction; assume that ….” Then, explicitly write out the negation of the statement you're trying to prove.

   Analogously to a proof by contrapositive, it's important to actually write out the negation of what you want to prove. This communicates to the reader what assumptions you're making and forces you to put into writing what you believe the negation of the statement is. It therefore makes the proof easier to read and reduces the chances that you accidentally take the negation of the statement incorrectly.

2. Starting with your assumption from part (1), proceed to conclude something impossible, such as that $1 = 0$, that a number is both even and odd, that something is an element of the empty set, that $\vert S \vert = \vert \wp(S) \vert$, etc.

3. State that you've reached a contradiction and, if it's not obvious, explain why it's a logical contradiction. This explains to the reader why your assumption couldn't possibly be right.

4. Conclude the proof. I commonly say something to the effect of “We have reached a contradiction, so our assumption must have been wrong, so […].” You can put whatever you'd like here as long as it explains why the contradiction you arrived at actually shows that the original assumption was incorrect.

One of the trickiest parts of writing a proof by contradiction is properly assuming the opposite of what you want to prove. When we talk about first-order logic later in a few weeks, you'll see several techniques for negating statements and you'll get a better feel for how to do this in general. For now, though, we recommend that you use the following set of rules and your own intuition.

Here are some common types of statements and their negations.

\[\begin{array}{c | c} \textbf{If you want to prove this by contradiction...} & \textbf{... assume this.} \\ \hline \text{All }P\text{'s are }Q\text{'s} & \text{Some }P\text{ is not a }Q \\ \hline \text{No }P\text{'s are }Q\text{'s} & \text{Some }P\text{ is a }Q \\ \hline \text{Some }P\text{'s are }Q\text{'s} & \text{All }P\text{'s are not }Q\text{'s} \\ \hline \text{Some }P\text{ is not a }Q & \text{All }P\text{'s are }Q\text{'s} \\ \hline \text{If }P\text{ is true, then }Q\text{ is true} & P\text{ is true and }Q\text{ is false} \\ \hline P\text{ is true and }Q\text{ is true} & P\text{ is false, or }Q\text{ is false, or both are false} \\ \hline P\text{ is true, }Q\text{ is true, or both are true} & P\text{ is false and }Q\text{ is false} \\ \end{array}\]

Exercises

Below are some optional exercises you can work through to practice the skills covered in this guide. We won't collect any of these for credit; they're here purely to let you put these concepts into practice for your own benefit.

1. Consider the following implication:

   "If my friend brings me ice cream, then I will be happy."

   What is the antecedent of this implication? What is the consequent?

   Solution

   The antecedent is the statement "my friend brings me ice cream." The consequent is "I will be happy."

   ---

2. Consider the following statement:

   "Your car will be towed if you park here."

   This statement is not written in the typical "if… then…" that we used in lecture, but it is still an implication. What it its antecedent? What is its consequent?

   Solution

   The antecedent is "you park here" and the consequent is "your car will be towed." This may seem surprising given that "your car will be towed" comes first, but it's a bit easier to see if you realize the above statement can be rewritten as "if you park here, then your car will be towed."

   ---

3. Suppose you want to prove the following:

   Theorem: For all natural numbers $m$ and $n\text,$ if $m$ is odd and $n$ is odd, then $m^2 + n^2$ is odd.

   Which of the following options is a better way to begin the proof?

   1. "Let $m$ and $n$ be odd natural numbers. We need to prove that $m^2 + n^2$ is odd."

   2. "Pick $m = 3$ and $n = 5\text.$ We will prove that $m^2 + n^2$ is odd."

   Solution

   The theorem we want to prove is a universally-quantified statement: for all natural numbers, something is true about those numbers. Therefore, the proper way to set up this proof is to have the reader choose $m$ and $n$ to be odd, and then we argue that $m^2 + n^2$ is odd. Option (1) thus works well here. However, option (2) would not be correct. Just checking that the theorem is true for $m = 3$ and $n = 5$ is not sufficient to show that the result works regardless of what odd numbers $m$ and $n$ are.

   ---

4. Suppose you want to prove the following:

   Theorem: There exist odd natural numbers $m$ and $n$ where $m^2 + n^2 = 34\text.$

   Which of the following options is a better way to begin the proof?

   1. "Let $m$ and $n$ be odd natural numbers. We need to prove that $m^2 + n^2 = 34\text.$"

   2. "Pick $m = 3$ and $n = 5\text.$ We will prove that $m^2 + n^2 = 34\text.$"

   Solution

   The theorem we want to prove is an existentially-quantified statement: there exists odd natural numbers where something is true about those numbers. Therefore, the proper way to set up this proof is to give concrete examples of odd natural numbers that work, then justify why they are correct. Option (2) thus works here. Option (1), however, would be what we'd do if we wanted to prove a universally-quantified statement. That's not the case here, nor is it true that any odd $m$ and $n$ will have the necessary properties.

   ---

5. Prove for all integers $m$ and $n$ that if $m$ and $n$ are odd, then $mn$ is odd.

   Solution

   This is a universally-quantified statement with an implication in it. We will therefore

   • ask the reader to choose integers $m$ and $n$
   • that are odd, then
   • prove $mn$ is odd too.

   Here is what that looks like:

   Proof: Pick odd integers $m$ and $n\text.$ We need to show that $mn$ is odd.

   Since $m$ and $n$ are odd, there are integers $r$ and $s$ where $m = 2r+1$ and $n = 2s + 1\text.$ This means that

   \[\begin{aligned} mn &= (2r+1)(2s+1) \\ &= 4rs + 2r + 2s + 1 \\ &= 2(2rs + r + s) + 1\text. \end{aligned}\]

   This means that there is an integer $q$ (namely, $2rs + r + s\text)$ such that $mn = 2q + 1\text.$ Thus $mn$ is odd. $\qed$

   ---

6. Prove for all integers $n$ that if $n$ is even, then there are odd integers $r$ and $s$ where $n = r + s\text.$

   Solution

   This proof combines both a universal portion ("for all integers…") and an existential portion ("there are odd integers…"). Our proof will thus start off by asking the reader to choose $n\text,$ but at that point we need to come up with choices of $r$ and $s$ that work. This is where we need to search around a bit, look for a pattern, and prove our pattern holds.

   The good news is that there are a lot of ways to write $n = r + s$ where $r$ and $s$ are odd. One easy way is to pick $r = 1$ and $s = n - 1\text.$ We just need to justify that those are odd. Here's what this looks like:

   Proof: Pick any even integer $n\text.$ We need to show there are odd integers $r$ and $s$ where $n = r + s\text.$

   Specifically, pick $r = 1$ and $s = n-1\text.$ We see that $r$ is odd because $1 = 2 \cdot 0 + 1\text.$ To see that $s$ is odd, first note that, since $n$ is even, there is an integer $k$ where $n = 2k\text.$ Then we see that

   \[\begin{aligned} n - 1 &= 2k - 1 \\ &= 2k - 2 + 1 \\ &= 2(k - 1) + 1\text, \end{aligned}\]

   so there is an integer $q$ (namely, $k - 1\text)$ where $n - 1 = 2q + 1\text,$ so $s$ is odd.

   Finally, note that $r + s = 1 + (n - 1) = n\text.$ Thus $r$ and $s$ are odd and $r + s = n\text,$ as required. $\qed$

   ---

7. What is the negation of the following statement?

   "There is a natural number $n$ where $n(n+1)$ is a perfect square."

   Solution

   This is an existentially-quantified statement, so its negation will be universally-quantified. One simple answer is "for every natural number $n\text,$ the number $n(n+1)$ is not a perfect square."

   ---

8. What is the negation of the following statement?

   "If someone is happy, then everyone is happy?"

   Solution

   This one is trickier than it might seem at first glance. Remember that the negation of the implication "if $P\text,$ then $Q$" is "$P$ and not $Q$." In this case, that means that our negation will have the form

   Someone is happy and it is not the case that everyone is happy.

   Of course, that last part, "it is not the case that everyone is happy," can itself be further simplified. The statement "everyone is happy" is universally-quantified. Its negation is the existentially-quantified statement "someone is not happy." Therefore, our overall negation is

   Someone is happy and someone is not happy.

   It's worth thinking this over for a bit. If it's the case that someone is happy and someone is not happy, why does that mean the original statement is false? If the original statement is true, why does it mean that "someone is happy and someone is not happy" is false?

   ---

9. What is the contrapositive of the following statement?

   "If $mn$ is even, then $m$ is even or $n$ is even."

   Solution

   The contrapositive of "if $P$ is true, then $Q$ is true" is "if $Q$ is false, then $P$ is false." Here, $P$ is "$mn$ is even," and $Q$ is "$m$ is even or $n$ is even. The negation of $P$ would be "$mn$ is odd." Now, $Q$ is an "or" between two options, and from the table earlier in this guide we see that the negation of "$A$ or $B$" is "not $A$ and not $B$." Putting this all together, we get the following:

   If $m$ is odd and $n$ is odd, then $mn$ is odd.

   And hey! That's something you proved earlier.

   ---

10. What is the contrapositive of the following statement?

    "If someone is happy, then everyone is happy."

    Solution

    To form a contrapositive, we swap the antecedent and consequent and negate both parts. So we can start off with this:

    If "everyone is happy" is false, then "someone is happy" is false.

    How do we simplify this? Well, the statement "everyone is happy" is universally-quantified, so its negation is the existentially-quantified statement "someone is not happy." The statement "someone is happy" is existentially-quantified, so its negation is the universally-quantified statement "everyone is not happy." This gives us our solution:

    If someone is not happy, then everyone is not happy.

    This means the exact same thing as the original implication we started with. It's worth thinking about why that is.

    ---

11. A natural number $n$ is called a triangular number if there is a natural number $k$ where $n = \frac{k(k+1)}{2}\text.$ We'll explore triangular numbers more later in the quarter.

    Prove the following using a proof by contrapositive: for all natural numbers $n\text,$ if $9n+1$ is not a triangular number, then neither is $n\text.$

    Solution

    The first step in doing a proof by contrapositive is figuring out what the contrapositive is. We are dealing with the following implication:

    If $9n+1$ is not a triangular number, then neither is $n\text.$

    Its contrapositive is

    If $n$ is a triangular number, then so is $9n+1\text.$

    Now, all we have to do is prove that via a direct proof. This is going to look similar in spirit to what we do with odd and even numbers, just with $\frac{k(k+1)}{2}$ instead of $2k$ or $2k+1\text.$ Here's what that looks like:

    Proof: We will prove the contrapositive, namely, that if $n$ is a triangular number, then so is $9n+1\text.$ So let $n$ be a triangular number; we'll prove $9n+1$ is as well.

    Since $n$ is triangular, there exists a natural number $k$ such that $n = \frac{k(k+1)}{2}\text.$ This means that

    \[\begin{aligned} 9n + 1 & = \frac{9(k(k+1))}{2} + 1 \\ & = \frac{9k^2 + 9k + 2}{2} \\ & = \frac{(3k+1)(3k+2)}{2} \\ & = \frac{(3k+1)((3k+1)+1)}{2} \end{aligned}\]

    Thus there is a natural number $m$ (namely, $3k + 1\text)$ such that $9n + 1 = \frac{m(m+1)}{2}\text,$ meaning that $9n+1$ is a triangular number, as required. $\qed$

    ---

12. A real number $x$ is called a whimsical number when there exist natural numbers $a$ and $b$ such that $x = a + b\sqrt{137}\text.$ Prove, using a proof by contrapositive, that for any real numbers $a$ and $b\text,$ if $ab$ is not whimsical, then at least one of $a$ and $b$ is not whimsical.

    Solution

    OUr first task is to figure out what the contrapositive is. We can begin by swapping the antecedent and consequent and negating both:

    If "at least one of $a$ and $b$ is not whimsical" is false, then $ab$ is whimsical.

    With a bit of thought, we can realize that the antecedent of this new implication means "$a$ and $b$ are not whimsical." That gives us our final contrapositive:

    If $a$ and $b$ are whimsical, then so is $ab\text.$

    Now, all that's left to do is prove this:

    Proof: We will prove the contrapositive of this statement, namely, that if $a$ and $b$ are whimsical, then $ab$ is whimsical.

    Pick some whimiscal numbers $a$ and $b\text.$ We need to show that $ab$ is whimsical. Since $a$ and $b$ are whimsical, we know that there are natural numbers $m$, $n$, $p$, and $q$ such that $a = m + n\sqrt{137}$ and $b = p + q\sqrt{137}\text.$ We then see that

    \[\begin{aligned} ab &= (m + n \sqrt{137})(p + q \sqrt{137}) \\ &= mp + mq \sqrt{137} + pn \sqrt{137} + 137nq \\ &= (mp + 137 nq) + (mq + pn) \sqrt{137}\text. \end{aligned}\]

    This means that there are natural numbers $r$ and $s$ (namely, $mp + 137nq$ and $mq + pn\text)$ such that $ab = r + s\sqrt{137}\text,$ so $ab$ is whimsical, as required. $\qed$

    ---

13. You have twenty red balls and three boxes. You distribute those balls into the boxes. Prove by contradiction that some box has an even number of balls in it.

    Solution

    When approaching a proof by contradiction, our first step should always be to write out the negation of the statement to prove. After all, we'll be assuming the negation is true, and so we need to know what we're assuming. In our case, the statement to prove is "some box has an even number of balls in it." This is an existentially-quantified statement: it says that out of the boxes we can always find at least one that has an even number of balls in it. Its negation is therefore the following universally-quantified statement:

    Every box has an odd number of balls in it.

    From here, we need to explain why that's not possible. With a little thought, we can realize that if you have three boxes, each with an odd number of balls in it, then you must have an odd total number of balls - but that's not possible because we have 20 balls and 20 is even.

    Here's what that looks like, written up as a formal proof:

    Proof: Assume for the sake of contradiction that all three boxes have an odd number of balls in them. Denote the number of balls in the three boxes as $m\text,$ $n\text,$ and $p\text.$ We note, since there are 20 total balls, that $m + n + p = 20\text.$

    Since $m\text,$ $n\text,$ and $p$ are odd, there exist integers $j\text,$ $k\text,$ and $l$ such that $m = 2j+1\text,$ $n = 2k+1\text,$ and $p = 3l+1\text.$ Then we see that

    \[\begin{aligned} m + n + p &= (2j+1) + (2k+1) + (2l+1) \\ &= 2j + 2k + 2l + 3 \\ &= 2(j + k + l + 1) + 1\text, \end{aligned}\]

    so there is an integer $q$ (namely, $j + k + l + 1\text)$ where $m + n + p = 2q+1\text,$ so $m + n + p$ is odd. But that's impossible, since $m + n + p = 20 = 2 \cdot 10$ is even.

    We've reached a contradiction, so our assumption was wrong and some bin has an even number of balls in it. $\qed$

    ---