From Mathematics to Generic Programming (2015)

Appendix B. Common Proof Techniques

There are a few standard proof techniques that occur frequently in mathematics and computer science, and which we use in this book. If you are having trouble understanding the proofs in the main text, you may want to review this section.

B.1 Proof by Contradiction

Many things we want to prove have the form “if p, then q” (also sometimes written “p q”), where p and q are two propositions. We always start with the premise that p is true; otherwise, we would be solving a different problem. The idea of proof by contradiction is to assume the opposite of what the original conjecture concludes (i.e., assume that q is not true), and then show that this assumption would lead to a logical contradiction—in particular, that proposition p would be false, which we know is not the case. This forces us to conclude that proposition q must be true after all, which is what we really wanted all along.

Let’s look at an example. Suppose we want to prove that for all integers n:

If n² is odd, then n is odd.

Here “n² is odd” is our p and “n is odd” is our q. So let’s assume the opposite conclusion is true, that n is not odd—that n is even. What does it mean for an integer n to be even? It means we can write it as twice some other integer m:

n = 2m

What happens if we square n?

n² = 2 · 2 · m²

Let’s introduce a new variable x, and set x = 2m². Then we can substitute:

n² = 2 · 2m² = 2x

Now we see that n² can be expressed as twice some other integer x. But that’s the definition of even, and our premise was that n² is odd. n² can’t be both even and odd—that’s a logical contradiction. So the assumption we made at the beginning that n is even must be false; n must therefore be odd, and we’ve proved the original result.

B.2 Proof by Induction

Some results we’d like to prove involve infinite sets of things. Obviously in these situations we can’t enumerate all the cases, but we can often use mathematical induction to obtain our result. To prove something by induction, you need to do two things:

• Prove that it’s true for the first element in the set. This is called the basis.

• Prove that if it’s true for an arbitrary element in the set (the induction hypothesis), then it’s also true for the successor of that element. This is called the inductive step.

For example, suppose we want to prove that for any positive integer n:

Basis:

Does the equation hold if n = 1? In other words, is it true that

We can just do the arithmetic, and see that the answer is “yes.”

Inductive step:

Assume that the equation is true for n = k. If that were true, would it also be true for k + 1? This is what it means to be true for k (i.e., this is our induction hypothesis):

Let’s add k + 1 to both sides:

This is just , where n = k+1. So we have proved that if the equation is true for k, it’s true for k + 1.

Since we have shown both the basis and the inductive step, we have proved our original statement.

B.3 The Pigeonhole Principle

The pigeonhole principle (sometimes known as the Dirichlet principle) is very simple: if you have n pigeonholes and more than n pigeons, then at least one pigeonhole must contain more than one pigeon. There are lots of examples of this in real life. For example, if you have 367 people, at least two of them must have the same birthday. But the idea also turns out to be useful in some mathematical proofs. Often when you see a theorem that’s trying to prove that two things will be the same, the pigeonhole principle is a good approach.

Here’s an example:

Prove that any set of 10 positive integers smaller than 100 will always contain two subsets with the same sum.

First, let’s consider how many possible sums we can get. The sum of any 10 positive integers less than 100 can’t be smaller than 10 or larger than 990, so it must be somewhere in the range [10, 990]. That range contains 990 − 10 = 980 values, so that’s the maximum number of possible sums.¹ Next, let’s see how many possible subsets of those 10 integers there are. We can represent each subset as a binary number where the ith bit is 1 if the ith integer in the set is in that subset, and 0 otherwise. There are 10 elements in the set, and we use one bit for each element, so there are 2¹⁰ = 1024 possible subsets. Since there are only 980 possible sums, and there are 1024 possible subsets, by the pigeonhole principle, at least two of the subsets must have the same sum.

¹ Actually, the problem says that we have a set of 10 integers, and a set may not contain repeated elements. So the actual number of possible sums is smaller than 980, but the result of the proof is the same.