Direct Proof and Counterexample

Section 3.1 Direct Proof and Counterexample

Before starting proof techniques, we introduce a few mathematical definitons. Keep in mind, mathematical definitions are constructed to provide a common language for proofs. They are intended to provide rigor and precision. They are NOT intended to provide conceptual understanding. You need to develop conceptual understanding of the terms apart from the definition. However, we need to rely on definitions to provide structure for our proofs.

🔗

We defined the integers in Definition 1.1.1. Recall from Section 2.1, we use

Z

for the set of integers.

🔗

Definition 3.1.1.

An integer,

n,

is even if it has the form

n = 2 k

for some

k \in Z .

🔗

Definition 3.1.2.

An integer

n,

is odd if it has the form

n = 2 k + 1

for some

k \in Z .

🔗

You are probably familiar, generally, with even numbers such as 2, 4, 6, 8, and odd numbers such as 3, 5, 7, 9. But the next example uses the definitions to look at more examples.

🔗

Example 3.1.3. Even or Odd.

Is -5 even or odd?

Answer 1.

- 5 = 2 (- 3) + 1

- 3 \in Z .

Is 0 even or odd?

Answer 2.

0 = 2 (0)

0 \in Z .

Let

a, b \in Z .

6 a^{2} b

even or odd?

Answer 3.

6 a^{2} b = 2 (3 a^{2} b)

3 a^{2} b \in Z .

6 a^{2} b

Let

a, b \in Z .

20 a - 6 b + 1

even or odd?

Answer 4.

20 a - 6 b + 1 = 2 (10 a - 3 b) + 1

10 a - 3 b \in Z .

20 a - 6 b + 1

Activity 3.1.1. Always, Sometimes, or Never Even.

Let

a, b

be integers. Determine if each of the following are always even, always odd, or sometimes even/ sometimes odd.

🔗

(a)

12 a b^{3}

🔗

(b)

3 a b

🔗

(c)

10 b^{2} - 4 a b + 1

🔗

(d)

4 b + 3

🔗

(e)

5 a + 3 b

🔗

We’ve now seen several examples of even/ odd integers. Are there integers which are both even and odd? Can an integer be neither even nor odd? The answer to both questions is no. However, proving that every integer is even or odd (and not both), is pretty challenging, and we won’t try to do it, yet. But for the moment we will assume if we know an integer is NOT even, then it must be odd, and vice versa.

🔗

We start our proof techniques by looking at how to prove universal conditional statements, which we studied in Section 2.3. Recall, a universal conditional statement has the form “For all

x \in D,

x

has property

P

then

x

has property

Q .

” We can restate this using symbolic notation: For all

x \in D, P (x) \to Q (x) .

Although we saw how to write “for all” using the symbol

\forall,

in this book we will generally avoid the quantifier symbols in our proofs. This just helps with clarity for the reader and is fairly standard in mathematical writing. However, the techniques for understanding and negating quantified statements from Section 2.2 still apply.

🔗

One very limited method for proving universal conditional statements is the method of exhaustion: for each specific

a \in D

where

P (a)

is true, show

Q (a)

is true. In other words, we check if

P (a)

then

Q (a)

for each

a \in D .

🔗

Example 3.1.4. Method of Exhaustion.

Prove for all

n \in Z,

n

is even and

4 \leq n \leq 16,

then

n

can be written as the sum of prime numbers.

Proof.

We can find all the integers that are even and

4 \leq n \leq 16 .

This is the set

{4, 6, 8, 10, 12, 14, 16} .

For each of these numbers we can demonstrate a way to write them as the sum of primes:

4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7, 12 = 5 + 7, 14 = 7 + 7, 16 = 11 + 5 .

The method of exhaustion only works if we can show the statement for every

x \in D .

But if

D

is infinite, we need to use a more general method. We saw the limitations of this method in Section 1.1. Although this method won’t result in a proof if our set is infinite, it can be a helpful first stab at a proof in that generating examples can lead to more general insight into the problem. Our first more general technique is the method of direct proof.

🔗

Method of Direct Proof.

To prove statements of the form “for all

x \in D, P (x) \to Q (x)

” using the method of direct proof we use the following process.

🔗

Let $x \in D .$ Make sure this is a variable or generic $x,$ not a specific value.
Assume $P (x)$ is true.
Show $Q (x)$ is true.

🔗

Example 3.1.5. Direct Proof.

Prove for all

x \in Z,

x

is even, then

x + 1

is odd.

Proof.

Let

x

be even. Then by definition,

x = 2 k

for some

k \in Z .

Then

x + 1 = 2 k + 1

where

k \in Z .

Which means

x + 1

is odd.

Example 3.1.6. Sum of Even Numbers.

Prove the sum of two even integers is even.

Note, this statement is not obviously in the form of an if...then. We often have to translate statements into more formal statements before proving them.

More formally, prove for all

a, b \in Z

a

and

b

are even, then

a + b

is even.

Proof.

Let

a, b

be even. Then by definition,

a = 2 k

for some

k \in Z

and

b = 2 j

for some

j \in Z .

(Note, we cannot use

k

for both

a

and

b

as they likely are two different numbers.) Then

a + b = 2 k + 2 j = 2 (k + j)

where

k + j \in Z .

Which means

a + b

is even.

A counterexample is used to disprove a universal conditional statements. If we have a universal conditional statement of the form “for all

x \in D, P (x) \to Q (x)

”, we show it is false with the following process.

🔗

Disproving by Counterexample.

To disprove statements of the form “for all

x \in D, P (x) \to Q (x)

” we find a counterexample.

🔗

Find $x \in D$ making, $P (x)$ true and $Q (x)$ false. Note, this step may happen as scratchwork, not part of your counterexample.
For your counterexample, state $x .$
Show $x \in D,$ $P (x)$ is true and $Q (x)$ is false.

🔗

Example 3.1.7. Counterexample.

Disprove the statement every prime number,

p,

is odd.

Let

p = 2 .

Then

2

is prime and

2

is not odd.

Activity 3.1.2. Proving a Statement is False.

Give a counterexample to show the following statement is false: for all

a, b \in R

a^{2} = b^{2}

then

a = b .

🔗

Some proof writing advice:

🔗

Make the proof self-contained. Try not to reference many other mathematical facts. Many proofs in this course will rely entirely on definitions.
Use complete sentences. Even equations have a sentence structure. Your proof should be able to be read in sentences.
Give reasons. Connect your statements together.
Include words. Often using a word is better that using a symbol. Many proofs have no symbols in them at all.
The audience for your proofs is not the instructor. Think of the audience as being your peers in the course or even yourself in a few weeks (or months) when you might have forgotten the specific content. Write so you will know what you meant later.
The goal of a proof is to write a clear, easy to follow argument--not to just get to the end. The “answer” is the proof itself. Use space, start a new line, set equations on their own line.
Never feel that you have to be able to know what the end of the proof will look like before you can start. Write proofs one step at a time. Start with what you know. See if you can do one thing. See if you can do another thing. Look at where you want to go. Do not try to see the whole picture at once. This is also good advice for reading a proof.

🔗

Some common proof-writing errors:

🔗

Using an example for a proof. If you need to prove a statement for all $x,$ it is not enough to show it for an example.
Using the same variable to represent two different things.
Jumping to conclusions. Giving inadequate reasons. This often occurs if you rely on additional mathematical ideas or don’t connect your ideas to each other.
Assuming what you need to prove. This is a big one. This most often occurs when there is confusion about conditional statements. Be careful about identifying the “if” and the “then” in a statement.

🔗

Often in math we need to identify whether a statement is true or false, so that we know whether we need to prove the true statement or disprove the false one. In order to practice, we give a few more definitions.

🔗

Definition 3.1.8.

An integer,

n,

is prime if

n > 1

and, for all positive integers

r, s,

n = r s

then

r = 1

s = 1 .

🔗

Definition 3.1.9.

An integer,

n,

is composite if

n > 1

and

n = r s

for some positive integers

r, s

with

r \neq 1

and

s \neq 1 .

🔗

Example 3.1.10. Prime or Composite.

Is 1 prime?

Answer 1.

n > 1 .

Is 1 composite?

Answer 2.

n > 1 .

Is 121 prime?

Answer 3.

121 = (11) (11) .

Let

a \in Z .

3 a

composite?

Answer 4.

a = 1

a > 1

3 a

Example 3.1.11. Prove or Disprove.

Prove or disprove there exists a positive integer

n

such that

n^{2} + 3 n + 2

is prime.

Since we need to try to decide if the statement is true or false, first try some examples.

Answer 1.

n = 1; n^{2} + 3 n + 2 = 6; not prime n = 5; n^{2} + 3 n + 2 = 42; not prime n = 8; n^{2} + 3 n + 2 = 90; not prime

After trying several examples, we might guess that it is false. If we want to disprove the statement then we need to prove the negation. Find the negation of the statement.

Answer 2.

For all positive integers

n, n^{2} + 3 n + 2

is not prime (is composite).

So we need to show that for a general

n

we can always write

n^{2} + 3 n + 2

as a product of

r, s

with

r, s \neq 1 .

We can try to factor the expression:

n^{2} + 3 n + 2 = (n + 2) (n + 1) .

Let

r = n + 2, s = n + 1 .

We need to show that

r, s \neq 1 .

Since

n > 0, n + 2 > 2

and

n + 1 > 1 .

Thus

r, s \neq 1 .

Therefore,

n^{2} + 3 n + 2

is not prime.

Activity 3.1.3. Prove or Disprove.

Let

m

and

n

be integers. Prove or disprove the following statements.

🔗

(a)

n

is even, then

5 n

is even.

🔗

(b)

n

is odd, then

5 n + 1

is odd.

🔗

(c)

n, m

are odd, then their product,

n m,

is odd.

🔗

Exercises Exercises

1.

Use the definitions of even, odd, prime and composite to justify your answer to each of the following questions. Let

m

and

n

be integers.

🔗

Is $6 m + 8 n$ even?
Is $10 m n + 7$ odd?
If $m > n > 0,$ is $m^{2} - n^{2}$ composite?

🔗

2.

Prove there are integers

m

and

n

such that

m > 1

and

n > 1

and

\frac{1}{n} + \frac{1}{m}

is an integer.

🔗

3.

Prove there is an integer

n

such that

2 n^{2} - 5 n + 2

is prime.

🔗

4.

Disprove by giving a counterexample: for all real numbers

a

and

b,

a < b

then

a^{2} < b^{2} .

🔗

5.

Disprove by giving a counterexample: for all integers,

m

and

n,

2 m + n

is odd then

m

and

n

are both odd.

🔗

6.

Find the mistakes in the following “proof.”

🔗

Theorem: For all integers

k,

k > 0

then

k^{2} + 2 k + 1

is composite.

🔗

“Proof”: For

k = 2,

k^{2} + 2 k + 1 = 2^{2} + 2 \cdot 2 + 1 = 9 .

But

9 = 3 \cdot 3,

and so 9 is composite. Hence the theorem is true.

🔗

7.

Find the mistakes in the following “proof.”

🔗

Theorem: The difference between any odd integer and any even integer is odd.

🔗

“Proof”: Suppose

n

is an odd integer, and

m

is an even integer. By definition of odd,

n = 2 k + 1

where

k

is an integer, and by definition of even

m = 2 k

where

k

is an integer. Then

🔗

n - m = 2 k + 1 - 2 k = 1.

Since 1 is odd the difference between an odd integer and and even integer is odd.

🔗

8.

Prove the difference of any even integer minus any odd integer is odd.

🔗

9.

Prove the sum of any two odd integers is even.

🔗

10.

Prove the following statement is false: there exists an integer

n

such that

6 n^{2} + 27

is prime.

🔗

11.

Prove or disprove the following statements using the method of direct proof or counterexample.

🔗

The difference of any two odd integers is odd.
The product of any even integer and any integer is even.
The difference of any two even integers is even.
The difference of any two odd integers is even.
For all integers $n,$ if $n$ is prime then $(- 1)^{n} = - 1 .$
For all integers $n,$ $n^{2} - n + 11$ is prime.
If $m$ and $n$ are perfect squares, then $m + n + 2 (m n)^{1 / 2}$ is a perfect square.

🔗

Prev Top Next