Section1pt4

The Proof Page

by D. A. Kouba

Section 1.4- Bacic Proof Methods I- Direct Proof, Proof by Cases, and Proof by Working Backward

In this section we will introduce specific types or methods of proof of mathematical statements. They include direct proof, proof by cases, and proof by working backward. We will use the following well known facts :

$\underline { \rm FACTS }$ :

1. Integer is even if for some integer .
2. Integer is odd if for some integer .
3. Integer divides integer , written , $a \mid b$ , if for some integer . NOTE : This definition applies only to integers.
4. Natural number (positive integer) is prime if its only natural number factors are and . truein
5. The absolute value of a real number , written $\mid z \mid$ , is defined in the following way : $\mid z \mid \ = z$ if $z \ge 0$ ; $\mid z \mid \ = -z$ if .

DIRECT PROOF

The direct proof of a mathematical statement should include the following.

1. Begin with a clear written statement of the given facts or assumptions.
2. Next provide a clear written statement of what is to be proven.
3. Then write the body of the proof, a sequence of logical steps or consequences leading to the desired result. Provide clear reasoning or substantiation for each step in the proof. A good rule of thumb is this. Treat each proof that you write as a writing exercise as well as a mathematical exercise. Remember that you are trying to convince your reader of the validity of your proof through the clarity and simplicity of your organization and logical reasoning. Finish your proof with a clear statement of that which was to be proven. (Many proofs are closed with the letters QED. This refers to the Latin ``quod est demonstratum," roughly meaning ``which is proven or demonstrated.") Shortcuts in proofs are to be avoided at this stage. Writing more details is better for those of you who are just learning how to write proofs.

Here is a simple example of a direct proof.

$\underline { \rm EXAMPLE }$ : Prove that if $x \mid a$ and $x \mid b$ , then $x \mid (a-b)$ .

Proof: ASSUME that $x \mid a$ and $x \mid b$ . Thus

and

for some integers

and

. SHOW that $x \mid (a-b)$ , i.e., show that

for some integer

. Then

(by assumptions)

(by distributive property)

where

is an integer. Thus, $x \mid (a-b)$ .

QED

Here is another example of a direct proof.

$\underline { \rm EXAMPLE }$ : Prove that if

is even and

is odd, then

is odd .

Proof: ASSUME that

is even and

is odd. Thus

and

for some integers

and

. SHOW that

is odd, i.e., show that

for some integer

. Then

(by assumptions)

(by distributive property)

(adding zero)

(by commutative property)

(by distributive property)

where

is an integer. Thus,

is odd.

QED

$\underline { \rm EXAMPLE }$ : Write clear and complete direct proofs for each of the following mathematical statements. Find solutions HERE : Page 1 , Page 2 .

1. If $x \mid a$ and $x \mid b$ , then $x \mid (a^2-b^2)$ .
2. If $x \mid a$ and $y \mid b$ , then $xy \mid ab$ .
3. If is even and is odd, then is odd .
4. If is odd, then is even .

PROOF BY CASES

A proof by cases of a mathematical statement should include the following.

1. Begin with a clear written statement of the given facts or assumptions.
2. Next provide a clear written statement of what is to be proven.
3. Now determine all possible cases which must be considered in order to prove the mathematical statement.
4. Then write the body of the proof. For each case, this must include a sequence of logical steps or consequences leading to the desired result. Provide clear reasoning or substantiation for each step in the proof. A good rule of thumb is this. Treat each proof that you write as a writing exercise as well as a mathematical exercise. Remember that you are trying to convince your reader of the validity of your proof through the clarity and simplicity of your organization and logical reasoning. Finish your proof with a clear statement of that which was to be proven. Shortcuts in proofs are to be avoided at this stage. Writing more details is better for those of you who are just learning how to write proofs.

Here is a simple example of a proof by cases.

$\underline { \rm EXAMPLE }$ : Prove that if

and

are real numbers, where $b \ne 0$ , then $\displaystyle{ \mid {a \over b} \mid } = \displaystyle{ {\mid a \mid} \over {\mid b \mid}}$ .

Proof: ASSUME that

and

are real numbers and $b \ne 0$ . SHOW that $\displaystyle{ \mid {a \over b} \mid } = \displaystyle{ {\mid a \mid} \over {\mid b \mid}}$ . We will consider the following cases.

$\underline { \rm CASE \ 1 }$ : Assume that $a \ge 0$ and

, so that $\displaystyle{ a \over b } \ge 0$ . Then $\mid a \mid = a$ , $\mid b \mid = b$ , and $\displaystyle{ \mid {a \over b} \mid } = \displaystyle{ a \over b } = \displaystyle{ {\mid a \mid} \over {\mid b \mid}}$ .

$\underline { \rm CASE \ 2 }$ : Assume that $a \ge 0$ and

, so that $\displaystyle{ a \over b } \le 0$ . Then $\mid a \mid = a$ , $\mid b \mid = -b$ , and $\displaystyle{ \mid {a \over b} \mid } = -\displaystyle{ a \over b } = \displaystyle{ a \over -b } = \displaystyle{ {\mid a \mid} \over {\mid b \mid}}$ .

$\underline { \rm CASE \ 3 }$ : Assume that

and

, so that $\displaystyle{ a \over b } < 0$ . Then $\mid a \mid = -a$ , $\mid b \mid = b$ , and $\displaystyle{ \mid {a \over b} \mid } = -\displaystyle{ a \over b } = \displaystyle{ -a \over b } = \displaystyle{ {\mid a \mid} \over {\mid b \mid}}$ .

$\underline { \rm CASE \ 4 }$ : Assume that

and

, so that $\displaystyle{ a \over b } > 0$ . Then $\mid a \mid = -a$ , $\mid b \mid = -b$ , and $\displaystyle{ \mid {a \over b} \mid } = \displaystyle{ a \over b } = \displaystyle{ -a \over -b } = \displaystyle{ {\mid a \mid} \over {\mid b \mid}}$ .

Thus, for all possible cases, it has been proven that $\displaystyle{ \mid {a \over b} \mid } = \displaystyle{ {\mid a \mid} \over {\mid b \mid}}$ .

QED

Here is another example of a proof by cases.

$\underline { \rm EXAMPLE }$ : Prove that $x \ + \mid x-7 \mid \ \ge 7$ for all real numbers

.

Proof: ASSUME that

is a real number. SHOW that $x \ + \mid x-7 \mid \ \ge 7$ . We will consider the following cases.

$\underline { \rm CASE \ 1 }$ : Assume that $x \ge 7$ . Then $x-7 \ge 0$ and $\mid x-7 \mid = x-7$ , so that $x \ + \mid x-7 \mid = x + (x-7) = 2x-7 \ge 2(7)-7 = 14-7 = 7$ , i.e., $x \ + \mid x-7 \mid \ \ge 7$ .

$\underline { \rm CASE \ 2 }$ : Assume that

. Then

and $\mid x-7 \mid = -(x-7) = 7-x$ , so that $x + \mid x-7 \mid = x + (7-x) = 7 \ge 7$ , i.e., $x \ + \mid x-7 \mid \ \ge 7$ .

Thus, for all possible cases, it has been proven that $x \ + \mid x-7 \mid \ \ge 7$ .

QED

$\underline { \rm EXAMPLE }$ : Write clear and complete proofs by cases for each of the following mathematical statements. Find solutions HERE : Page 1 , Page 2 , Page 3 .

1. If is a real number, then $\mid x+3 \mid - \ x > 2$ .
2. If is a real number, then $\mid x-1 \mid + \mid x+5 \mid \ \ge 6$ .
3. The expression is odd for all integers .
4. If is an even integer, then or for some integer .
5. If and are real numbers, then $\mid \ \mid a \mid - \mid b \mid \ \mid \ \le \ \mid a-b \mid$ .

PROOF BY WORKING BACKWARD

A proof by working backward of a mathematical statement should include the following.

1. Begin with a clear written statement of the given facts or assumptions.
2. Next provide a clear written statement of what is to be proven.
3. Then write the body of the proof. Begin with the final result, which must be PROVEN TRUE, working backward step-by-step, writing equivalent statements, until a connection is made with the assumptions of the problem or some other TRUE statement(s). Provide clear reasoning or substantiation for each step in the proof. A good rule of thumb is this. Treat each proof that you write as a writing exercise as well as a math exercise. Remember that you are trying to convince your reader of the validity of the proof through the clarity and simplicity of your organization and logical reasoning. Finish your proof with a clear statement of that which was to be proven. Shortcuts in proofs are to be avoided at this stage. Writing more details is better for those of you who are just learning how to write proofs.

Here is a simple example of a proof by working backward.

$\underline { \rm EXAMPLE }$ : Prove that $x^2 + y^2 \ge 2xy$ for all real numbers

and

.

Proof: ASSUME that

and

are real numbers. SHOW that $x^2 + y^2 \ge 2xy$ . But

$x^2 + y^2 \ge 2xy$ . . . is TRUE

iff

$x^2 + y^2 - 2xy \ge 0$ . . . is TRUE

iff

$x^2 - 2xy + y^2 \ge 0$ . . . is TRUE

iff

$(x-y)^2 \ge 0$ . . . is TRUE .

Since the last statement is TRUE, all of the equivalent statements are TRUE. In particular, $x^2 + y^2 \ge 2xy$ .

QED

$\underline { \rm EXAMPLE }$ : Write clear and complete proofs by working backward for each of the following mathematical statements. Find solutions HERE : Page 1 , Page 2 , Page 3 , Page 4 .

1. The expression $x + \displaystyle{ 9 \over x } \ge 6$ for all real numbers .
2. If is divisible by 3 for some integer , then is divisible by 3.
3. The expression $\displaystyle{ x^4 \over 4 } + (x+1)^3 > \displaystyle{(x+1)^4 \over 4 }$ for all real numbers $x \ge -1$ .
4. There is a fixed positive integer for which $\displaystyle{ 3 \over n } < \displaystyle{ n-4 \over n+10 }$ for all integers $n \ge N$ .

RETURN to The Proof Page .

Please e-mail your comments, questions, or suggestions to D. A. Kouba at kouba@math.ucdavis.edu .

Next: About this document ...

Duane Kouba 2002-06-28