0.2: Introduction to Proofs/Contradiction
( \newcommand{\kernel}{\mathrm{null}\,}\)
In this section, we will explore different techniques of proving a mathematical statement "If p then q." (p→q).
Direct Proof
In this technique, we shall assume p and show that q is true.
Theorem 0.2.1
Let n be an integer. If n is even then n2 is even.
- Proof
-
Assume that n is even. Then n=2m for some integer m.
Consider n2=(2m)2=4m2=2(2m2). Since m is an integer, (2m2) is an integer.
Thus n2 is even.
Example 0.2.1
Show that for all integers n, if n is odd then n2 is odd.
- Answer
-
Assume that n is odd. Then n=2m+1 for some integer m.
Consider n2=(2m+1)2=4m2+4m+1=2(2m2+2m)+1.
Since m is an integer, (2m2+2m) is an integer.
Thus n2 is odd.
Proof by Contrapositive
In this technique, we shall assume ¬p and show that ¬q is true.
Theorem 0.2.2
Let n be an integer. If n2 is even then n is even.
- Proof
-
We shall prove this statement by assuming n is odd. Then n=2m+1 for some integer m.
Consider n2=(2m+1)2=4m2+4m+1=2(2m2+2m)+1.
Since m is an integer, (2m2)+2m is an integer.
Thus n2 is odd.
Example 0.2.2
Show that for all integers n, if n2 is odd then n is odd.
- Answer
-
We shall prove this statement by assuming n is even. Then n=2m for some integer m.
Consider n2=(2m)2=4m2=2(2m2).
Since m is an integer, (2m2) is an integer. Thus n2 is even.
Proof by Contradiction
In this technique, we shall assume the negation of the given statement is true and come to a contradiction.
Theorem 0.2.3
√2 is irrational.
- Proof
-
Assume that √2 is rational. Then √2=ba, where b∈Z,a∈Z∖{0}, with no common factors between a and b. Now, √2a=b. Then 2a2=b2. Since 2 divides 2a2, 2 divides b2. Thus b2 is even. Therefore, b is even (by theorem 2). Since b is even, 2 divides b. Therefore, 22 divides b2.
Since 2a2=b2, 22 divides 2a2. Therefore, 2 divides a2. Which implies a is even. This contradicts the fact that a and b have no common factors. Thus √2 is irrational.
Proof by Counterexample
Example 0.2.3:
Decide whether the statement is true or false and justify your answer:
For all integers a,b,u,v, and u≠0,v≠0, if au+bv=0 then a=b=0.
Solution: The statement is false.
Counterexample: Choose a=1,b=−1,u=2,v=2, then au+bv=0, but a≠0.b≠0,a≠b.
Proof by induction
In mathematics, we use induction to prove mathematical statements involving integers. There are two types of induction: regular and strong. The steps start the same but vary at the end. Here are the steps. In mathematics, we start with a statement of our assumptions and intent:
Let p(n)∀n≥n0,n,n0∈Z be a statement. We would show that p(n) is true for all possible values of n.
- Show that p(n) is true for the smallest possible value of n: In our case p(n0). AND
- For Regular Induction: Assume that the statement is true for n=k, for some integer k≥n0. Show that the statement is true for n = k + 1.
OR
For Strong Induction: Assume that the statement p(r) is true for all integers r, where n0≤r≤k for some k≥n0. Show that p(k+1) is true.
If these steps are completed, and the statement holds, we are saying that, by mathematical induction, we can conclude that the statement is true for all values of n≥n0.
Example 0.2.4:
Prove that 1+2+...+n=n(n+1)2,∀n∈Z.
Solution:
Base step: Choose n=1. Then L.H.S =1 and R.H.S =(1)(1+1)2=1
Induction Assumption: Assume that 1+2+...+k=k(k+1)2, for k∈Z.
We shall show that 1+2+...+k+(k+1)=(k+1)[(k+1)+1]2=(k+1)(k+2)2
Consider, 1+2+...+k+(k+1)=k(k+1)2+(k+1)=(k+1)(k2+11)=(k+1)(k+22)=(k+1)(k+2)2.
Thus, by induction we have 1+2+...+n=n(n+1)2,∀n∈Z.