Direct Proof: Contraposition
If you tried to prove but failed to produce a direct
proof of your conjecture P → Q
can use a variant of direct proof,
Q' → P' is the contra positive of P → Q
Example 1: Prove that “If the square of an integer
is odd, then the integer must be odd.”
P: n2 is odd, Q: n is odd
P → Q
Try to prove, Q' → P'
Q' : n is even, P' : n2 is even
n is even, n2 = n x n is even
Direct Proof: Contraposition
2: Prove that “If n+1 separate
passwords are issued to n students, then some
student gets ≥ 2 passwords.”
The contrapositive is:
• If every student gets < 2 passwords, then n+1 separate
passwords were NOT issued.”
every student has < 2 passwords
Then, every one of the n students has at most 1
total number of passwords issued is at most n,
Indirect Proof: Proof by Contradiction
from the definition of contradiction which says
P Λ Q' → 0
(P Λ Q'→0) → (P→ Q) is a tauto logy .
In a proof of contradiction, one as sumes that the
hypothesis and the negation of the conclusion are true
and then try to deduce some contradiction from these
Example 1: Prove that “If a number added to itself gives
itself, then the number is 0.”
The hypothesis (P) is x + x = x and the conclusion (Q) is x =
0. Hence, the hypotheses for the proof by contradiction are:
x + x = x and x ≠ 0 (the negation of the conclusion)
2x = x and x ≠ 0, hence dividing both sides by x, the
result is 2 = 1, which is a contradiction. Hence, (x + x = x)→
(x = 0).
Proof by Contradiction
Example 2: Prove “For all real numbers x and y, if x + y
2, then either x ≥ 1 or y ≥ 1.”
Proof: Say the conclusion is false, i.e. x < 1 and y < 1. (Note:
or becomes and in negation.)
Adding the two conditions , the result is x + y < 2.
this point, this condition is P‘ if P = x + y ≥ 2, hence, P Λ
P’ which is a contradiction. Hence, the statement above is
3: The sum of even integers is even.
Let x = 2m, y = 2n for integers m and n and assume
x + y is odd.
x + y = 2m + 2n = 2k + 1 for some integer k.
Hence, 2*(m + n - k) = 1, where m + n - k is some integer.
This is a contradiction since 1 is not even.
1. Assume that √5 is rational number, then √5 =b/a, 5 =
2. 5a2 = b2 ------- (1)
Section 2.1 Proof Techniques 12
3. b2 is a multiple of 5, 5 is a prime number, therefore b is a multiple of 5
4. If we let b=5k (k is integer) 5a2=25k2
5. a2 is a multiple of 5, 5 is a prime number, therefore a is a multiple of 5
7. This is a contradiction that a and b have no common factors 5
6. Now, 5 is factor of both a and b.
8.Therefore √5 is not rational.
Fortuitous happening or something by chance
or good luck.
a formal proof technique.
proofs provided by this method although other
methods can be used as well.
342 players in a tennis tournament. One winner
Section 2.1 Proof Techniques 13
in the end. Each match is between two players with
exactly one winner and the loser gets eliminated . Prove
the total number of matches played in the tournament are
341. Solution :
Only one champion at the end of the tournament,
hence 341 losers at the end, hence 341 matches should
have been played to have 341 losers.
Summarizing Proof techniques
Approach to prove P→
Demonstrate P→ Q
for all cases
May only be used for
finite number of cases
Assume P, deduce Q
approach- usually the
thing to try
Assume Q', derive P'
Use this Q' if as a
hypothesis seems to
give more ammunition
then P would
Assume P Λ Q', deduce
Use this when Q says
something is not true
Not really a proof
Fun to know
Class Exercise 1. Product of any 2 consecutive integers is even.
2. The sum of 3 consecutive integers is even.
3. Product of 3 consecutive integers is even.
4. The square of an odd integer equals 8k+1 for
some integer k.
5. The sum of two rational numbers is rational.
6. For some positive integer x, x + 1/x ≥ 2.