Proofs, Recursion and Analysis of Algorithms

Direct Proof: Contraposition
If you tried to prove but failed to produce a direct
proof of your conjecture P → Q
You can use a variant of direct proof,
contraposition
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: n² is odd, Q: n is odd
Conjecture: P → Q
Try to prove, Q' → P'
Q' : n is even, P' : n² is even
Since n is even, n² = n x n is even
(n=2k, n²=4k²=2(2k²))

Direct Proof: Contraposition
Example 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.”
Suppose every student has < 2 passwords
Then, every one of the n students has at most 1
password.
The total number of passwords issued is at most n,
not n+1.

Indirect Proof: Proof by Contradiction
Derived from the definition of contradiction which says
P Λ Q' → 0
Hence, (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
assumptions.
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)
Then 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.
At this point, this condition is P‘ if P = x + y  ≥ 2, hence, P Λ
P’ which is a contradiction. Hence, the statement above is
true.
Example 3: The sum of even integers is even.
Proof: Let x = 2m, y = 2n for integers m and n and assume
that
x + y is odd.
Then 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.

Class Exercise
Prove that √5 is not a rational number .
What kind of proof method and How ?
Definition of rational number: a number that can be
re presented as a form of b/a (a,b, integers, a≠0, and a
and b have no common factors )

1. Assume that √5 is rational number, then √5 =b/a, 5 = b²/a²,
2. 5a² = b² ------- (1)
Section 2.1 Proof Techniques 12
3. b² 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) 5a²=25k² a²=5k²
5. a² 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.

Serendipity
Serendipity: Fortuitous happening or something by chance
or good luck.
Not a formal proof technique.
Interesting proofs provided by this method although other
methods can be used as well.
Example: 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

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.