Proof methods and Strategy

Niloufar Shafiei
Proof methods (review)
p
q
 Direct technique

Premise: p

Conclusion: q
 Proof by contraposition

Premise: ¬q

Conclusion: ¬p
 Proof by contradiction

Premise: p ¬q

Conclusion: a contradiction

1
Prove a theorem (review)
How to prove a theorem?
1. Choose a proof method
2. Construct argument steps

Argument:
premises

conclusion

2
Proof by cases

Prove a theorem by considering different cases
seperately

To prove q it is sufficient to prove

p1  p2  …  pn
p1
q
p2
q
…
pn
q
3
Exhaustive proof
 Exhaustive proof

Number of possible cases is relatively small.

A special type of proof by cases

Prove by checking a relatively small number of
cases

4
Exhaustive proof (example)
Show that n2
2n if n is positive integer with n
<3.
Proof (exhaustive proof):
 Check possible cases

n=1 1
2

n=2 4
4

5
Exhaustive proof (example)
Prove that the only consecutive positive integers not
exceeding 50 that are perfect powers are 8 and 9.
Proof (exhaustive proof):
 Check possible cases Definition:

a=2 1,4,9,16,25,36,49 An integer is a
perfect power if it

a=3 1,8,27
equals na, where

a=4 1,16 a in an integer

a=5 1,32 greater than 1.

a=6 1
 The only consecutive numbers that are perfect powers
are 8 and 9.
6
 Proof by cases

Proof by cases must cover all possible cases.

7
Proof by cases (example)
Prove that if n is an integer, then n2
n.

Proof (proof by cases):

Break the theorem into some cases
1. n = 0
2. n
1
3. n
-1

8
Proof by cases (example)
Prove that if n is an integer, then n2
n.

Proof (proof by cases):

Check possible cases
1. n = 0 02
0
2. n
1
n.n
1.n n2
n
3. n
-1
n2
0 n2
n

n2
n holds in all three cases, we can conclude that if
n is an integer, then n2
n.
9
Proof by cases (example)
Prove that |xy|=|x||y|, where x and y are real numbers.
Definition:
Proof (proof by cases): The absolute

Break the theorem into some cases value of a, |a|,
1. x and y both nonnegative equals a when
2. x nonnegative and y is negative a
0 and equals
3. x negative and y nonnegative -a when a<0.
4. x and y both negative

10
Proof by cases (example)
Prove that |xy|=|x||y|, where x and y are real numbers.
Definition:
Proof (proof by cases): The absolute value of a, |a|,
equals a when a
0 and

Check possible cases
equals -a when a<0.
1. x and y both nonnegative
|xy| = xy |x|=x |y|=y |x||y| = xy
|xy| = |x||y|
2. x nonnegative and y is negative
|xy| = -xy |x|=x |y| = -y |x||y| = -xy
|xy| = |x||y|

11
Proof by cases (example)
Prove that |xy|=|x||y|, where x and y are real numbers.
Definition:
Proof (proof by cases): The absolute value of a, |a|,

Check possible cases equals a when a
0 and
equals -a when a<0.
3. x negative and y nonnegative
|xy| = -xy |x|=-x |y| = y |x||y| = -xy
|xy| = |x||y|
4. x and y both negative
|xy| = xy |x|=-x |y| = -y |x||y| = xy
|xy| = |x||y|

It is true for all four cases, so |xy|=|x||y|, where x and y are
real numbers.
12
Proof by cases (example)
Prove that x2 + 3y2 = 8 is false where x and y are integers.

Proof (proof by cases):

 Find possible cases

x = -2, -1, 0, 1, 2

y = -1, 0, 1
 Check possible cases

x2 = 0, 1, 4

3y2 = 0, 3

Largest sum of x2 and 3y2 is 7.
 So, x2 + 3y2 = 8 is false where x and y are integers.
13
Without loss of generality
 How to shorten the proof by cases.

If same argument is used in different cases.
 Proof theses cases together, without loss
of generality (WLOG).

Incorrect use of this principle can lead to
errors.

14
Without loss of generality (example)
Prove that |xy|=|x||y|, where x and y are real numbers.

Proof (proof by cases):

Check possible cases
1. x and y both nonnegative
2. x nonnegative and y is negative
3. x negative and y nonnegative
4. x and y both negative

15
Without loss of generality (example)
Prove that |xy|=|x||y|, where x and y are real numbers.

Proof (proof by cases):

Check possible cases
1. x and y both nonnegative
2. x nonnegative and y is negative
|xy| = -xy |x|=x |y| = -y |x||y| = -xy
|xy| = |x||y|
3. x negative and y nonnegative
we can complete this case using the same argument as
we used for case 2.
4. x and y both negative

16
Without loss of generality (example)
Show that (x+y)r < xr + yr where x and y are positive
real numbers and r is a real number with 0 < r < 1.
Proof:

Without loss of generality assume x+y = 1.
x+y=t
(x/t) + (y/t) = 1
((x/t)+(y/t))r < (x/t)r + (y/t)r
tr ((x/t)+(y/t))r < tr (x/t)r + tr (y/t)r
(x+y)r < xr + yr
So, the inequality (x+y)r < xr + yr is the same when
(x+y=1) and (x+y=t).
17
Without loss of generality (example)
Show that (x+y)r < xr + yr where x and y are positive real
numbers and r is a real number with 0 < r < 1.

Proof:

We assume x+y = 1.

Since x and y are positive, 0< x < 1 and 0< y < 1.

0<r<1 0 < 1-r < 1

x1-r < 1 y1-r < 1

x / xr < 1 y / yr < 1

xr > x yr > y

xr + yr > x+y=1

xr + yr > (x+y)r = 1
18
Errors in proofs (example)
If x is a real number, then x2 is a positive real number.
Proof:
Case 1: x is positive
x2 is the product of two positive numbers, so x2 is positive.
Case2: x is negative
x2 is the product of two negative numbers, so x2 is
positive.
 Case x=0 is missed.

Case 3: x=0
x2 = 0, so x2 is not positive

Thus the theorem is false.
19
Errors in proofs (example)
Show that 1 = 2.
Proof:
Assume a and b are two equal positive integers.
1. a=b
2. a2 = ab
3. a2 - b2 = ab - b2
4. (a - b)(a + b) = b(a - b)
5. a + b = b
6. 2b = b
7. 1 = 2

Step 5: a - b = 0, so dividing both sides of the equation
by a-b is wrong. 20
Existence proofs
 A proof of a proposition of the form x P(x) is called
an existence proof.
 Existence proof

Constructive proof
 Finding an element a that P(a) is true.

Nonconstructive proof
 Prove x P(x) is true in some other way.
 Prove by contradiction

¬ x P(x) (
x ¬P(x) ) implies a
contradiction.
21
Constructive proof (example)
There is a positive integer that can be written
as the sum of squares of two positive
integers.

Proof:
 Find an example

5 = 22 + 1 2

22
Nonconstructive proof (example)
There exist irrational numbers x and y such that xy is rational
Proof: Definition:
 By previous example The real number r

2 is irrational. is rational if r=p/q,
 (2 ) 2
integers p and q
 Case 1: If (2 ) 2 is rational that q
.

Thus, theorem is proved
 Case 2: If (2 ) 2 is irrational

((2 ) 2 ) 2 = (2 ) 2 . 2 = (2 ) 2 = 2

2 (=2/1) is rational.

Thus, theorem is proved.
23
Uniqueness proofs
 Theorem assert the existence of a unique element.

Unique element:
 There is exactly one element with a particular
property.

What we need to show?
 There is an element x with this property.
(Existence)
 No other element y has this property.
If y has this property too, then x = y.
(Uniqueness)

24
Uniqueness proofs

Proof of “there is an element with unique

property P(x)”:
x (P(x)  y (y
x
¬P(x)))

25
Uniqueness proofs (example)
Show that if a and b are real numbers and
a
0 , then there is a unique real number r
such that ar + b = 0.

Proof: (uniqueness proof)

 Existence proof

r = - b/a

a(-b/a) + b = -b + b = 0
26
Uniqueness proofs (example)
Show that if a and b are real numbers and a
0 , then
there is a unique real number r such that ar + b = 0.

Proof: (uniqueness proof)

 uniqueness proof

Assume s is a real number such that as + b = 0.
as + b = ar + b
as = ar
s=r (a
0 )

So, if s
r, then as+b
0 .

27
Proof strategies
 Finding proofs can be challenging.

Replace terms by their definitions

Carefully analyze hypotheses and conclusion

Choose a proof technique

Attempt to prove the theorem

If it fails try different proof methods

28
Forward and backward reasoning
p
q
 Forward reasoning

Assume premises are true.

Using premises, axioms, other theorems,
construct a sequence of steps that leads to the
conclusion.
 Backward reasoning

Work on the conclusion

Find a statement r that you can prove r
q.
29
Backward reasoning (example)
Prove that arithmetic mean of two positive real numbers is
more than their geometric mean.

Proof: (backward reasoning) Arithmetic mean

(x+y)/2 >
xy of x and y:
(x+y)2/4 > xy
(x+y)/2
(x+y)2 > 4xy
Geometric mean
x2 + 2xy + y2 > 4xy
of x and y:
x2 - 2xy + y2 > 0

xy
(x-y)2 > 0
We can easily reverse the steps to construct a proof using
forward reasoning.
30
Backward reasoning (example)
Prove that arithmetic mean of two positive real numbers
is more than their geometric mean.
Arithmetic mean
Proof: (backward reasoning) of x and y:
(x-y)2 > 0 (x+y)/2
x2 - 2xy + y2 > 0 Geometric mean
x2 + 2xy + y2 > 4xy of x and y:
(x+y)2 > 4xy
xy
(x+y)2/4 > xy
(x+y)/2 >
xy

31
Backward reasoning (example)
Game:

There are 15 stones on a pile

Two players takes turn to remove stones from the
pile.

A player can remove one, two or three stones at a
time from the pile.

The player who removes the last stone wins the
game.

Show that player 1 can win the game no matter what

player 2 does.
32
Backward reasoning (example)
Proof: (backward reasoning)
Find a strategy for player 1 that player 1 always wins.
(backward reasoning)

Player 1 wins.

At last step, 1,2 or 3 stones are left on the pile.
(How can player 1 make player 2 leave 1, 2 or 3 stones on
the pile?)

Player 1 leaves 4 stones on the pile.
(How many stones should be left on the pile for player 1?)

5, 6 or 7 stones are left on the pile for player 1.
(How can player 1 make player 2 leave 5, 6 or 7 stones on
the pile?)
33
Backward reasoning (example)
Proof: (backward reasoning)

Player 1 leaves 8 stones on the pile.
(How many stones should be left on the pile for
player 1?)

9, 10 or 11 stones are left on the pile for player 1.
(How can player 1 make player 2 leave 9, 10 or 11
stones on the pile?)

Player 1 leaves 12 stones on the pile.

34
Backward reasoning (example)
Proof: (backward reasoning)
 Strategy for player 1

Turn 1: leave 12 stones on the pile for player 2

Turn 2: player 2

Turn 3: leave 8 stones on the pile for player 2

Turn 4: player 2

Turn 5: leave 4 stones on the pile for player 2

Turn 6: player 2

Turn 7: removes all stones
Player 1 wins.

35
Adapting existing proofs
Often an existing proof can be adapted to
prove a new result.

Some of the ideas in existing proofs may be

helpful.

36
Adapting existing proofs (example)
If 3 is a factor of n2, then 3 is a factor of n.
Proof (proof by contradiction):
Assume 3 is a factor of n2 and 3 is not a factor of n.

a n2 = 3a

b n = 3b+1 or n=3b+2
Case 1: n=3b+1
n2 = (3b+1)2 = 9b2 + 6b + 1 = 3 (3b2 + 2b) + 1
Let k = 3b2 + 2b.
n2 = 3k + 1 So, 3 is not a factor of n2.
(Contradiction)

37
Adapting existing proofs (example)
If 3 is a factor of n2, then 3 is a factor of n.
Proof (proof by contradiction):
Assume 3 is a factor of n2 and 3 is not a factor of n.

a n2 = 3a

b n = 3b+1 or n=3b+2
Case 2: n=3b+2
n2 = (3b+2)2 = 9b2 + 12b + 4 = 3 (3b2 + 4b + 1) + 1
Let k = 3b2 + 4b + 1.
n2 = 3k + 1 So, 3 is not a factor of n2.
(Contradiction)

So, if 3 is a factor of n2, then 3 is a factor of n.

38
Adapting existing proofs (example)
Prove that 3 is irrational. Definition:
The real number r
Proof (proof by contradiction): is rational if r=p/q,

integers p and q
Assume 3 is rational.
that q
.

a,b 3 = a/b b
0
If a and b have common factor, remove it by dividing a and b
by it.
3 = a/b
3 = a2 / b2
3b2 = a2
So, 3 is factor of a2and by previous theorem, 3 is factor of n.

39
Adapting existing proofs (example)
Prove that 3 is irrational. Definition:
The real number r
Proof (proof by contradiction): is rational if r=p/q,

integers p and q
3b2 = a2
that q
.

k a = 3k.
3b2 = 9k2
b2 = 3k2
So, 3 is factor of b2 and by previous theorem, 3 is factor of b.

m b = 3m.
So, a and b have common factor 3 which contradicts the
Assumption.

40
Looking for counterexample

 Theorem proof

You might first try to prove theorem.

If your attempts are unsuccessful, try to find
counterexample.

41
Looking for counterexample
(example)
Every positive integer is the sum of the squares of three
integers.

Proof:

Try to find a counterexample
1 = 02 + 02 + 12
2 = 02 + 12 + 12
3 = 12 + 12 + 12
4 = 02 + 02 + 22
5 = 02 + 12 + 22
6 = 12 + 12 + 22
7=?
42
Looking for counterexample
(example)
Every positive integer is the sum of the squares of three
integers.

Proof:

Try to find a counterexample
7 is a counterexample.
Since squares less than 7 are 0, 1 and 4, 7 cannot be
written as a sum of three of these numbers.

43
Recommended exercises
3,5,7,9,13,15,20,21,28,32

Recommended book:
“How to read and do proofs”
by Daniel Solow

44