Proofs

Section 3.2 Proofs

Investigate!

Decide which of the following are valid proofs of the following statement:

If $a b$ is an even number, then $a$ or $b$ is even.
🔗

Suppose $a$ and $b$ are odd. That is, $a = 2 k + 1$ and $b = 2 m + 1$ for some integers $k$ and $m .$ Then

$\begin{aligned} a b & = (2 k + 1) (2 m + 1) \\ = 4 k m + 2 k + 2 m + 1 \\ = 2 (2 k m + k + m) + 1 . \end{aligned}$

Therefore $a b$ is odd.
Assume that $a$ or $b$ is even - say it is $a$ (the case where $b$ is even will be identical). That is, $a = 2 k$ for some integer $k .$ Then

$\begin{aligned} a b & = (2 k) b \\ = 2 (k b) . \end{aligned}$

Thus $a b$ is even.
Suppose that $a b$ is even but $a$ and $b$ are both odd. Namely, $a b = 2 n,$ $a = 2 k + 1$ and $b = 2 j + 1$ for some integers $n,$ $k,$ and $j .$ Then

$\begin{aligned} 2 n & = (2 k + 1) (2 j + 1) \\ 2 n & = 4 k j + 2 k + 2 j + 1 \\ n & = 2 k j + k + j + \frac{1}{2} . \end{aligned}$

But since $2 k j + k + j$ is an integer, this says that the integer $n$ is equal to a non-integer, which is impossible.
Let $a b$ be an even number, say $a b = 2 n,$ and $a$ be an odd number, say $a = 2 k + 1 .$

$\begin{aligned} a b & = (2 k + 1) b \\ 2 n & = 2 k b + b \\ 2 n - 2 k b & = b \\ 2 (n - k b) & = b . \end{aligned}$

Therefore $b$ must be even.

Anyone who doesn’t believe there is creativity in mathematics clearly has not tried to write proofs. Finding a way to convince the world that a particular statement is necessarily true is a mighty undertaking and can often be quite challenging. There is not a guaranteed path to success in the search for proofs. For example, in the summer of 1742, a German mathematician by the name of Christian Goldbach wondered whether every even integer greater than 2 could be written as the sum of two primes. Centuries later, we still don’t have a proof of this apparent fact (computers have checked that “Goldbach’s Conjecture” holds for all numbers less than

4 \times 10^{18},

which leaves only infinitely many more numbers to check).

🔗

Writing proofs is a bit of an art. Like any art, to be truly great at it, you need some sort of inspiration, as well as some foundational technique. Just as musicians can learn proper fingering, and painters can learn the proper way to hold a brush, we can look at the proper way to construct arguments. A good place to start might be to study a classic.

🔗

Theorem 3.2.1.

There are infinitely many primes.

🔗

Proof.

Suppose this were not the case. That is, suppose there are only finitely many primes. Then there must be a last, largest prime, call it

p .

Consider the number

🔗

N = p! + 1 = (p \cdot (p - 1) \cdot \dots 3 \cdot 2 \cdot 1) + 1 .

🔗

Now

N

is certainly larger than

p .

Also,

N

is not divisible by any number less than or equal to

p,

since every number less than or equal to

p

divides

p! .

Thus the prime factorization of

N

contains prime numbers (possibly just

N

itself) all greater than

p .

p

is not the largest prime, a contradiction. Therefore there are infinitely many primes.

🔗

This proof is an example of a proof by contradiction, one of the standard styles of mathematical proof. First and foremost, the proof is an argument. It contains sequence of statements, the last being the conclusion which follows from the previous statements. The argument is valid so the conclusion must be true if the premises are true. Let’s go through the proof line by line.

🔗

Suppose there are only finitely many primes. [this is a premise. Note the use of “suppose.”]
There must be a largest prime, call it $p .$ [follows from line 1, by the definition of “finitely many.”]
Let $N = p! + 1 .$ [basically just notation, although this is the inspired part of the proof; looking at $p! + 1$ is the key insight.]
$N$ is larger than $p .$ [by the definition of $p!$ ]
$N$ is not divisible by any number less than or equal to $p .$ [by definition, $p!$ is divisible by each number less than or equal to $p,$ so $p! + 1$ is not.]
The prime factorization of $N$ contains prime numbers greater than $p .$ [since $N$ is divisible by each prime number in the prime factorization of $N,$ and by line 5.]
Therefore $p$ is not the largest prime. [by line 6, $N$ is divisible by a prime larger than $p .$ ]
This is a contradiction. [from line 2 and line 7: the largest prime is $p$ and there is a prime larger than $p .$ ]
Therefore there are infinitely many primes. [from line 1 and line 8: our only premise lead to a contradiction, so the premise is false.]

🔗

We should say a bit more about the last line. Up through line 8, we have a valid argument with the premise “there are only finitely many primes” and the conclusion “there is a prime larger than the largest prime.” This is a valid argument as each line follows from previous lines. So if the premises are true, then the conclusion must be true. However, the conclusion is NOT true. The only way out: the premise must be false.

🔗

The sort of line-by-line analysis we did above is a great way to really understand what is going on. Whenever you come across a proof in a textbook, you really should make sure you understand what each line is saying and why it is true. Additionally, it is equally important to understand the overall structure of the proof. This is where using tools from logic is helpful. Luckily there are a relatively small number of standard proof styles that keep showing up again and again. Being familiar with these can help understand proof, as well as give ideas of how to write your own.

🔗

Subsection Direct Proof

The simplest (from a logic perspective) style of proof is a direct proof. Often all that is required to prove something is a systematic explanation of what everything means. Direct proofs are especially useful when proving implications. The general format to prove

P \to Q

is this:

🔗

Assume $P .$ Explain, explain, …, explain. Therefore $Q .$
🔗

Often we want to prove universal statements, perhaps of the form

\forall x (P (x) \to Q (x)) .

Again, we will want to assume

P (x)

is true and deduce

Q (x) .

But what about the

x ?

We want this to work for all

x .

We accomplish this by fixing

x

to be an arbitrary element (of the sort we are interested in).

🔗

Here are a few examples. First, we will set up the proof structure for a direct proof, then fill in the details.

🔗

Example 3.2.2.

Prove: For all integers

n,

n

is even, then

n^{2}

is even.

🔗

Solution.

The format of the proof will be this: Let

n

be an arbitrary integer. Assume that

n

is even. Explain explain explain. Therefore

n^{2}

is even.

To fill in the details, we will basically just explain what it means for

n

to be even, and then see what that means for

n^{2} .

Here is a complete proof.

Proof.

Let

n

be an arbitrary integer. Suppose

n

is even. Then

n = 2 k

for some integer

k .

Now

n^{2} = (2 k)^{2} = 4 k^{2} = 2 (2 k^{2}) .

Since

2 k^{2}

is an integer,

n^{2}

is even.

🔗

Example 3.2.3.

Prove: For all integers

a,

b,

and

c,

a | b

and

b | c

then

a | c .

(Here

x | y,

read “

x

divides

y

” means that

y

is a multiple of

x,

i.e., that

x

will divide into

y

without remainder).

🔗

Solution.

Even before we know what the divides symbol means, we can set up a direct proof for this statement. It will go something like this: Let

a,

b,

and

c

be arbitrary integers. Assume that

a | b

and

b | c .

Dot dot dot. Therefore

a | c .

How do we connect the dots? We say what our hypothesis (

a | b

and

b | c

) really means and why this gives us what the conclusion (

a | c

) really means. Another way to say that

a | b

is to say that

b = k a

for some integer

k

(that is, that

b

is a multiple of

a

). What are we going for? That

c = l a,

for some integer

l

(because we want

c

to be a multiple of

a

). Here is the complete proof.

Proof.

Let

a,

b,

and

c

be integers. Assume that

a | b

and

b | c .

In other words,

b

is a multiple of

a

and

c

is a multiple of

b .

So there are integers

k

and

j

such that

b = k a

and

c = j b .

Combining these (through substitution) we get that

c = j k a .

But

j k

is an integer, so this says that

c

is a multiple of

a .

Therefore

a | c .

🔗

Subsection Proof by Contrapositive

Recall that an implication

P \to Q

is logically equivalent to its contrapositive

\neg Q \to \neg P .

There are plenty of examples of statements which are hard to prove directly, but whose contrapositive can easily be proved directly. This is all that proof by contrapositive does. It gives a direct proof of the contrapositive of the implication. This is enough because the contrapositive is logically equivalent to the original implication.

🔗

The skeleton of the proof of

P \to Q

by contrapositive will always look roughly like this:

🔗

Assume $\neg Q .$ Explain, explain, … explain. Therefore $\neg P .$
🔗

As before, if there are variables and quantifiers, we set them to be arbitrary elements of our domain. Here are two examples:

🔗

Example 3.2.4.

Is the statement “for all integers

n,

n^{2}

is even, then

n

is even” true?

🔗

Solution.

This is the converse of the statement we proved above using a direct proof. From trying a few examples, this statement definitely appears to be true. So let’s prove it.

A direct proof of this statement would require fixing an arbitrary

n

and assuming that

n^{2}

is even. But it is not at all clear how this would allow us to conclude anything about

n .

Just because

n^{2} = 2 k

does not in itself suggest how we could write

n

as a multiple of 2.

Try something else: write the contrapositive of the statement. We get, for all integers

n,

n

is odd then

n^{2}

is odd. This looks much more promising. Our proof will look something like this:

Let

n

be an arbitrary integer. Suppose that

n

is not even. This means that …. In other words …. But this is the same as saying …. Therefore

n^{2}

is not even.

Now we fill in the details:

Proof.

We will prove the contrapositive. Let

n

be an arbitrary integer. Suppose that

n

is not even, and thus odd. Then

n = 2 k + 1

for some integer

k .

Now

n^{2} = (2 k + 1)^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1 .

Since

2 k^{2} + 2 k

is an integer, we see that

n^{2}

is odd and therefore not even.

🔗

Example 3.2.5.

Prove: for all integers

a

and

b,

a + b

is odd, then

a

is odd or

b

is odd.

🔗

Solution.

The problem with trying a direct proof is that it will be hard to separate

a

and

b

from knowing something about

a + b .

On the other hand, if we know something about

a

and

b

separately, then combining them might give us information about

a + b .

The contrapositive of the statement we are trying to prove is: for all integers

a

and

b,

a

and

b

are even, then

a + b

is even. Thus our proof will have the following format:

Let

a

and

b

be integers. Assume that

a

and

b

are both even. la la la. Therefore

a + b

is even.

Here is a complete proof:

Proof.

Let

a

and

b

be integers. Assume that

a

and

b

are even. Then

a = 2 k

and

b = 2 l

for some integers

k

and

l .

Now

a + b = 2 k + 2 l = 2 (k + l) .

Since

k + l

is an integer, we see that

a + b

is even, completing the proof.

Note that our assumption that

a

and

b

are even is really the negation of

a

b

is odd. We used De Morgan’s law here.

🔗

We have seen how to prove some statements in the form of implications: either directly or by contrapositive. Some statements are not written as implications to begin with.

🔗

Example 3.2.6.

Consider the following statement: for every prime number

p,

either

p = 2

p

is odd. We can rephrase this: for every prime number

p,

p \neq 2,

then

p

is odd. Now try to prove it.

🔗

Solution.

Proof.

Let

p

be an arbitrary prime number. Assume

p

is not odd. So

p

is divisible by 2. Since

p

is prime, it must have exactly two divisors, and it has 2 as a divisor, so

p

must be divisible by only 1 and 2. Therefore

p = 2 .

This completes the proof (by contrapositive).

🔗

Subsection Proof by Contradiction

There might be statements which really cannot be rephrased as implications. For example, “

\sqrt{2}

is irrational.” In this case, it is hard to know where to start. What can we assume? Well, say we want to prove the statement

P .

What if we could prove that

\neg P \to Q

where

Q

was false? If this implication is true, and

Q

is false, what can we say about

\neg P ?

It must be false as well, which makes

P

true!

🔗

This is why proof by contradiction works. If we can prove that

\neg P

leads to a contradiction, then the only conclusion is that

\neg P

is false, so

P

is true. That’s what we wanted to prove. In other words, if it is impossible for

P

to be false,

P

must be true.

🔗

Here are three examples of proofs by contradiction:

🔗

Example 3.2.7.

Prove that

\sqrt{2}

is irrational.

🔗

Solution.

Proof.

Suppose not. Then

\sqrt{2}

is equal to a fraction

\frac{a}{b} .

Without loss of generality, assume

\frac{a}{b}

is in lowest terms (otherwise reduce the fraction). So,

2 = \frac{a^{2}}{b^{2}}

2 b^{2} = a^{2} .

Thus

a^{2}

is even, and as such

a

is even. So

a = 2 k

for some integer

k,

and

a^{2} = 4 k^{2} .

We then have,

2 b^{2} = 4 k^{2}

b^{2} = 2 k^{2} .

Thus

b^{2}

is even, and as such

b

is even. Since

a

is also even, we see that

\frac{a}{b}

is not in lowest terms, a contradiction. Thus

\sqrt{2}

is irrational.

🔗

Example 3.2.8.

Prove: There are no integers

x

and

y

such that

x^{2} = 4 y + 2 .

🔗

Solution.

Proof.

We proceed by contradiction. So suppose there are integers

x

and

y

such that

x^{2} = 4 y + 2 = 2 (2 y + 1) .

x^{2}

is even. We have seen that this implies that

x

is even. So

x = 2 k

for some integer

k .

Then

x^{2} = 4 k^{2} .

This in turn gives

2 k^{2} = (2 y + 1) .

But

2 k^{2}

is even, and

2 y + 1

is odd, so these cannot be equal. Thus we have a contradiction, so there must not be any integers

x

and

y

such that

x^{2} = 4 y + 2 .

🔗

Example 3.2.9.

The Pigeonhole Principle: If more than

n

pigeons fly into

n

pigeon holes, then at least one pigeon hole will contain at least two pigeons. Prove this!

🔗

Solution.

Proof.

Suppose, contrary to stipulation, that each of the pigeon holes contain at most one pigeon. Then at most, there will be

n

pigeons. But we assumed that there are more than

n

pigeons, so this is impossible. Thus there must be a pigeonhole with more than one pigeon.

While we phrased this proof as a proof by contradiction, we could have also used a proof by contrapositive since our contradiction was simply the negation of the hypothesis. Sometimes this will happen, in which case you can use either style of proof. There are examples however where the contradiction occurs “far away” from the original statement.

🔗

Subsection Proof by (counter) Example

It is almost NEVER okay to prove a statement with just an example. Certainly none of the statements proved above can be proved through an example. This is because in each of those cases we are trying to prove that something holds of all integers. We claim that

n^{2}

being even implies that

n

is even, no matter what integer

n

we pick. Showing that this works for

n = 4

is not even close to enough.

🔗

This cannot be stressed enough. If you are trying to prove a statement of the form

\forall x P (x),

you absolutely CANNOT prove this with an example.

This is not to say that looking at examples is a waste of time. Doing so will often give you an idea of how to write a proof. But the examples do not belong in the proof.

🔗

However, existential statements can be proven this way. If we want to prove that there is an integer

n

such that

n^{2} - n + 41

is not prime, all we need to do is find one. This might seem like a silly thing to want to prove until you try a few values for

n .

🔗

$n$	1	2	3	4	5	6	7
$n^{2} - n + 41$	41	43	47	53	61	71	83

So far we have gotten only primes. You might be tempted to conjecture, “For all positive integers

n,

the number

n^{2} - n + 41

is prime.” If you wanted to prove this, you would need to use a direct proof, a proof by contrapositive, or another style of proof, but certainly it is not enough to give even 7 examples. In fact, we can prove this conjecture is false by proving its negation: “There is a positive integer

n

such that

n^{2} - n + 41

is not prime.” Since this is an existential statement, it suffices to show that there does indeed exist such a number.

🔗

In fact, we can quickly see that

n = 41

will give

41^{2}

which is certainly not prime. You might say that this is a counterexample to the conjecture that

n^{2} - n + 41

is always prime. Since so many statements in mathematics are universal, making their negations existential, we can often prove that a statement is false (if it is) by providing a counterexample.

🔗

Example 3.2.10.

Above we proved, “for all integers

a

and

b,

a + b

is odd, then

a

is odd or

b

is odd.” Is the converse true?

🔗

Solution.

The converse is the statement, “for all integers

a

and

b,

a

is odd or

b

is odd, then

a + b

is odd.” This is false! How do we prove it is false? We need to prove the negation of the converse. Let’s look at the symbols. The converse is

\forall a \forall b ((O (a) \lor O (b)) \to O (a + b)) .

We want to prove the negation:

\neg \forall a \forall b ((O (a) \lor O (b)) \to O (a + b)) .

Simplify using the rules from the previous sections:

\exists a \exists b ((O (a) \lor O (b)) \land \neg O (a + b)) .

As the negation passed by the quantifiers, they changed from

\forall

\exists .

We then needed to take the negation of an implication, which is equivalent to asserting the if part and not the then part.

Now we know what to do. To prove that the converse is false we need to find two integers

a

and

b

so that

a

is odd or

b

is odd, but

a + b

is not odd (so even). That’s easy: 1 and 3. (remember, “or” means one or the other or both). Both of these are odd, but

1 + 3 = 4

is not odd.

🔗

Subsection Proof by Cases

We could go on and on and on about different proof styles (we haven’t even mentioned induction or combinatorial proofs here), but instead we will end with one final useful technique: proof by cases. The idea is to prove that

P

is true by proving that

Q \to P

and

\neg Q \to P

for some statement

Q .

So no matter what, whether or not

Q

is true, we know that

P

is true. In fact, we could generalize this. Suppose we want to prove

P .

We know that at least one of the statements

Q_{1}, Q_{2}, \dots, Q_{n}

is true. If we can show that

Q_{1} \to P

and

Q_{2} \to P

and so on all the way to

Q_{n} \to P,

then we can conclude

P .

The key thing is that we want to be sure that one of our cases (the

Q_{i}

’s) must be true no matter what.

🔗

If that last paragraph was confusing, perhaps an example will make things better.

🔗

Example 3.2.11.

Prove: For any integer

n,

the number

(n^{3} - n)

is even.

🔗

Solution.

It is hard to know where to start this, because we don’t know much of anything about

n .

We might be able to prove that

n^{3} - n

is even if we knew that

n

was even. In fact, we could probably prove that

n^{3} - n

was even if

n

was odd. But since

n

must either be even or odd, this will be enough. Here’s the proof.

Proof.

We consider two cases: if

n

is even or if

n

is odd.

Case 1:

n

is even. Then

n = 2 k

for some integer

k .

This give

\begin{aligned} n^{3} - n & = 8 k^{3} - 2 k \\ = 2 (4 k^{2} - k), \end{aligned}

and since

4 k^{2} - k

is an integer, this says that

n^{3} - n

is even.

Case 2:

n

is odd. Then

n = 2 k + 1

for some integer

k .

This gives

\begin{aligned} n^{3} - n & = (2 k + 1)^{3} - (2 k + 1) \\ = 8 k^{3} + 12 k^{2} + 6 k + 1 - 2 k - 1 \\ = 2 (4 k^{3} + 6 k^{2} + 2 k), \end{aligned}

and since

4 k^{3} + 6 k^{2} + 2 k

is an integer, we see that

n^{3} - n

is even again.

Since

n^{3} - n

is even in both exhaustive cases, we see that

n^{3} - n

is indeed always even.

🔗

Exercises Exercises

1.

Consider the statement “for all integers

a

and

b,

a + b

is even, then

a

and

b

are even”

🔗

Write the contrapositive of the statement.
Write the converse of the statement.
Write the negation of the statement.
Is the original statement true or false? Prove your answer.
Is the contrapositive of the original statement true or false? Prove your answer.
Is the converse of the original statement true or false? Prove your answer.
Is the negation of the original statement true or false? Prove your answer.

🔗

2.

For each of the statements below, say what method of proof you should use to prove them. Then say how the proof starts and how it ends. Bonus points for filling in the middle.

🔗

There are no integers $x$ and $y$ such that $x$ is a prime greater than 5 and $x = 6 y + 3 .$
For all integers $n,$ if $n$ is a multiple of 3, then $n$ can be written as the sum of consecutive integers.
For all integers $a$ and $b,$ if $a^{2} + b^{2}$ is odd, then $a$ or $b$ is odd.

🔗

3.

Consider the statement: for all integers

n,

n

is even then

8 n

is even.

🔗

Prove the statement. What sort of proof are you using?
Is the converse true? Prove or disprove.

🔗

4.

The game TENZI comes with 40 six-sided dice (each numbered 1 to 6). Suppose you roll all 40 dice.

🔗

Prove that there will be at least seven dice that land on the same number.
How many dice would you have to roll before you were guaranteed that some four of them would all match or all be different? Prove your answer.

🔗

5.

Prove that for all integers

n,

it is the case that

n

is even if and only if

3 n

is even. That is, prove both implications: if

n

is even, then

3 n

is even, and if

3 n

is even, then

n

is even.

🔗

6.

Prove that

\sqrt{3}

is irrational.

🔗

7.

Consider the statement: for all integers

a

and

b,

a

is even and

b

is a multiple of 3, then

a b

is a multiple of 6.

🔗

Prove the statement. What sort of proof are you using?
State the converse. Is it true? Prove or disprove.

🔗

8.

Prove the statement: For all integers

n,

5 n

is odd, then

n

is odd. Clearly state the style of proof you are using.

🔗

9.

Prove the statement: For all integers

a,

b,

and

c,

a^{2} + b^{2} = c^{2},

then

a

b

is even.

🔗

10.

Suppose that you would like to prove the following implication:

🔗

For all numbers $n,$ if $n$ is prime then $n$ is solitary.
🔗

Write out the beginning and end of the argument if you were to prove the statement,

🔗

Directly
By contrapositive
By contradiction

🔗

You do not need to provide details for the proofs (since you do not know what solitary means). However, make sure that you provide the first few and last few lines of the proofs so that we can see that logical structure you would follow.

🔗

11.

Suppose you have a collection of 5-cent stamps and 8-cent stamps. We saw earlier that it is possible to make any amount of postage greater than 27 cents using combinations of both these types of stamps. But, let’s ask some other questions:

🔗

Prove that if you only use an even number of both types of stamps, the amount of postage you make must be even.
Suppose you made an even amount of postage. Prove that you used an even number of at least one of the types of stamps.
Suppose you made exactly 72 cents of postage. Prove that you used at least 6 of one type of stamp.

🔗

12.

Prove:

x = y

if and only if

x y = \frac{(x + y)^{2}}{4} .

Note, you will need to prove two “directions” here: the “if” and the “only if” part.

🔗

13.

Prove that

\log (7)

is irrational.

🔗

14.

Prove that there are no integer solutions to the equation

x^{2} = 4 y + 3 .

🔗

15.

Prove that every prime number greater than 3 is either one more or one less than a multiple of 6.

🔗

16.

Your “friend” has shown you a “proof” he wrote to show that

1 = 3 .

Here is the proof:

🔗

Proof.

I claim that

1 = 3 .

Of course we can do anything to one side of an equation as long as we also do it to the other side. So subtract 2 from both sides. This gives

- 1 = 1 .

Now square both sides, to get

1 = 1 .

And we all agree this is true.

🔗

What is going on here? Is your friend’s argument valid? Is the argument a proof of the claim

1 = 3 ?

Carefully explain using what we know about logic.

🔗

17.

A standard deck of 52 cards consists of 4 suites (hearts, diamonds, spades and clubs) each containing 13 different values (Ace, 2, 3, …, 10, J, Q, K). If you draw some number of cards at random you might or might not have a pair (two cards with the same value) or three cards all of the same suit. However, if you draw enough cards, you will be guaranteed to have these. For each of the following, find the smallest number of cards you would need to draw to be guaranteed having the specified cards. Prove your answers.

🔗

Three of a kind (for example, three 7’s).
A flush of five cards (for example, five hearts).
Three cards that are either all the same suit or all different suits.

🔗

18.

Suppose you are at a party with 19 of your closest friends (so including you, there are 20 people there). Explain why there must be least two people at the party who are friends with the same number of people at the party. Assume friendship is always reciprocated.

🔗

19.

Your friend has given you his list of 115 best Doctor Who episodes (in order of greatness). It turns out that you have seen 60 of them. Prove that there are at least two episodes you have seen that are exactly four episodes apart on your friend’s list.

🔗