Methods of proof

METHODS OF PROOF
DIRECT PROOF
DISPROOF BY
COUNTER EXAMPLE

INTRODUCTION:
To understand written mathematics, one must understand what makes
up a correct mathematical argument, that is, a proof. This requires an understanding of the
techniques used to build proofs. The methods we will study for building proofs are also
used throughout computer science, such as the rules computers used to reason, the
techniques used to verify that programs are correct, etc.
Many theorems in mathematics are implications, p q. The techniques of proving
implications give rise to different methods of proofs.

METHODS OF PROOF

DIRECT PROOF INDIRECT PROOF

pq

PROOF BY PROOF BY

CONTRAPOSITION CONTRADICTION

p q ~q~p p q (p~q) c

DIRECT PROOF:
The implication p q can be proved by showing that if p is true, the
q must also be true. This shows that the combination p true and q false never occurs. A
proof of this kind is called a direct proof.
25-Mthods of Proof

p q pq
T T T
T F F
F T T
F F T

SOME BASICS:
1. An integer n is even if, and only if, n = 2k for some integer k.
2. An integer n is odd if, and only if, n = 2k + 1 for some integer k.
3. An integer n is prime if, and only if, n > 1 and for all positive integers r and s, if
n = rs, then r = 1 or s = 1.
4. An integer n > 1 is composite if, and only if, n = rs for some positive integers r
and s with r 1 and s 1.
a
5. A real number r is rational if, and only if,r= for some integers a and b with b0.
b
6. If n and d are integers and d 0, then d divides n, written d|n if, and only if, n = d.k
for some integers k.
7. An integer n is called a perfect square if, and only if, n = k2 for some integer k.
EXERCISE:
Prove that the sum of two odd integers is even.
SOLUTION:
Let m and n be two odd integers. Then by definition of odd numbers
m = 2k + 1 for some k Z
n = 2l + 1 for some l Z
Now m + n = (2k + 1) + (2l + 1)
= 2k + 2l + 2
= 2 (k + l + 1)
= 2r where r = (k + l + 1) Z
Hence m + n is even.
EXERCISE:
Prove that if n is any even integer, then (-1)n = 1
SOLUTION:
Suppose n is an even integer. Then n = 2k for some integer k.
Now
(-1) n= (-1)2k
= [(-1)2]k
= (1)k
=1 (proved)
EXERCISE:
Prove that the product of an even integer and an odd integer is even.
SOLUTION:
Suppose m is an even integer and n is an odd integer. Then
m = 2k for some integer k
and n = 2l + 1 for some integer l
Now
mn = 2k (2l + 1)
= 2k (2l + 1)
25-Mthods of Proof

= 2r where r = k(2l + 1) is an integer

Hence mn is even. (Proved)

EXERCISE:
Prove that the square of an even integer is even.
SOLUTION:
Suppose n is an even integer. Then n = 2k
Now
square of n = n2= (2k)2
= 4k2
= 2(2k2)
= 2p where p = 2k2 Z
2
Hence, n is even. (proved)
EXERCISE:
Prove that if n is an odd integer, then n3 + n is even.
SOLUTION:
Let n be an odd integer, then n = 2k + 1for some k Z
Now n3 + n = n (n2 + 1)
= (2k + 1) ((2k+1)2 + 1)
= (2k + 1) (4k2 + 4k + 1 + 1)
= (2k + 1) (4k2 + 4k + 2)
= (2k + 1) 2. (2k2 + 2k + 1)
= 2(2k + 1) (2k2 + 2k + 1) k Z
= an even integer
EXERCISE:
Prove that, if the sum of any two integers is even, then so is their difference.
SOLUTION:
Suppose m and n are integers so that m + n is even. Then by definition of
even numbers
m + n = 2k for some integer k
m = 2k - n .(1)
Now m - n = (2k - n) - n using (1)
= 2k - 2n
= 2 (k - n) = 2r where r = k - n is an integer
Hence m - n is even.
EXERCISE:
Prove that the sum of any two rational numbers is rational.
SOLUTION:
Suppose r and s are rational numbers.
Then by definition of rational
a c
r and s
b d
for some integers a, b, c, d with b0 and d0
a c
Now rs
b d
ad bc

bd
p

q
25-Mthods of Proof

where p = ad + bc Z and q =bd Z

and q 0
Hence r + s is rational.

EXERCISE:
Given any two distinct rational numbers r and s with r < s. Prove that there is
a rational number x such that r < x < s.
SOLUTION:
Given two distinct rational numbers r and s such that
r<s .(1)
Adding r to both sides of (1), we get
r+r<r+s
2r < r + s
rs
r .(2)
2
Next adding s to both sides of (1), we get
r+s<s+s
r + s < 2s

rs (3)
s
2

Combining (2) and (3), we may write

rs
r s ..(4)
2
Since the sum of two rationals is rational, therefore r + s is rational. Also the quotient of
a rational by a non-zero rational, is rational, therefore r s is rational and by (4) it lies
between r & s. 2
Hence, we have found a rational number
such that r < x < s. (proved)
EXERCISE:
Prove that for all integers a, b and c, if a|b and b|c then a|c.
PROOF:
Suppose a|b and b|c where a, b, c Z. Then by definition of divisibility
b=ar and c=bs for some integers r and s.
Now c = bs
= (ar)s (substituting value of b)
= a(rs) (associative law)
= ak where k = rs Z
a|c by definition of divisibility
EXERCISE:
Prove that for all integers a, b and c if a|b and a|c then a|(b+c)
PROOF:
Suppose a|b and a|c where a, b, c Z
By definition of divides
b = ar and c = as for some r, s Z
25-Mthods of Proof

Now
b + c= ar + as (substituting values)
= a(r+s) (by distributive law)
= ak where k = (r + s) Z
Hence a|(b + c) by definition of divides.

EXERCISE:
Prove that the sum of any three consecutive integers is divisible by 3.
PROOF:
Let n, n + 1 and n + 2 be three consecutive integers.
Now
n + (n + 1) + (n + 2)= 3n + 3
= 3(n + 1)
= 3k where k=(n+1)Z
Hence, the sum of three consecutive integers is divisible by 3.
EXERCISE:
Prove the statement:
There is an integer n > 5 such that 2n - 1 is prime
PROOF:
Here we are asked to show a single integer for which 2n -1is prime. First of all
we will check the integers from 1 and check whether the answer is prime or not by
putting these values in 2n-1.when we got the answer is prime then we will stop our
process of checking the integers and we note that,
Let n = 7, then
2n - 1 = 27 - 1 = 128 - 1 = 127
and we know that 127 is prime.
EXERCISE:
Prove the statement: There are real numbers a and b such that
ab a b
PROOF:
Let ab a b

Squaring,we get a + b = a + b + 2 a b
0 =2 a b canceling a+b

0 = ab
0 = ab squaring
either a = 0 or b = 0
It means that if we want to find out the integers which satisfy the given condition then
one of them must be zero.
Hence if we let a = 0 and b = 3 then
R.H .S a b 0 3
R.H .S 3
Now L.H .S a b by putting the values of a and b we get
0 3
L.H .S 3
25-Mthods of Proof

From above it quite clear that the given condition is satisfied if we take a=0 and b=3.
PROOF BY COUNTER EXAMPLE:
Disprove the statement by giving a counter example.
For all real numbers a and b, if a < b then a 2 < b2.
SOLUTION:
Suppose a = -5 and b = -2
then clearly - 5 < - 2
But a = (-5) = 25 and b2 = (-2)2 = 4
2 2

But 25 > 4
This disproves the given statement.
EXERCISE:
Prove or give counter example to disprove the statement.
For all integers n, n2 - n + 11 is a prime number.
SOLUTION:
The statement is not true
For n = 11
we have , n2 - n + 11= (11) 2 - 11 + 11
= (11) 2
= (11) (11)
=121
which is obviously not a prime number.

EXERCISE:
Prove or disprove that the product of any two irrational numbers is an irrational number.

SOLUTION:
We know that 2 is an irrational number. Now

2
( 2 )( 2 ) ( 2 ) 2 2
1

which is a rational number. Hence the statement is disproved.

EXERCISE:
Find a counter example to the proposition:
For every prime number n, n + 2 is prime.

SOLUTION:
Let the prime number n be 7 then
n+2=7+2=9
which is not prime.
26-Proof by contradiction

Lecture No.1 Proof by contradiction

PROOF BY CONTRADICTION:
A proof by contradiction is based on the fact that either a statement is true or it is false but
not both. Hence the supposition, that the statement to be proved is false, leads logically to
a contradiction, impossibility or absurdity, then the supposition must be false.
Accordingly, the given statement must be true.
This method of proof is also known as reductio ad absurdum because it relies on reducing
a given assumption to an absurdity.
Many theorems in mathematics are conditional statements (pq). Now the negation of he
implication pq is
~(pq) ~(~pq)
~(~p) (~q) DeMorgans Law
p ~q
Clearly if the implication is true, then its negation must be false, i.e., leads to a
contradiction.
Hence pq (p ~q) c
where c is a contradiction.
Thus to prove an implication pq by contradiction method we suppose that the condition
p and the negation of the conclusion q, i.e., (p ~q) is true and ultimately arrive at a
contradiction.
The method of proof by contradiction, may be summarized as follows:
1. Suppose the statement to be proved is false.
2. Show that this supposition leads logically to a contradiction.
3. Conclude that the statement to be proved is true.

THEOREM:
There is no greatest integer.
PROOF:
Suppose there is a greatest integer N. Then n N for every integer n.
Let M=N+1
Now M is an integer since it is a sum of integers.
Also M > N since M = N + 1
Thus M is an integer that is greater than the greatest integer, which is a contradiction.
Hence our supposition is not true and so there is no greatest integer.

EXERCISE:
Give a proof by contradiction for the statement:
2
If n is an even integer then n is an even integer.

PROOF:
Suppose n2 is an even integer and n is not even, so that n is odd.
Hence n = 2k + 1 for some integer k.
2 2
Now n = (2k + 1)
= 4k2 + 4k + 1
= 2(2k2 + 2k) + 1
= 2r + 1 where r = (2k2 + 2k) Z
26-Proof by contradiction

This shows that n2 is odd, which is a contradiction to our supposition that n2 is even.
Hence the given statement is true.

EXERCISE:
Prove that if n is an integer and n3 + 5 is odd, then n is even using
contradiction method.

SOLUTION:
Suppose that n3 + 5 is odd and n is not even (odd). Since n is odd and the
product of two odd numbers is odd, it follows that n2 is odd and n3 = n2. n is odd. Further,
since the difference of two odd number is even, it follows that
5 = (n3 + 5) - n3
is even. But this is a contradiction. Therefore, the supposition that n3 + 5 and n are both
odd is wrong and so the given statement is true.

EXERCISE:
Prove by contradiction method, the statement: If n and m are odd integers,
then n + m is an even integer.

SOLUTION:
Suppose n and m are odd and n + m is not even (odd i.e by taking
contradiction).
Now n = 2p + 1 for some integer p
and m = 2q + 1 for some integer q
Hence n + m = (2p + 1) + (2q + 1)
= 2p + 2q + 2 = 2 (p + q + 1)
which is even, contradicting the assumption that n + m is odd.

THEOREM:
The sum of any rational number and any irrational number is irrational.

PROOF:
We suppose that the negation of the statement is true. That is, we suppose that there is a
rational number r and an irrational number s such that r + s is rational. By definition of
ration

a
r
b
(1)
and

(2)
c
rs
d

for some integers a, b, c and d with b 0 and d 0.

Using (1) in (2), we get
26-Proof by contradiction

a c
s
b d
c a
s
d b
bc ad
s (bd 0)
bd

Now bc - ad and bd are both integers, since products and difference of integers are
integers. Hence s is a quotient of two integers bc-ad and bd with bd 0. So by definition
of rational, s is rational.
This contradicts the supposition that s is irrational. Hence the supposition is false and the
theorem is true.

EXERCISE:
Prove that 2 is irrational.
PROOF:
Suppose 2
is rational. Then there are integers m and n with no common factors so that
m
2
n
Squaring both sides gives

m2
2
n2

Or m2 = 2n2 (1)
2
This implies that m is even (by definition of even). It follows that m is even. Hence
m=2k for some integer k (2)
Substituting (2) in (1), we get
(2k)2 = 2n2
4k2 = 2n2
n2 = 2k2
This implies that n2 is even, and so n is even. But we also know that m is even. Hence
both m and n have a common factor 2. But this contradicts the supposition that m and n
have no common factors. Hence our supposition is false and so the theorem is true.
Substituting (2) in (1), we get
(2k)2 = 2n2
4k2 = 2n2
n2 = 2k2
2
This implies that n is even, and so n is even. But we also know that m is even. Hence
both m and n have a common factor 2. But this contradicts the supposition that m and n
have no common factors. Hence our supposition is false and so the theorem is true.

EXERCISE:
26-Proof by contradiction

Prove by contradiction that 6 7 2 is irrational.

PROOF:
Suppose 6 7 2 is rational.
Then by definition of rational,
a
67 2
b
for some integers a and b with b0.
Now consider,
a
7 2 6
b
6b a
7 2
b
6b a
2
7b
Since a and b are integers, so are 6b-a and 7b and 7b0;
hence 2 is a quotient of the two integers 6b-a and 7b with 7b0.
Accordingly, 2 is rational (by definition of rational).
This contradicts the fact because 2 is irrational.
Hence our supposition is false and so 6 7 2 is irrational.

EXERCISE:
Prove that 2 + 3 is irrational.

SOLUTION:
Suppose 2 + 3 is rational. Then, by definition of rational, there exists
integers a and b with b0 such that
a
2 3
b

Squaring both sides, we get

a2
23 2 2 3 2
b
a2
2 23 2 5
b
a 2 5b 2
2 6
b2
a 2 5b 2
6
2b 2
26-Proof by contradiction

Since a and b are integers, so are therefore a2 - 5b2 and 2b2 with 2b20. Hence 6 is the
quotient of two integers a2 - 2b2 and 2b2 with 220. Accordingly, 6 is rational. But this
is a contradiction, since 6 is not rational. Hence our supposition is false and so
2 + 3 is irrational.

REMARK:
The sum of two irrational numbers need not be irrational in general for

(6 7 2 ) (6 7 2 ) 6 6 12
which is rational.

EXERCISE:
Prove that for any integer a and any prime number p, if p|a, then
P (a + 1).

PROOF:
Suppose there exists an integer a and a prime number p such that p|a and p|(a+1).
Then by definition of divisibility there exist integer r and s so that
a = pr and a + 1 = ps
It follows that
1 = (a + 1) - a
= ps - pr
= p(s-r) where s r Z
This implies p|1.
But the only integer divisors of 1 are 1 and -1 and since p is prime p>1. This is a
contradiction.
Hence the supposition is false, and the given statement is true.

PROOF BY CONTRAPOSITION:
A proof by contraposition is based on the logical equivalence between a statement and its
contrapositive. Therefore, the implication p q can be proved by showing that its
contrapositive ~ q ~ p is true. The contrapositive is usually proved directly.
The method of proof by contrapositive may be summarized as:
1. Express the statement in the form if p then q.
2. Rewrite this statement in the contrapositive form
if not q then not p.
3. Prove the contrapositive by a direct proof.
EXERCISE:
Prove that for all integers n, if n2 is even then n is even.
26-Proof by contradiction

PROOF:
The contrapositive of the given statement is:
if n is not even (odd) then n2 is not even (odd)
We prove this contrapositive statement directly.
Suppose n is odd. Then n = 2k + 1 for some k Z
Now n2 = (2k+1) 2= 4k2 + 4k + 1
= 2(2k2 + 2k) + 1
= 2r + 1 where r = 2k2 + 2k Z
Hence n2 is odd. Thus the contrapositive statement is true and so the given statement is
true.
EXERCISE:
Prove that if 3n + 2 is odd, then n is odd.
PROOF:
The contrapositive of the given conditional statement is
if n is even then 3n + 2 is even
Suppose n is even, then
n = 2k for some k Z
Now 3n + 2 = 3 (2k) + 2
= 2. (3k + 1)
= 2.r where r = (3k + 1) Z
Hence 3n + 2 is even. We conclude that the given statement is true since its contrapositive
is true.
EXERCISE:
Prove that if n is an integer and n3 + 5 is odd, then n is even.
PROOF:
Suppose n is an odd integer. Since, a product of two odd integers is odd,
therefore n2 = n.n is odd; and n3 = n2.n is odd.
Since a sum of two odd integers is even therefore n2 + 5 is even.
Thus we have prove that if n is odd then n3 + 5 is even.
Since this is the contrapositive of the given conditional statement, so the given statement
is true.
EXERCISE:
Prove that if n2 is not divisible by 25, then n is not divisible by 5.

SOLUTION:
The contra positive statement is:
if n is divisible by 5, then n2 is divisible by 25
Suppose n is divisible by 5. Then by definition of divisibility
n = 5k for some integer k
Squaring both sides
n2 = 25k2 where k2 Z
n2 is divisible by 25
.
EXERCISE:
Prove that if |x| > 1 then x > 1 or x < -1 for all x R.
PROOF:
The contrapositive statement is:
if x 1 and x-1 then |x| 1 for x R.
26-Proof by contradiction

Suppose that x 1 and x -1

x 1 and x -1
-1 x 1
and so
|x| 1
Equivalently |x| > 1

EXERCISE:
Prove the statement by contraposition:
For all integers m and n, if m + n is even then m and n are both even or m and n are both
odd.
PROOF:
The contrapositive statement is:
For all integers m and n, if m and n are not both even and m and n are not both odd, then
m + n is not even.
Or more simply,
For all integers m and n, if one of m and n is even and the other is odd, then m + n is
odd
Suppose m is even and n is odd. Then
m = 2p for some integer p
and n = 2q + 1 for some integer q
Now m + n = (2p) + (2q + 1)
= 2(p+q) + 1
= 2r + 1 where r = p+q is an integer
Hence m + n is odd.
Similarly, taking m as odd and n even, we again arrive at the result that m + n is odd.
Thus, the contrapositive statement is true. Since an implication is logically equivalent to
its contrapositive so the given implication is true.
27-Algorithm