Chapter 2:

Proof Techniques
Prepared by:
Er.Sharad Neupane
Associate Professor,KEC
Kalimati,Kathmandu
Proof:
A proof is a valid argument that establishes the truth of a mathematical statement.
Formal Proof(Imp):
A formal proof is based simply on symbol manipulation (no need of thinking, just apply
rules).Example of formal proof include rules of inference to build arguments.
Informal Proofs (Imp):
• Proofs where steps are not expressed in any formal language and more than one inference rule
may be used at each step,where steps may be skipped, and where axioms(postulates that we
assume to be true) and inference rules used are not explicitly stated.
Direct Proof(Imp)
Let p→q be any conditional statement then its direct proof is given by:
We assume that p to be true and we show that q is true
Q)Show that the statement “If n is odd then n² is odd” by using direct proof method.
(Note: Any integer n is said to be even if there exist an another integer k such that
n=2k and is odd if n=2k+1)
Let p:n is odd.
q: n² is odd.
Let p be true i.e. n is odd is true
Then from the definition of odd integer
n=2k+1 for some integer k………(i)
Now we have to show that q is true i.e. n² is odd.
We have n=2k+1 from (i)
Squaring on both sides
n² =(2k+1)²
=4k²+4k+1
=2(2k²+2k)+1 which is odd as it is in the form 2k+1
Here q is true when p is true so the given conditional statement is true by direct
proof method.
Q)If m and n are both perfect squares then mn is also perfect square. Prove this
statement by using direct proof method.
(Note: Any integer ‘a’ is said to be a perfect square if there exist an another integer
‘b’ such that a=b²).
Let p: m and n are both perfect squares
q: mn is a perfect square.
Assume p is true i.e. m and n are both perfect square.
From definition of perfect square
m=a²………(i)
n=b²……….(ii)
For some integer a and b.
Now we have to show that q is true i.e.mn is a perfect square.
Multiplying equations (i) and (ii) we qet
mn=a²b²
=(ab)²
Here mn is a perfect square as it is in the form a=b².Here q is true when p is true so the
given conditional is true by direct proof method.
Indirect Proof(Imp):
The proof of the statement where we do not start with hypothesis and end up to the
conclusion is called indirect proof.
1.Proof by contrapositive or contraposition
2.Proof by contradiction
1.Proof by contrapositive or contraposition:
It uses the fact that the conditional statement is equivalent to its
contrapositive(p→q ≡ ┐q→ ┐p).Here first we assume that ┐q to be true and we
show that ┐p is true.
Q.If n is an integer and 3n+2 is odd then n is odd. Prove this using proof by
contraposition.
Let p: n is an integer and 3n+2 is odd
q: n is odd.
Let ┐q is true i.e. n is not odd which implies n is even
From the definition of even integer we have
n=2k for some integer k
Now we have to show that ┐p is true i.e. 3n+2 is not odd which implies it is even.
Solving for 3n+2
3n+2=3×2k+2
=6K+2
=2(3K+1) which is even i.e.3n+2 is not odd.
Here ┐p is true when ┐q is true so the statement (┐q→ ┐p) is true which means
(p→q) is true by the method of proof by contrapositive.
Q.)Prove that if n=ab where a and b are positive integer then a ≤ √n or b ≤ √n by the method of
proof by contraposition.
Let p:n=ab
q: a ≤ √n or b ≤ √n
Let ¬q is true i.e. ¬(a ≤ √n or b ≤ √n) is true
= ¬(a ≤ √n ˅ b ≤ √n)
= ¬(a ≤ √n) ∧ ¬(b ≤ √n)
= (a > √n) ∧ (b > √n) is true which implies both (a > √n)………(i) and (b>
√n)……….(ii) are separately true.
Now we have to show that ¬p is true i.e. n ≠ab.
Multiplying equation (i) and (ii) we get ab > √n×√n implies ab > n that is n ≠ab which implies ¬p
is true.
Here ¬p is true when ¬q is true so (┐q→┐p) is true which means (p →q)
is true i.e. the given conditional statement is true by the method of proof by contraposition or
contrapositive.
2.Proof by contradiction(Imp):
a)Proof by contradiction of the propositional statement.
Steps:
First denote the given propositional statement by propositional variable say p
We assume that negation of p to be true
By using various definitions ,already proven theorems, axioms etc. we show that
negation of p is false.
Finally we say that our assumption that negation of p which is true seems to be
false which is a contradiction to our assumption. So, the given original statement
is true.
Q) Prove that √2 is irrational by giving a proof by contradiction.
(Note: Any integer ‘r’ is said to be rational if it can be expressed in the form r=a/b
where b ≠0,a and b do not have a common factor, a and b are both integer)
Let p: √2 is irrational
Let ¬p is true i.e. √2 is not irrational which implies √2 is rational.
From the definition of rational number,
√2=a/b where b ≠0,a and b do not have common factor, a and b are both integers.
or, √2b=a
squaring on both the sides we get
a²=2b²……….(i)
Here we see that a² is even as it is in the from n=2k.This implies that a is also even. Thus ‘a’ can
be expressed as
a=2k for some integer k.
Now substituting the value of a=2k in equation (i) we get
(2k)²=2b²
or,4k²=2b²
or,2k²=b²
or,b²=2k²
Here b² is even since it is in the from n=2k.This implies that ‘b’ is also even.
Thus b can be expressed as b=2l for some integer ‘l’.
Finally we have ,
√2=a/b=2k/2l………….(ii)
From above relation (ii) we see that both a and b have a common factor 2 which is a
contradiction that both a and b do not have a common factor. So our assumption that
“√2 is rational” is wrong so the given original statement is true i.e. √2 is irrational.
b)Proof by contradiction of conditional statement:
Let p→q be any conditional statement then proof by contradiction of this conditional statement is
given by:
We assume that p and ¬q are true. After this using various definitions, already proven theorems
axioms etc. we conclude that p is not true taking ¬q as reference. This is the contradiction to our
assumption that p is true.so we finally conclude that our assumption is wrong so given original
conditional statement is true.
Q)Prove that “if 3n+2 is odd then n is odd” by the method of proof by contradiction.
Let p: 3n+2 is odd.
q: n is odd..
Let p is true i.e.3n+2 is odd and let ¬q is true i.e. n is not odd which implies n is even.
If n is even then from the definition of even integer
n=2k for some integer k.
Now solving for 3n+2 we get 3×2k+2=6k+2=2(3k+1) which is even implies it is not odd.
Here our assumption that p is true is wrong i.e. p is not true. Hence the given conditional
statement is true by the method of proof by contradiction
 Vacuous and Trivial proof:

p q p→q p q p→q
T T T T T T
T F F T F F
F T T F T T
F F T F F T

Figure 1:Vacuous Proof Figure 2:Trivial Proof

Vacuous Proof:
The conditional statement p→q is true when p is false no matter what the truth value of q
is.So,if we can show that p part as false then we can have proof called vacuous proof of
the conditional statement p→q. i.e. we can say that the given conditional statement is true
by vacuous proof method.
Q)Show that the proposition P(0) is true where the domain consists of the integer numbers
and P(n) is “If n ≥ 1 then n² > n.”
[Note: vacuous proof: when p is false p→ q is true, regardless of the value of q]
Here,P(n):“If n ≥ 1 then n² > n.”
P(n): p→ q
where, p denote n ≥ 1 and q denote n² > n.
 Now P(0) can be be obtained by substituting n=0 in P(n).
Thus P(0): “If 0 ≥ 1 then 0² > 0.”
Here, p part in P(0) i.e. 0≥ 1 is false so we can say that P(0) i.e. p→ q is true by vacuous proof
method.
Trivial Proof:
The conditional statement p→q is true when q is true no matter what the truth value of p is. So, if
we can show q part as true then we can have proof called trivial proof of the conditional statement
p→q. i.e. we can say that the given conditional statement is true by trivial proof method.
Q)Let P(n) be “If a and b are positive integers with a ≥ b, then an
≥ bn, where the domain consists of all integers. Show that P(0) is true.
The proposition P(0) is “If a ≥ b, then a0 ≥ b0 ”.
Because a0 = b0 =1, the conclusion of the given conditional statement is true. Hence we can say
that P(0) is true by trivial proof method as q part is true no matter what the truth value of p part is.
Proof by equivalence(Imp):
To prove the statement of the form p ↔ q, we show that both p → q and q → p are true i.e. to give
the proof ot the biconditional statement(statement of the form p iff q).It uses the fact that (p ↔ q)
≡ (p → q) ∧ (q → p)
Q)Prove that if n is a positive integer, then n is odd if and only if n² is odd.
Let p: n is a positive integer, then n is odd.
q: n² is odd.
The given statement is in the form p iff q i.e. (p ↔ q).Now to prove this statement we use the fact
that ,(p ↔ q) ≡ (p → q) ∧ (q → p).
We have to show that (p → q) and (q → p) both are true then only
(p ↔ q) will be true.
First consider (p → q). To prove this conditional statement as true we use direct proof method.
Let p be true i.e. n is odd is true,
From the definition of odd integer,
n=2k+1 for some integer k……………….(i)
We have to show that q part is true i.e. n² is odd.
Now squaring on both sides of (i)
n²=(2k+1)²
=4k²+4k+1
=2(2k²+2k)+1
Thus q is true i.e.n² is odd as it is in the form 2k+1.
Here q is true when p is true so the given conditional statement i.e. (p → q) is true by direct proof
method.
Again consider the statement (q → p).To show this statement true we use the method of proof by
contraposition .
(q → p) ≡ ┐p →┐q
Let ┐p be true i.e.n is not odd which implies n is even.
From the definition of even integer we can write
n=2k for some integer k………(i)
Now we show that ┐q is true i.e. n² is not odd which implies n² is even.
Squaring equation (i) we get
n²=(2k)²
=4k²
=2(2k²) which is even as it is in the form 2k
This shows that ┐q is true when ┐p is true so the statement ┐p →┐q is true that means (q
→ p) is true.
Here both (p→ q) and (q → p) are true so the given biconditional statement is true by the
method of proof by equivalence.
Note: Propositional statements p1,p2,……….. pn are equivalent means that (p1 → p2) and
(p2 →p3) and……..(pn →p1) should all be true.
Q)Show that these statements about integer n are equivalent.
p1: n is even
p2: n-1 is odd
p3: n² is even
Here we have to show that (p1 → p2), (p2 → p3) and (p3 → p1) are all true.
First consider the statement (p1 → p2) i.e. if n is even then n-1 is odd.
Let p1 is true i.e. n is even is true.
From the definition of even integer
n=2k for some integer k…………..(i)
Now we show that p2 is true i.e. n-1 is odd.
Subtracting 1 from both sides of equation (i)
n-1=2k-1
=2k-2+1
=2(k-1)+1 is odd as it is in the form 2k+1
Here p2 is true when p1 is true so (p1 → p2) is true by direct proof method.
Again consider the statement (p2 → p3) i.e. If n-1 is odd then n² is even.
Let p2 is true i.e. n-1 is odd
From the definition of odd integer,
n-1=2k+1 for some integer k.....................(ii)
Now we have to show that p3 is true i.e. n² is even
From equation (ii)
n=2k+2
Squaring on both sides
n²=(2k+2)²
=4k²+8k+4
=2(2k²+4k+2) which is even as it is in the form 2k
Here p3 is true when p2 is true so (p2 → p3) is true by direct proof method.
Again consider the statement (p3 → p1) i.e. if n² is even then n is even.For this we go for proof by
contraposition as (p3 → p1) ≡ (┐p1 →┐p3)
Let ┐p1 is true i.e.n is not even implies that n is odd
From the definition of odd integer,
n=2k+1 for some integer k………………(iii)
Now we have to show that ┐p3 is true i.e. n² is not even implies n² is
odd.
Squaring on both sides of equation (iii)
n²=(2k+1)²
=4k² +4k+1
=2(2k²+2k)+1 which is odd as it is in the form 2k+1
Here ┐p3 is true when ┐p1 is true so (┐p1 →┐p3) is true which means (p3 → p1) is true.
Here all the statements (p1 → p2), (p2 → p3) and (p3 → p1) are all true so statements p1,p2 and
p3 are equivalent.
Proof by Mathematical Induction(Imp):
Principle of weak (elementary) and strong(complete) induction(Imp):
In weak induction, we test the base case putting n=0 or 1
and assume that particular statement is true for kth step however in strong induction
we assume that the particular statement holds true from all the steps from base case
to kth step. The difference is that in weak induction we assume that the particular
statement holds true for the kth step and we show it holds true for (k+1)th step
however in strong induction we assume that any particular statement holds true from
base case to kth step and we show that it holds true for (k+1)th step.
Mathematical induction is a means of proving theorem by showing that if it is true
for any particular case then it is true for the next case in a series.
Suppose that we have some statement say p(n) and we want to demonstrate that
p(n) is true for all positive integer n.To prove that p(n) is true for all positive
integer n where p(n) is a propositional function then we perform the following
steps:
1) Basis step(base case):
We verify that p(0) or p(1) is true
2) Inductive step:
We assume that p(k) holds true for any arbitrary integer ‘k’ and show that p(k+1)
holds true.
Q) Use mathematical induction to show that 1+2+22+…….+2n=2n+1-1 where n is a positive
integer.
Let p(n):1+2+22+…….+2n=2n+1-1
Basis step(Base case):
For n=1, p(1):1+21=21+1-1=>3=3 which is true therefore p(1) holds true.
Inductive step:
Let p(k) holds true for any arbitrary positive integer ‘k’.i.e p(k):1+2+22+…….+2k=2k+1-1…… (i)
is true
Now we show that p(k+1) holds true.i.e. p(k+1): 1+2+22+…….+2k+1=2k+1+1-1 is true.
L.H.S=1+2+22+…….+2k+1
=1+2+22+……+2k +2k+1

=2k+1-1+2k+1 [From equation (i)]

=2. 2k+1-1
=2k+1+1-1
=R.H.S
Here, p (k+1) holds true whenever p(k) holds true so the given statement
1+2+22+…….+2n=2n+1-1 is true where n is positive integer.
Q) Show that n< 2n for all positive integer n by using mathematical induction.
Let p(n): n< 2n where n is the positive integer.
Basic step:
For n=1,p(1):1< 21 =>1<2 which is true
Inductive Step:
Let p(k) holds true for any arbitrary positive integer ‘k’.i.e.k< 2k is
true………….(i)
Now we have to show that p(k+1) holds true i.e. k+1<2k+1
We have,k+1<2k+1 =>k+1<2k * 21 ………….. (ii)
Since we have k < 2k from equation (i) so we can conclude that from above
relation (ii) the term k+1 will be always less than the term 2k * 2.

Here p(k+1) holds true whenever p(k) holds true so, the given mathematical
statement i.e. n<2n where n is the positive integer is true.
Q) Prove that n3-n is divisible by 3 whenever n is a positive integer.
Let p(n): n3-n is divisible by 3 whenever n is a positive integer.
Basis step:
p(1):13-1 is divisible by 3 true i.e. 0 is divisible by 3 which is true.
Inductive step:
Let p(k) holds true i.e.k3-k is divisible by 3 is true………(i)
Now we have to show that p(k+1) holds true i.e.(k+1)3-(k+1) is divisible by 3.
(k+1)3-(k+1) = (k3+1+3k2+3k)-k-1
=k3+3k2+3k-k
=3k2+3k+k3-k
=3(k2+k)+( k3-k)
Here (k3-k) is divisible by 3 from (i) and 3(k2+k) is also divisible by 3 so their sum
is also divisible by 3.
Here p(k+1) holds true whenever p(k) holds true so the given mathematical
statement is true.i.e. n3-n is divisible by 3 whenever n is a positive integer.
Proof by cases:
A proof by cases must covered all possible cases that arise in a theorem i.e. one
should check that all possible cases are covered.
Example:
Prove that if n is an integer then n2 + 3n+2 is even using proof by cases.
Solution:
Here possible cases are that n is an odd integer and n is an even integer.
Case 1:n is an odd integer
If n is an odd integer then from the definition of odd integer we can write n=2k+1
for some integer ‘k’.
We have to show that n2 + 3n+2 is even.
Now substituting n=2k+1 we get
(2k+1) 2+3(2k+1)+2
=4k2 +4k+1+6k+3+
= 4k2 +10k+6
=2(2k2 +5k+3) which is even since it is in the form n=2k
Case 2: n is an even integer
If n is an even integer then from the definition of even integer we can write n=2k for some
integer ‘k’.
We have to show that n2 + 3n+2 is even.
Now substituting n=2k we get
(2k) 2+3(2k)+2
=4k 2+6k+2
=2(2k 2+3k+1) which is even since it is in the form n=2k
Since in both the cases the result is even hence n2 + 3n+2 is even
if n is an integer.
Mistakes in proof:
There are many common error made in constructing mathematical proof. Among
them most common error is mistake made in arithmetic and basic algebra.
Let us consider the statement: If n2 is positive then n is positive
We know for all n if n is a positive integer then n2 is positive.
However, if n2 is positive then n is not positive. For this let us take the value of n=-2
n2 =(-2)2 =4 which is positive but -2 is not positive. So from n2 is positive we
cannot conclude that n is positive.