Proofs

Exercise 7.1. You’re about to leave on holiday, but you forgot to pack socks! You’ve ran back to your room, but the light’s burnt out, so you can’t see the colours of your socks.

You know that in your sock drawer that there are ten pairs of green socks, ten pairs of black socks, and eleven pairs of blue socks (all mixed up.)

How many of your socks do you need to take before you can be sure you’ve grabbed at least one matching pair?

Exercise 7.2. You’re a mad scientist! You’ve conducted an experiment on yourself to get superpowers. It worked, but to keep the powers you need to take two different tablets each day; if you forget one, or take more than one of either type, you’ll, um, explode.

Unfortunately, they look completely identical, and you’ve just dropped your last two days of supply (four tablets) on the floor.

What can you do?

Proofs: Motivation and Fundamentals

Throughout this coursebook, we’ve stressed the importance of clear, logical explanations for why things are true. In our previous chapters, we motivated the need for these arguments in a number of ways:

• In our answer to Exercise 1.1, we said that making a good, logical argument is often a useful skill in the workplace! In real life, you will often have to work for people who aren’t particularly “tech-y” and will expect you to be able to do literally impossible tasks. Being able to give a clear and patient explanation for why something can never happen is a good skill to have!

• In our argument for Claim 1.1, we explained why an argument that just checks a few hundred or even a few thousand cases is often not enough in mathematics and computer science. As we saw then, there are tons of examples of claims that are true for all of the small values you’d like to check, but that suddenly become completely false when you get to large values (i.e. the ones that you could encounter when running code!)

• Finally, in chapter 4 we studied algorithms, step-by-step processes that we could easily turn into computer programs. When doing so, we often added in discussions about why these algorithms were “guaranteed” to work or why these algorithms would never “crash;” these arguments made it so that we could trust these processes to always work.

  This is something that you do in real life as a computer scientist all the time! Good code involves carefully thinking about all of the possible inputs you could be given, and for each case ensuring that your code is well-behaved. Writing such code and documenting it in a way that others can understand is a key part of being a professional programmer!

These motivations aren’t just hypotheticals! Here’s a pair of stories that illustrate why knowing how to make logical arguments is a useful skill:

Story 7.1. Janelle Shane is a researcher in optics who works with neural networks and machine learning. Roughly speaking, the way that a neural network works is the following:

• Take a bunch of examples of the thing you want the neural network to recognize, as well as a bunch of nonexamples.
• “Show” the neural network these examples and nonexamples.
• The neural network will then come up with a set of rules that it believes describes what it means for.

“Show” is hard to define in words, but there are some great YouTube videos: see SethBling’s Mar I/O videos for a fun and accessible introduction!

People are often tempted to just use the results of a neural network directly, without checking whether its discovered rules make sense. Doing so, as Janelle notes, leads to some fascinatingly weird behaviour:

• “There was an algorithm that was supposed to sort a list of numbers. Instead, it learned to delete the list, so that it was no longer technically unsorted.”
• ” In 1997, some programmers built algorithms that could play tic-tac-toe remotely against each other on an infinitely large board. One programmer, rather than designing their algorithm’s strategy, let it evolve its own approach. Surprisingly, the algorithm suddenly began winning all its games. It turned out that the algorithm’s strategy was to place its move very, very far away, so that when its opponent’s computer tried to simulate the new greatly-expanded board, the huge gameboard would cause it to run out of memory and crash, forfeiting the game.”
• “An algorithm that was supposed to figure out how to apply a minimum force to a plane landing on an aircraft carrier. Instead, it discovered that if it applied a huge force, it would overflow the program’s memory and would register instead as a very small force. The pilot would die but, hey, perfect score.”

In short: just because something works for a bunch of examples doesn’t mean it’s good!

Story 7.2. A somewhat darker story on the importance of being able to read and understand proofs comes from the NSA, and something called a Dual Elliptic Curve Deterministic Random Bit Generator. This was an algorithm, designed by the NSA (a USA security agency,) that they claimed was a cryptographically secure way to generate random numbers.

However, this algorithm was one that the NSA had built a “backdoor” into. That is, they designed the algorithm around certain secret values so that anyone with knowledge of those values (i.e. the NSA) could predict the randomly-generated numbers with a higher-than-normal degree of accuracy and thereby defeat cryptographic systems using this algorithm.

The NSA managed to get their algorithm used as a “standard” for over seven years. However, many mathematicians and computer scientists were suspicious of the NSA’s algorithm from the very start, in large part because it was not something that was proven to work! Their research led to the eventual revocation of the NSA’s algorithm as a standard.

See the New York Times for an article summarizing the scandal.

Also, check out Kleptography: Using Cryptography Against Cryptography and Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, if you’d like to read through some research papers describing the NSA’s algorithm/its weaknesses.

So: we have some motivation for why we would want to write clear, logical arguments. The next question for us, then, is what counts as a valid argument?

Every major field of study in academia, roughly speaking, has a way of “showing” that something is true. In English, if you wanted to argue that the whale in Melville’s Moby Dick was intrinsically tied up with mortality, you would write an essay that quoted Melville’s story alongside some of of his other writings and perhaps some contemporary literature, and logically argue (using these quotations as “evidence”) that your claim holds. Similarly, if you were a physicist and you wanted to show that the speed of light is roughly $3.0 \cdot 10^8$ meters per second, you’d set up a series of experiments, collect data, and see if it supports your claim.

In mathematics, a proof is an argument that mathematicians use to show that something is true. However, the concepts of “argument” and “truth” aren’t quite as precise as you might like; certainly, you’ve had lots of “arguments” with siblings or classmates that haven’t proven something is true!

In mathematics, the same sort of thing happens: there are many arguments that (to an outsider) look like a convincing reason for why something is true, but fail to live up to the standards of a mathematician. In Chapter 1, we already studied a pair of “failed” proofs: namely, our first attempts at proving Claim 1.1 and Exercise 1.1. We said that these arguments failed because they did not work in general: that is, they only considered a few cases, and did not consider all of the possible ways to put dominoes on a chessboard, or to pick a pair of integers.

This, however, is not the only way in which a proof might fail us! Here’s another dodgy proof:

“Bad” proof:

A defense of the “bad” proof: We’re not using examples; we’re working in general! Also, we totally showed that this claim is true: after all, we started with our claim and turned it into a true thing!

Why this proof is not acceptable in mathematics:

• We have no idea what $x$ and $y$ are! In particular, by plugging in some sample values of $x$ and $y$ , we can see that this is sometimes true and sometimes false: for $x=1, y=4$ we do indeed have $\sqrt{xy} = \sqrt{4} = 2 \leq \frac{1+4}{2} = 2.5$ , but for $x=-1, y=-1$ the claim $\sqrt{(-1)\cdot(-1)} \leq \frac{-1-1}{2}$ is very false, as $-1 \not\leq 1$ ! So, to do anything here, we first need to know what $x$ and $y$ are. That is: we need to define what set $x,y$ come from!
• This proof is “backwards:” that is, it starts by assuming our claim is true, and from there gets to a true statement. This is not a logically sound way to make an argument! For example, if we assume that 1=2, we can easily deduce a true statement by multiplying both sides by 0:

This doesn’t prove that 1=2, though! As we said above, proofs need to start with true things, and then through argument get to what you’re trying to show.

• Finally, this proof has no words! This flaw in some sense is why the other two flaws could exist: if you had to write out in words what $x$ and $y$ were, and how you went from one line to the next, it would probably become clear that this proof was written backwards and also that we have to be careful with what $x, y$ are allowed to be.

This sort of thing is often easy to fix, though! If your proof is “backwards,” simply try starting from the end and reasoning your way backwards to the start. If your logic was flawed, somewhere along the way you’ll encounter a nonreversible step.

For example, if we tried to reverse our proof that $1=2$ , we could go from $0=0$ to $0 \cdot 1 = 0 \cdot 2$ , but would see that we can’t “divide by 0” to get to the desired conclusion (and thus that this doesn’t work.)

With this in mind, let’s try a “fixed” version of this proof:

Theorem 7.1. (The arithmetic mean-geometric mean inequality.) For any two nonnegative real numbers $x,y$ , we have that the geometric mean of $x$ and $y$ is less than or equal to the arithmetic mean of $x$ and $y$ : in other words, we have that

Proof. Take any pair of nonnegative real numbers $x,y$ . We know that any squared real number is nonnegative: so, in specific, we have that the square of $x-y$ , $(x-y)^2$ is nonnegative. If we take the equation $0 \leq (x-y)^2$ and perform some algebraic manipulations, we can deduce that

Because $x$ and $y$ are both nonnegative, we can take square roots of both sides to get

Again, because both $x$ and $y$ are nonnegative, we can also remove the absolute-value signs on the sum $x+y$ , which gives us

which is what we wanted to prove.

Much better! This proof doesn’t have logical flaws, it’s easier to read, and we’ve justified all of our steps so that even a skeptical reader would believe us.

Direct Proofs

The proof we just wrote serves as a nice example of the first proof technique we’ll study in this class: the idea of a direct proof. To prove that a given claim is true, the most straightforward path we’ve used in this class has been the following:

• Write down things that you know are true that relate to your claim. This typically includes the definitions of any terms referred to in the definition, any results from class or the tutorials/assignments that look related, and maybe some fundamental facts you know entering this class about numbers.
• Combine those things by using logic or algebra to create more things you know are true.
• Keep doing this until you get to the claim!

A particularly common form of direct proof comes up when people want to prove a statement of the form “if A holds, then B must follow” for two propositions A and B (or equivalently, “A implies B,” which we write in symbols as $A \Rightarrow B$ .)

To write a direct proof of such a statement, we proceed as before, but also throw in the assumption that A holds! That is, to prove “A implies B,” we assume thaat A is true, and try to combine this assumption with other known true things to deduce that B is true. (Logically speaking, this is because $A \Rightarrow B$ holds as long as we’re never in the situation where $A$ is true and $B$ is false. Therefore, if we can show that $A$ being true forces $B$ to also be true, then we know that our claim must hold!)

We illustrate this with a pair of examples here:

Proof. We start by “assuming” the part by the “if:” that is, we assume that $n$ is an odd integer. By definition, this means that we can write $n = 2k+1$ for some other integer $k$ .

We seek to study $n^2$ . By our observation above, this is just $(2k+1)^2 = 4k^2 + 4k+1 = 4(k^2+k)+1$ . This is a multiple of 4 plus 1, as claimed! Therefore we have completed our proof.

Proof. We start this proof by thinking about all of the facts that we know about graphs and degrees. There’s one result that should immediately jump to mind, namely the degree-sum formula: for any graph $G$ ,

Let’s use this result! Specifically: in this problem, we’re studying vertices with odd degree. How can we turn this result into something that talks about odd-degree vertices? Well: from our work in our first chapter, we know that every integer is either even or odd. If we apply this idea to our degree-sum formula, we get the following:

We wanted to study the odd-degree vertices, so let’s get them isolated on one side of our equation:

On the right-hand side, notice that we have an even number (twice the number of edges) minus a bunch of even numbers (the degrees of all even-degree vertices in $G$ ); therefore, the right-hand-side is even!

As a result, the left-hand-side is also even. But this means that the sum of all odd-degree vertices is an even number.

We know that summing an odd number of odd numbers is always odd, and that summing an even number of odd numbers is always even. Because the left-hand side is even, we know we must be in the second case; that is, that we have an even number of vertices of odd degree, as claimed!

Proof by Cases

Our second proof technique is best illustrated by an example:

Theorem 7.2. For every natural number $n$ , if $n$ is a square number, then $n \not\equiv 2 \mod 3$ .

Proof. As always, we start by expanding our definitions. If $n$ is a square number, then by definition we know that $n = k^2$ for some integer $k$ .

From here, we use the particularly clever trick that this section is devoted to: we consider cases. That is: we want to look at what $n$ is congruent to modulo 3.

We don’t have any information about what $n$ or $k$ theirselves are modulo 3, so it would seem hard to introduce this information into our proof! However, by the definition of the modulus operator $\%$ , we know that every number is congruent to one of 0, 1 or 2 modulo 3. By definition, then, this means that we most always be in one of the following three cases:$k \equiv 0 \mod 3$ , $k \equiv 1 \mod 3$ or $k \equiv 2 \mod 3$ .

In each of these cases, we can now expand our definitions and use our knowledge of modular arithmetic to proceed further:

• Assume that we’re in the $k \equiv 0 \mod 3$ case. In this situation, we have that $k = 3m$ for some $m$ , which means that $k^2 = 9m^2 = 3(3m^2)$ is also a multiple of 3. Thus, $k^2 \equiv 0 \mod 3$ .
• Now, assume instead that we’re in the $k \equiv 1 \mod 3$ case. In this situation, we have that $k \equiv 3m + 1$ for some $m$ , which means that $k^2 = 9m^2 + 6m + 1= 3(3m^2 + 2m) + 1$ . Thus, $k^2 \equiv 1 \mod 3$ .
• Finally, consider the last remaining case, where $k \equiv 2 \mod 3$ . In this situation, we have that $k \equiv 3m + 2$ for some $m$ , which means that $k^2 = 9m^2 + 12m + 4= 3(3m^2 + 4m + 1) + 1$ . Thus, $k^2 \equiv 1 \mod 3$ .

In all three of these cases, we’ve seen that $n = k^2$ is not congruent to 2 modulo 3. These cases cover all of the possibilities! Therefore, we know that $n$ is simply never congruent to 2 modulo 3 in any situation, and have therefore proven our claim.

The trick to the proof above was that we were able to introduce additional information about $k$ (namely, its remainder on division by 3) by simply considering all possible remainders as separate cases! This technique, called proof by cases, is a powerful technique in several situations:

• Whenever you’re dealing with integers and answering a question about whether some expression $f(n)$ is even or odd, try considering the two cases ”$n$ is even” and ”$n$ is odd.”
• If you’re dealing with a claim about modular arithmetic, or with claims like “is a multiple of”, considering the different possible remainders that a number could have (i.e. the three cases where $k \% 3 = 0, 1$ or $2$ we considered above) is often a great approach.
• If you’re dealing with claims about rational and irrational numbers, separating the cases ”$x$ is rational” and ”$x$ is irrational” can be handy.

We practice this in the examples below:

Proof. We proceed by considering cases:

• We first consider the case where $x \geq -7$ . In this case, $x+7 \geq 0$ , and so $|x+7| - x$ is just $x+7 - x = 7$ . In this case, our inequality holds!

• Now, we consider the case where $x < -7$ . In this case, $x+7 < 0$ , and so we have $|x+7| = -(x+7)$ (as the negative of a negative is a positive!)

  Therefore, we have $|x+7| - x = -(x+7) - x = -7-2x$ . If $x < -7$ < then $-2x > 14$ , and so $-2x - 7 > 14-7 = 7$ . Therefore our claim holds in this case as well!

Because every number is either greater than or equal to 7 or less than 7, we’ve considered all possible cases. As our claim was true in each possible case, this completes our proof!

_Proof._We consider two possible cases:

• $x > y$ . In this case, we have $\max(x,y) = x$ and $\min(x,y) = y$ ; therefore, $\max(x,y) + \min(x,y) = x+y$ as claimed.
• $x \leq y$ . In this case, we have $\max(x,y) = y$ and $\min(x,y) = x$ ; therefore, $\max(x,y) + \min(x,y) = y+x = x+y$ , also as claimed.

This covers all possible cases, as for any two numbers $x,y$ either $x > y$ or $x \leq y$ ! Therefore, we’ve proven our claim.

In the next example, we return to the tricks we used to calculate the last digit of a number in Claim 1.10:

Proof. We saw before in our chapter on integers that if $d_0$ is the last digit of an integer $n$ , then $n^m \% 10$ is equal to $d_0^m \% 10$ for any positive integer power $m$ .

Therefore, in our claim, we don’t have to actually consider every possible integer $k$ ; we can just consider the ten different possible last digits $k$ could have, and calculate the cubes of each of those! We do so here:

• $0^4 \% 10 = 0 \% 10 = 0$ .
• $1^4 \% 10 = 1 \% 10 = 1$ .
• $2^4 \% 10 = 16 \% 10 = 6$ .
• $3^4 \% 10 = 81 \% 10 = 1$ .
• $4^4 \% 10 = 256 \% 10 = 6$ .
• $5^4 \% 10 = 625 \% 10 = 5$ .
• $9^4 \% 10 = (81)^2 \% 10 = 1^2 \% 10 = 1$ .
• $6^4 \% 10 = (36)^2 \% 10 = 6^2 \% 10 = 6$ .
• $7^4 \% 10 = (49)^2 \% 10 = 9^2 \% 10 = 6$ .
• $8^4 \% 10 = (64)^2 \% 10 = 4^2 \% 10 = 6$ .

In all ten cases, our remainders are always 0, 1, 5, or 6, as claimed! Therefore, we’ve proven our claim.

Finally, we can use a proof by cases to prove one of our exercises:

Answer to Exercise 7.1. Even though there are lots of socks in the drawer, there are only 3 colours. Therefore, we can just take 4 socks to make sure that at least 2 of them are the same colour. To understand why, let’s look at the colours of three first socks.

There are two possible cases here:

• If we were lucky enough to pick two matched socks from those first three, then we’ve succeeded!
• However, in the worst-case scenario the first three socks we took were all different colours, and we do not yet have a pair. In this situation, we have one sock of each colour.

In this case, however, our fourth sock is guaranteed to match at one of our three previously chosen socks!

In any case, we’ve grabbed a pair of socks, as desired.

Proof by Contradiction

Contradiction - i.e. the “if we’re stuck on a problem, suppose we’re wrong and see what happens” proof technique --- is a method we’ve already used to considerable success throughout this coursebook! In this section, we study several more examples of proof by contradiction, and talk a bit about the trickier aspects of this proof method.

To start, let’s examine one of the most famous proofs by contradiction! In this proof, we’re going to really pick apart the structure of a proof by contradiction, so that we can see why this method works:

Proof. As always, let’s start by unpacking our definitions:

• $\sqrt{2}$ is the unique positive real number such that when we square it, we get 2.
• A number $x$ is rational if we can write $x = \frac{m}{n}$ , where $m$ and $n$ are integers and $n$ is nonzero.

With this done, our claim can be unpacked to the following:

“For a real number $x$ , if $x = \sqrt{2}$ , then there are no values of $m, n \in \mathbb{Z}$ with $n \neq 0$ such that $x = \frac{m}{n}$ .”

So: how do we do this? Because the problem wants us to show that we cannot write $\sqrt{2} = \frac{m}{n}$ for any integers $m, n$ with $n \neq 0$ , we can’t just check a few examples: we’d have to look at all of them, and this could be quite difficult! We’d have to find some useful property that makes all examples of this form fail, and this could be quite hard to find.

Instead, consider the following way to “side-step” these difficulties. Instead of looking at all pairs $m, n$ and trying to show that each one fails, let’s assume that we have one such pair $m, n$ such that $\sqrt{2} = \frac{m}{n}$ !

With this assumption in hand, let’s now show that this assumption “breaks mathematics” in some way: that starting from this assumption, we can get to something we know is impossible, like $1+1=0$ . If we can do this, then we know that our original assumption that there was such a fraction $\frac{m}{n}$ must have been nonsense (i.e. false), and therefore that our claim that no such fraction exists is true!

We do this here. Suppose that we can find two integers $m, n$ with $n \neq 0$ such that $\sqrt{2} = \frac{m}{n}$ . If $m$ and $n$ have common factors, divide through by those factors to write $\frac{m}{n}$ in its simplest possible form: that is, don’t write something like $\frac{3}{6}$ or $\frac{12}{24}$ , write $\frac{1}{2}$

Then if we square both sides, we get $2 = \frac{m^2}{n^2}$ . Multiplying both sides by $n^2$ gives us $2n^2 = m^2$ , which means that $m^2$ is even (because it is a multiple of 2)!

This means that $m$ is even (see the tutorials from earlier in this course!), and therefore that we can write $m = 2k$ for some integer $k$ . If we plug this into our equation $2n^2 = m^2$ , we get $2n^2 = (2k)^2 = 4k^2$ , and by dividing by $2$ we have $n^2 = 2k^2$ .

This means that $n^2$ is even, and therefore that $n$ is even as well (same logic as before.)

But this means that both $n$ and $m$ are multiples of 2; that is, that they have a common factor! We said earlier that we’d divided through by any common factors to get rid of them, so this is a contradiction: from our initial assumption we got to something that is both true and false. As a result, our original assumption (that we could write $\sqrt{2} = \frac{m}{n}$ ) must be false; that is, we have shown that $\sqrt{2} \neq \frac{m}{n}$ for any integers $m, n$ with $n \neq 0$ , as desired. Yay!

We can generalize the form of the argument we just made above as follows:

• We have a claim we’re trying to prove; let’s denote it $P$ , for shorthand.
• Instead of proving $P$ is true directly, we want to prove that “not $P$ ” is impossible.
• To do this, we can simply do the following:

  1. Assume, for the moment, that “not-$P$ ” is actually true!

  2. Working from this assumption, find a pair of contradictory statements that are implied by “not $P$ .” That is, find a pair of statements $Q$ and “not-$Q$ ” such that if $P$ was false, both $Q$ and “not-$Q$ ” would both hold. Common examples are “1=1” and “1=0”, or ”$n$ is even” and ”$n$ is false”, or ”$x$ is positive” and ”$x$ is negative”: stuff like that.

  3. This proof demonstrates that “not-$P$ ” must be impossible, because it implies two contradictory things (like the two simultaneous claims ”$n$ is even”and ”$n$ is odd.“) Mathematics is free from false statements and contradictions; therefore, we know that this must be impossible. In other words, “not-$P$ ” must be false and $P$ must be true!

This is how a proof by contradiction works. You take your claim $P$ , assume it’s false, and use “not $P$ ” to deduce contradictory statements, which you know mathematics cannot contain.

We consider another example here:

Proof. In the example we’re studying here, we want to show that it’s impossible for $a^b$ to be irrational for every pair of irrational numbers $a,b$ . To do this via a proof by contradiction, we do the following: first, assume that $a^b$ is irrational for every pair of irrational numbers $a,b$ ! If we apply this knowledge to one of the few numbers ($\sqrt{2}$ ) we know is irrational, our assumption tells us that in specific

What do we do from here? Well: pretty much the only thing we have is our assumption, our knowledge that $\sqrt{2}$ is irrational, and our new belief that $\sqrt{2}^{\sqrt{2}}$ is also irrational. The only thing really left to do, then, is to let $a = \sqrt{2}^{\sqrt{2}}$ , $b = \sqrt{2}$ , and apply our hypothesis again. But this is excellent! On one hand, our we have that $a^b$ is irrational by our hypothesis. On the other hand, we have that $a^b$ is

which is clearly rational. This is a contradiction! Therefore, we know that our hypothesis must be false: there must be a pair of irrational numbers $a,b$ such that $a^b$ is rational.

An interesting quirk of the above proof is that it didn’t actually give us a pair of irrational numbers $a,b$ such that $a^b$ is rational! It simply told us that either

• $\sqrt{2}^{\sqrt{2}}$ is rational, in which case $a=b=\sqrt{2}$ is an example, or
• $\sqrt{2}^{\sqrt{2}}$ irrational, in which case $a = \sqrt{2}^{\sqrt{2}}, b = \sqrt{2}$ is an example,

but it never actually tells us which pair satisfies our claim! This is a weird property of proofs by contradiction: they are often nonconstructive proofs, in that they will tell you that a statement is true or false without necessarily giving you an example that demonstrates the truth of that statement.

To stick with the classical route, let’s study another one of the first proofs by induction, that we considered all the way back in our first chapter:

Proof. As we did with our argument that no number can be both even and odd at the same time, let’s approach this with a bit of a thought experiment: what would happen if there were not infinitely many prime numbers?

Well: if this were to happen, then there would be some fixed number of primes in existence. Let’s give that number a name, and say that there were $n$ primes in existence. Then, if we had a piece of paper with $n$ lines on it, we could in theory write down all of the prime numbers that existed!

If we labeled those lines $1,2,\ldots n$ , we could then refer to those prime numbers by their labels: that is, we could refer to our prime numbers by calling them $p_1, p_2, p_3, \ldots p_n$ . (Giving things names: a very useful technique!)

In this world where we have all of these prime numbers, what can we do with them? Well: as we saw before, a particularly useful property about prime numbers is that they form the building blocks out of which we can make all integers. Therefore, we’re motivated to take our primes and stick them together, and see what happens!

After a lot of effort, you might eventually hit on the clever combination of our prime numbers that Euclid discovered: think about what happens if we multiply all of our prime numbers together, and then add 1 to that entire sum. That is: look at the number

On one hand: take any of the prime numbers on our list. To indicate that we’re taking a general prime number from our list, let’s refer to that prime number as $p_i$ , where $i$ could be any index. Look at $\frac{M}{p_i}$ . By definition, this is equal to

In particular, notice that this is not an integer! $\frac{1}{p_i}$ is some fraction strictly between 0 and 1, because $p_i$ is a prime and therefore at least 2, while the right-hand-bit is a product of integers and therefore is an integer itself.

Therefore, we’ve shown that if we multiply $p_i$ by a number to get $M$ , that number cannot be an integer; in other words, we have shown that $p_i$ is not a factor of $M$ . This holds for any of our primes, because $p_i$ was an arbitrary prime; therefore $M$ is not a multiple of any of our prime numbers!

On the other hand, though, we know that $M$ is an integer. Therefore, we know that we can factor $M$ into prime numbers! Do so, and write $M$ as a product of prime numbers.

Our argument above tells us that that none of those prime numbers can be from our list $p_1, \ldots p_n$ . But this list was supposed to contain all of the prime numbers! Therefore, we know that our original assumption that we could write down all of the prime numbers must have been false: that is, there must have been infinitely many prime numbers.

Common Contradiction Mistakes: Not Understanding Negation

In a proof by contradiction, we’re trying to prove that a claim $P$ is true by showing that “not-$P$ ” cannot be false. Perhaps surprisingly, the most common mistake people make when using a proof by contradiction is in their very first step: specifically, in writing just what “not-$P$ ” is for a given claim!

For example, consider the following claim:

Here are a number of incorrect ways that people will try to negate this claim:

• “For every pair of integers $x,y$ such that $x,y$ are both even, we have that $x \cdot y$ is also even.”

  The first mistake made here is in the first two words, where we wrote “for every!” That is: Claim 7.10 is a claim about all pairs of integers. As such, if someone were to say that $P$ was false, they’d just have to have one counterexample to prove us wrong!

  That is: if someone made a claim that every UoA student was enrolled in Compsci 120, you wouldn’t prove them wrong by trying to show that every UoA student is not enrolled in Compsci 120; you’d just have to find at least one student not in Compsci 120.

  This tells us the first part of how we should write the negation of this claim: it should go “There is a pair of integers $x,y$ …”

• This, however, is not enough! That is: “There is a pair of integers $x,y$ such that $x,y$ are both even and $x \cdot y$ is also even” is also not the negation of our claim.

  To see why this fails, note that Claim 7.10 is a claim about all pairs of odd integers. As such, if we’re trying to say that this claim fails, we still need to work in the same universe as our normal claim, and we need to find a counterexample that consists of a pair of odd integers.

  That is: if someone told you “every Compsci 120 student who’s never been to Antartica currently has an A,” you don’t disprove them by trying to find a student who’s been to Antarctica! Their claim was about people who haven’t been to Antarctica; to disprove it, you need to work within the same bounds!

As such, the correct negation of Claim 7.10, is the following:

Much more reasonable!

Using similar logic, the clam

should negate to the following:

This is because the opposite of a claim about something existing is that there are no counterexamples (i.e. a claim about everything). As well, the universe of numbers we’re studying (primes) should remain the same, leaving only the conclusion (even) to flip to “odd.”

Let’s consider another claim:

There are many tempting and incorrect ways to negate this claim:

• If $G$ is a claim containing $<2$ vertices, then $G$ does not contain 2 vertices whose degrees are different.” This is the same “negating the universe” error from before!

  That is: our claim is about graphs on 2 or more vertices. Its negation should still talk about graphs on 2 or more vertices! As well, our claim was about vertices whose degrees agreed. Its negation should still talk about vertices with equal degree!

• This suggests the following as a fix: “If $G$ is a graph containing $\geq 2$ vertices, then $G$ does not contains two vertices whose degrees are equal.”

  This has the right universe, but it fails for a second, more subtle reason: the opposite of “if $A$ then $B$ ” is not “if $A$ then not-$B$ .”

  That is: suppose that someone claimed to you “if you attend tutorials in Compsci 120, you’ll pass the class.” The above strategy would say that you could disprove their claim by saying “if you attend tutorials in Compsci 120, then you won’t pass the class.”

  This doesn’t really make sense, though! Their claim here is a really strong guarantee: it says that everyone who attends tutorials in Compsci 120 will pass. To disprove this, you don’t need to show that everyone who attends tutorials won’t pass; that’s way too hard! Instead, you’d just need to find at least one person who (1) attended all of the tutorials but (2) didn’t pass the class.

  That is: the opposite of “if $A$ then $B$ ” is “there is a situation where $A$ holds and $B$ fails.”

By using this, the correct negation of Claim 7.12,. is the following:

We can summarise the observations we made above as follows:

To finish this section and put this to use, let’s prove Claim 7.12!

Proof of Claim 7.12,. As noted above, the contradictive assumption here would be that $G$ is a graph on $n\geq 2$ vertices in which all of the vertices have different degrees.

We know that the maximum degree of any vertex in $G$ is $n-1$ , because any vertex is at most adjacent to every other vertex. As well, the minimum degree of any vertex is trivially 0. Therefore, there are in theory $n$ different possible degrees for the $n$ vertices in $G$ , namely the values $0,1,\ldots n-1$ .

If no degrees are repeated in $G$ , then (because there are $n$ vertices and $n$ different possible degrees) there is exactly one vertex with degree $i$ , for every $i \in \{0,1,\ldots n-1\}$ . If $n \geq 2$ , note that in particular $n-1 \geq 1$ , and so the degree-0 and degree-$(n-1)$ vertices are different.

Now, notice that if there is a vertex with degree $n-1$ , it is connected to every other vertex in our graph. In particular it must be connected to the vertex that has degree 0, which contradicts the property that this vertex is supposed to have degree 0.

Therefore we have a contradiction, and can conclude that our original claim must hold.

Proof by Construction

In many of the proofs above, we’ve been focused on proving claims about “all” numbers $x,y$ , or “all” odd integers $n$ , or other sorts of “universal” claims about things. When we’re proving claims of these forms, we need to use techniques and arguments like the ones above where we work in general / don’t get to use examples to prove our claim!

Sometimes, however, we’ll find ourselves with claims of the form “There exists a number $n$ such that…” or “There is a value $x$ with the property…” In this sort of situation, we’re not being asked to show that something is true for all values: instead, we’re just asked to find a single example!

In situations like this, a common technique is proof by construction, where we simply create an object with the desired properties. We illustrate this with an example:

Proof. Notice that $2^0 = 1$ . Therefore, $1$ is a power of 2. 1 is also odd, as we can write it in the form $1+2k$ for some integer $k$ (specifically, $k=0$ .) Therefore we’ve constructed the claimed integer, as desired.

Notice the following two aspects of this proof:

• We didn’t have to work with a general integer $n$ ; instead, we got to give a specific example! This is because our claim was of the form “There is …”, which means that we’re just asked for a single example. If our proof had started “For all …”, this would be different, and this proof would be invalid (just like how examples weren’t enough for a proof in our earlier “the sum of any two odd numbers is even” claim.)
• Also notice that we didn’t just say “1 is the answer” and ended our proof; we actually took the time to explain why 1 has the desired properties. You should expect to always do this!

We give a second example, to illustrate how these sorts of things come up in combinatorics and/or “puzzle” mathematics:

Proof. Behold!

In this proof, we don’t have much to really explain: the solution presented self-evidently has the desired property (just check every row and column.) If it was unclear, though, we’d have to have some explanation along with our answer!

We close by giving a pair of slightly trickier examples for how construction can work, by using processes and algorithms:

Proof. Consider the following algorithm to paint any connected graph $G$ ’s vertices with the colors red and blue:

Algorithm 7.13. Init: Choose any vertex $v$ in $G$ , and paint it red.

1. Take all currently uncolored vertices that are connected to any red vertices by an edge, and color them blue.
2. Take all currently uncolored vertices that are connected to any blue vertices by an edge, and color them red.
3. If there are any uncolored vertices left, go back to (i) and repeat.

We claim that this algorithm will always succeed at coming up with a valid vertex coloring of any tree $G$ ; indeed, more generally, we claim that this algorithm will always succeed at making a valid 2-coloring of any graph $G$ that doesn’t contain an odd-length circuit as a subgraph! Because any tree does not have an odd-length circuit as a subgraph (indeed, it doesn’t contain a cycle subgraph of any length), this would prove our claim.

To see why, we use a second proof technique: contradiction! Think about what would happen if this algorithm would fail, given a connected graph $G$ with no odd-length circuit subgraphs.

Because $G$ is connected, the above process will eventually color every vertex of $G$ ; we first color $v$ , then its neighbors, then its neighbor’s neighbors, and so on/so forth, coloring every vertex within a walk of $k$ edges by the $k$ -th pass. So if the algorithm fails, it does so because in its coloring there must be an edge $\{x,y\}$ in which $x, y$ both get the same color.

Notice that if a vertex $w$ is colored blue, it is because we can walk to to $w$ from our starting $v$ in either one step, or three steps, or five steps … or in general an odd number of steps. This is because we alternated between red and blue in our algorithm. Similarly, if a vertex $w$ is colored red, it is because we can walk to $w$ in either 0 or 2 or 4 or 6 or … or an even number of edges.

Take any walk $P_x$ from $v$ to $x$ , and any other walk $P_y$ from $v$ to $y$ . We have proven that either $P_x, P_y$ both have an even number of edges, or that they both have an odd number of edges. Therefore, the circuit formed by starting at $v$ , walking along $P_x$ to $x$ , using the $\{x,y\}$ edge to go to $y$ , and then reversing $P_y$ to return to $v$ has either $(\textrm{even} + 1 + \textrm{even})$ or $(\textrm{odd} + 1 + \textrm{odd})$ length. Both of the quantities, in particular, are odd! This contradicts our assumption that $G$ had no odd-length circuits.

As a result, our original claim (that $G$ is bipartite) must be true!

Claim 7.16.Link copied A Hamiltonian circuit in a graph $G$ is a walk that starts and ends at the same vertex, and along the way visits every other vertex exactly once. For example, the cube graph $Q_3$ below has a Hamiltonian circuit (highlighted.) The $n \times n$ grid graphs are defined by drawing a $n \times n$ grid of vertices and connecting adjacent vertices, as drawn below: Prove for all $n \in \mathbb{N}$ that $G_{2n, 2n}$ has a Hamiltonian circuit.

Proof. Consider the following constructive process for generating such a circuit:

• Label the $(2n)^2$ vertices in the grid graph $G_{2n, 2n}$ with coordinates $(i,j)$ , where vertex $(1,1)$ is the vertex in the bottom-left-hand corner and $(2n,2n)$ is the vertex in the upper-right-hand corner.
• Start at $(1,1)$ ,
• From this vertex, walk to the right until you’re at the bottom-right corner $(1,2n)$ .
• Go up one step to $(2,2n)$ , and then walk back to the left until you’re at $(2,2)$ .
• Go up one step to $(3,2)$ , then walk back to the right until you’re at $(3,2n)$ .
• Go up one step to $(4,2n)$ , and then walk back to the left until you’re at $(4,2)$ .
• Go up one step to $(5,2)$ , then walk back to the right until you’re at $(5,2n)$ .
• … Keep doing this! Eventually, you will find yourself at $(2n,2)$ , having walked on all of the vertices whose second coordinates are not equal to 1, and not having visited any vertices whose second coordinate is 1 other than (1,1). (This is where the ”$2n$ ” part comes in: because we go right on odd rows and left on even rows, if our grid has even height then we’ll be going left on our top row and thus wind up at $(2n,2)$ as claimed.)
• Walk from $(2n,2)$ to $(2n,1)$ , and then go down to $(1,1)$ .

By construction we have visited all vertices in our graph exactly once, and thus created a Hamiltonian circuit, as desired.

Finally, we can answer one our earlier exercises by using construction:

Answer to Exercise 7.2. This has a nice constructive answer: take half of each of the four tablets today, and the other half tomorrow.

Because this is constructive, we don’t have to explain how we came up with this clever idea: we can just present it as an answer! (Though if you did something clever to come up with an idea, it is good to mention how you did this.) We just have to explain why this works, which is pretty simple: half of each tablet gives us half of the tablets of each type, and thus exactly one dose for each kind.

Proof by Induction: First Examples

Sometimes, in mathematics, we will want to study a statement $P(n)$ that depends on some variable $n$ . For example:

• $P(n) =$ “The sum of the first $n$ natural numbers is $\frac{n(n+1)}{2}$ .”
• $P(n) =$ “If $q \geq 2$ , we have $n \leq q^n$ .
• $P(n) =$ “Every polynomial of degree $n$ has at most $n$ roots.”
• $P(n) =$ Take a $2^n \times 2^n$ grid of unit squares, and remove one square from the top-right-hand corner of your grid. The resulting shape can be tiled by - shapes.

For any fixed $n$ , we can usually use our earlier proof methods to prove that the claim holds! For instance, let $P(n)$ be the fourth example above, and consider $P(3)$ , which is the claim that if we take a $8 \times 8$ grid of squares and delete the top-right-hand corner square, we can tile the rest of the shape with tiles. We can prove this by construction by just giving an explicit way to do it: see the drawing below!

However, sometimes we will want to prove that one of these statements holds for every value $n \in \mathbb{N}$ . How can we do this?

The answer here is mathematical induction! Mathematical induction is just a formal way of writing up our “building-block plus preserved property” process, in a way that will hopefully let us avoid everyone having the same shoe size. We describe it here:

• To start, take a claim $P(n)$ that we want to prove holds for every $n \in \mathbb{N}$ .

• The first step in an inductive proof is the base step: in this step, we explicitly prove that the statement $P$ holds for a few small cases using normal proof methods (typically construction or just calculation.)

  Usually you just prove that your claim holds when $n=0$ , but sometimes you start with $n=1$ if your claim is one where 0 is a “dumb” case, or prove a handful of cases like $n=0,1,2,3$ to get the hang of things before moving on. You can think of this as the “building block” step from before!

• With this done, we move to the induction step! Here, we prove the following statement:

Because this is an implication, i.e. an if-then proof, we usually prove it directly by assuming that our claim holds for all values up to some $n$ , and then use this assumption to prove that our claim holds when we have $n+1$ in our claim.

Just doing these two steps shows that your claim $P$ is true for every natural number $n$ ! To see why, just examine what these two steps tell you:

• By our “base case” reasoning, we know that our claim is true at n=0.
• By our “inductive step” reasoning, we know that if our claim is true at 0, it is true at the “next” value $n+1 = 1$ .
• By our “inductive step” reasoning, we know that if our claim is true up to 1, it is true at the “next” value $2$ .
• By our “inductive step” reasoning, we know that if our claim is true up to 2, it is true at the “next” value $3$ .
• …
• By continuing this process, we eventually get to any $n$ ! Therefore our claim is true for every $n \in \mathbb{N}$ , as desired.

The way we usually think of inductive proofs is to think of topping dominoes. Specifically, think of each of your $P(n)$ propositions as individual dominoes - one labeled $P(0)$ , one labeled $P(1)$ , one labeled $P(2)$ , and so on/so forth. With our inductive step, we are insuring that all of our dominoes are lined up - in other words, that if we’ve knocked over some of them, the “next one” will also be knocked over. Then, we can think of the base step as “knocking over” the first domino. Once we do that, the inductive step makes it so that all of the later dominoes also have to fall, and therefore that our proposition must be true for all $n$ (because all the dominoes fell!)

To illustrate how these kinds of proofs go, let’s go back to our tiling problem, and prove that we can tile this grids for every $n \in \mathbb{N}$ ! (As an added bonus, let’s prove it for grids where we remove one square from anywhere, not just the top-right-hand corner!)

Claim 7.17.Link copied For any $n \in \mathbb{N}$ , take a $2^n \times 2^n$ grid of unit squares, and remove one square from somewhere in your grid. The resulting grid can be tiled by - shapes.

Proof. As suggested by the section title, we proceed by induction, where our proposition $P(n)$ is “we can tile a $2^n \times 2^n$ grid of $1 \times 1$ squares with one square deleted by using - shapes.”

Base case: we want to prove $P(0)$ . So: what is $P(0)$ ?

Well: for $n=0$ , we have a $2^0 \times 2^0 = 1 \times 1$ grid, which we’ve removed a $1 \times 1$ square from. In other words, we have nothing. If you want, you can think of “nothing” as being something we can trivially cover by placing no three-square shapes!

Alternately, you can decide that 0 is a stupid case and look at $n=1$ instead. For $n = 1$ , we simply have a $2 \times 2$ grid with one square punched out. As this is one of our three-square shapes, we are done here; just place a tile on top of our grid!

Either starting place is fine. In general, we recommend doing as many base cases as you need to do in order to feel comfortable with the pattern and believe that you’ve done something concrete! Most of the time, though, the base case will feel kinda silly; don’t worry about this! The inductive step will do all of the heavy lifting for us.

Inductive step: We want to prove that if we know that our claim holds up to $n$ , then it holds for $n+1$ as well; formally, this means that we want to show that if $P(0)$ and $P(1)$ and … and $P(n)$ all hold, then $P(n+1)$ must follow.

In this problem in particular, this means that we’re assuming that we can tile a $2^{k} \times 2^{k}$ -grid with a square deleted for any $k \leq n$ , and want to use this assumption to tile a $2^{n+1} \times 2^{n+1}$ grid with a square deleted.

To do this, take any $2^{n+1} \times 2^{n+1}$ grid with a square deleted. Divide it into four $2^n \times 2^n$ squares by cutting it in half horizontally and vertically. Finally, by rotating our grid if needed, make it so that the one missing square is in the upper-right hand corner.

Take this grid, and carefully cut out one three-square shape in the center as drawn below.

Now, look at each of the four $2^n \times 2^n$ squares in this picture. They all are missing exactly one square: the upper-right hand one because of our original setup, and the other three because of our placed three-square-shape.

By our inductive hypothesis $P(n)$ we know that all of these smaller squares can be tiled! Doing so then gives us a tiling of the whole shape; in other words, we’ve shown how to use our $P(n)$ results to get a tiling of the $2^{n+1} \times 2^{n+1}$ grid.

As this completes our inductive step, we are thus done with our proof by induction.

The claim we proved above - one where we were some sense “growing” or “extending” a result on small values of $n$ to get to larger values of $n$ - is precisely the kind of question that induction is set up to solve! The Fibonacci numbers, which we introduce in the next question, is another object where this sort of “extension” approach is useful to consider.

To illustrate how it works, let’s use it to calculate the first few values of the Fibonacci sequence! We know that $f_0 = 0, f_1 = 1$ by definition.

To find $f_2$ , we can use the fact that for any $n \geq 2$ , $f_n = f_{n-2} + f_{n-1}$ to calculate that.

We can calculate further values of $f_n$ similarly:

• $f_3 = f_1 + f_2 = 1+1 = 2,$
• $f_4 = f_2 + f_3 = 1+2 = 3,$
• $f_5 = f_3 + f_4 = 2+3 = 5,$
• $f_6 = f_4 + f_5 = 3+5 = 8,$
• $f_7 = f_5 + f_6 = 5+8 = 13,$
• $f_8 = f_6 + f_7 = 8+13 = 21,$
• $f_9 = f_7 + f_8 = 13+21 = 34,$
• $f_{10} = f_8 + f_9 = 21+34 = 55,$
• $f_{11} = f_9 + f_{10} = 34+55 = 89,$
• $f_{12} = f_{10} + f_{11} = 55+89 = 144,$

When doing this, you’ll likely notice a number of interesting properties about the Fibonacci sequence: see for a ton of weird/beautiful properties these numbers have! We prove one of these properties here:

Proof. Let $P(n)$ denote the claim “(the $n$ -th Fibonacci number is even) $\Leftrightarrow$ ($n$ is a multiple of 3).” We want to prove that $P(n)$ holds for all $n \in \mathbb{N}$ , and proceed to prove this claim by induction.

Our base cases are pretty easy to check! We calculated the Fibonacci numbers from $f_0$ to $f_{12}$ above, and we can see that the only ones that are even are $f_0, f_3, f_6, f_9$ and $f_{12}$ ; so we know that $P(0), P(3), P(6), P(9),$ and $P(12)$ all hold.

We now move to the inductive step: here, we want to prove $P(0)$ and $P(1)$ and $P(2)$ and … and $P(n)$ , when all combined together, imply $P(n+1)$ . We start with what we’re assuming, namely that all of $P(0), P(1),\ldots P(n)$ are all true: that is, we’re assuming that the $k$ -th Fibonacci number is even if and only if it is a multiple of 3, for every $k \in \{0,1,\ldots n\}$ .

We want to prove $P(n+1)$ , i.e. that the $n+1$ -th Fibonacci number is even if and only if it is a multiple of 3.

So: let’s consider cases! There are two possible cases for the value $n+1$ : either it is a multiple of 3, or it’s not.

• If $n+1$ is a multiple of 3, we can write $n+1=3k$ for some $k \in \mathbb{Z}$ . Notice that this means that $n = 3k-1$ and $n-1 = 3k-2$ , and in particular that both of the values $n, n-1$ are not multiples of 3! As a result, our inductive assumption tells us that $f_n, f_{n-1}$ are both not even, because they’re not multiples of 3! But being not-even just means that these numbers are both odd. As a result, because $f_{n+1} = f_n + f_{n-1} =$ odd+ odd= even, we have shown that $f_{n+1}$ is even in this case.
• If $n+1$ is not a multiple of 3, then $n+1$ either has remainder 1 or 2 when we divide it by 3; this is because any number has remainder 0, 1 or 2 when divided by 3. This means we can write $n+1 = 3k + 1$ or $3k+2$ , for some $k \in \mathbb{Z}$ . As a result, we can see that of the two numbers $n, n-1$ , exactly one of them is a multiple of 3; if $n+1 = 3k+1$ then $n, n-1 = 3k, 3k-1$ , and if $n+1 = 3k+2$ then $n,n-1 = 3k+1, 3k$ . As a result, our inductive hypothesis tells us that exactly one of $f_n, f_{n-1}$ are odd, and the other is even. Therefore, because $f_{n+1} = f_n + f_{n-1} =$ (one odd number plus one even number)= odd, we have shown that $f_{n+1}$ is odd in this case.

So, by using strong induction, we have proven that $f_n$ is even if and only if it is a multiple of 3!

Induction: Two Recurrence Relations

As we just saw in the section above, induction is a useful tool to study recurrence relations! In this section, we continue with this theme, and use induction to prove Claim 4.2 and Claim 4.6 from our algorithms chapter.

Proof. We proceed by induction. First, we can notice that the table of values we calculated earlier validates our claim for the first few values of $n$ :

This gives us our base case.

For the inductive step, we proceed as always: we assume that our claim holds up to some value $n$ , and seek to prove it for $n+1$ .

In particular, if our claim holds up to some value $n$ , we have $\texttt{SelectionSortSteps}(n) = \dfrac{3n^2+9n-10}{2}.$