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 } $ :

DIRECT PROOF



The direct proof of a mathematical statement should include the following. 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 $ a=xm $ and $ b=xn $ for some integers $ m $ and $n$. SHOW that $ x \mid (a-b) $, i.e., show that $ a-b = xq $ for some integer $ q $. Then

$ a-b = xm - xn $ (by assumptions)

$ = x(m-n) $ (by distributive property)

$ = x q $ ,

where $ q=m-n $ is an integer. Thus, $ x \mid (a-b) $.

QED



Here is another example of a direct proof.

$ \underline { \rm EXAMPLE } $ : Prove that if $ m $ is even and $n$ is odd, then $ m+n-2 $ is odd .

Proof: ASSUME that $ m $ is even and $n$ is odd. Thus $m=2k$ and $ n=2p+1 $ for some integers $ k $ and $ p $. SHOW that $ m+n-2 $ is odd, i.e., show that $ m+n-2=2q+1$ for some integer $ q $. Then

$ m+n-2 = 2k + (2p+1) - 2 $ (by assumptions)

$ = 2(k+p) - 1 $ (by distributive property)

$ = 2(k+p) - 1 + 2 - 2 $ (adding zero)

$ = 2(k+p) + 1 - 2 $

$ = 2(k+p) - 2 + 1 $ (by commutative property)

$ = 2(k+p-1) + 1 $ (by distributive property)

$ = 2 q + 1 $ ,

where $ q=k+p-1$ is an integer. Thus, $ m+n-2 $ 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 .

PROOF BY CASES



A proof by cases of a mathematical statement should include the following. Here is a simple example of a proof by cases.

$ \underline { \rm EXAMPLE } $ : Prove that if $ a $ and $ b $ 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 $ a $ and $ b $ 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 $ b>0 $, 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 $ b<0 $, 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 $ a < 0 $ and $ b>0 $, 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 $ a < 0 $ and $ b<0 $, 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 $ x $ .

Proof: ASSUME that $ x $ 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 $ x < 7 $ . Then $ x-7 < 0 $ 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 .

PROOF BY WORKING BACKWARD



A proof by working backward of a mathematical statement should include the following. 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 $ x $ and $ y $ .

Proof: ASSUME that $ x $ and $ y $ 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 .




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