
0.2 Introduction to Proofs/Contradiction

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

In this section, we will explore different techniques of proving a mathematical statement "If $$p$$ then $$q$$". ($$p \to q$$).

Direct Proof

In this technique, we shall assume $$p$$ and show that $$q$$ is true.

Theorem $$\PageIndex{1}$$

Let $$n$$ be an integer. If $$n$$ is even then $$n^2$$ is even.

Proof

Assume that $$n$$ is even. Then $$n=2m$$ for some integer $$m$$.

Consider $$n^2=(2m)^2=4m^2=2(2m^2).$$ Since $$m$$ is an integer, $$(2m^2)$$ is an integer.

Thus $$n^2$$ is even.

Exercise $$\PageIndex{1}$$

Show that for all integers $$n$$, if $$n$$ is odd then $$n^2$$ is odd.

Assume that $$n$$ is odd. Then $$n=2m+1$$ for some integer $$m$$.

Consider $$n^2=(2m+1)^2=4m^2+4m+1=2(2m^2+2m)+1.$$

Since $$m$$ is an integer, $$(2m^2+2m)$$ is an integer.

Thus $$n^2$$ is odd.

Proof by Contrapositive

In this technique, we shall assume $$\not p$$ and show that $$\not q$$ is true.

Theorem $$\PageIndex{2}$$

Let $$n$$ be an integer. If $$n^2$$ 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 $$n^2=(2m+1)^2=4m^2+4m+1=2(2m^2+2m)+1.$$

Since $$m$$ is an integer, $$(2m^2)+2m$$ is an integer.

Thus $$n^2$$ is odd.

Exercise $$\PageIndex{2}$$

Show that for all integers $$n$$, if $$n^2$$ is odd then $$n$$ is odd.

We shall prove this statement by assuming $$n$$ is even. Then $$n=2m$$ for some integer $$m$$.

Consider $$n^2=(2m)^2=4m^2=2(2m^2).$$

Since $$m$$ is an integer, $$(2m^2)$$ is an integer. Thus $$n^2$$ is even.

In this technique, we shall assume the negation of the given statement is true, and come to a contradiction.

Theorem $$\PageIndex{3}$$

$$\sqrt{2}$$ is irrational.

Proof

Assume that $$\sqrt{2}$$ is rational. Then $$\sqrt{2}= \dfrac {a}{b}$$, where $$a \in \mathbb{Z}, b \in \mathbb{Z}\setminus \{0\}$$, with no common factors between $$a$$ and $$b$$. Now, $$\sqrt{2} a=b$$. Then $$2a^2=b^2$$. Since $$2$$ divides $$2a^2$$, $$2$$ divides $$b^2$$. Thus $$b^2$$ is even. Therefore, $$b$$ is even, (by theorem 2). Since $$b$$ is even, $$2$$ divides $$b$$. Therefore, $$2^2$$ divides $$b^2$$.

Since $$2a^2=b^2$$, $$2^2$$ divides $$2a^2$$. Therefore, $$2$$ divides $$a^2$$.  Which implies  $$a$$ is even.  This contradicts the fact that $$a$$ and $$b$$ have no common factors.  Thus $$\sqrt{2}$$ is irrational.

Proof by Counterexample

Example $$\PageIndex{1}$$:

Decide whether the statement is true or false and justify your answer:

For all integers $$a,b,u,v$$, and $$u\ne 0, v \ne 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\ne 0. b \ne 0, a \ne 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) \forall n \geq n_0, \, n, \, n_0 \in \mathbb{Z}$$ be a statement. We would show that p(n) is true for all possible values of n.

1. Show that p(n) is true for the smallest possible value of n: In our case $$p(n_0)$$. AND
2. For regular Induction: Assume that the statement is true for $$n = k,$$ for some integer $$k \geq n_0$$. 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 $$n_0 ≤ r ≤ k$$ for some $$k ≥ n_0$$. 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 \geq n_0.$$

Example $$\PageIndex{2}$$:

Prove that $$1 + 2 + ... + n = \displaystyle \frac{n(n + 1)}{2}, \, \forall n \in \mathbb{Z}$$.

Solution:

Base step: Choose $$n = 1$$. Then L.H.S =$$1$$. and R.H.S $$= \frac{(1)(1 + 1)}{2}=1$$

Induction Assumption: Assume that $$1 + 2 + ... +k= \displaystyle\frac{k(k + 1)}{2}$$ , for $$k \in \mathbb{Z}$$.

We shall show that $$1 + 2 + ... + k + (k + 1) = \displaystyle\frac{(k + 1)[(k + 1) + 1]}{2} = \frac{(k + 1)(k + 2)}{2}$$

Consider $$1 + 2 + ... + k + (k + 1)$$

$$= \displaystyle \frac{k(k + 1)}{2} + (k + 1)$$

$$= (k + 1) \left( \displaystyle\frac{k}{2} + \displaystyle\frac{1}{1}\right)$$

$$= (k + 1) \left( \displaystyle\frac{k + 2}{2}\right)$$

$$= \displaystyle \frac{(k + 1)(k + 2)}{2}$$.

Thus, by induction we have $$1 + 2 + ... + n = \displaystyle\frac{n(n + 1)}{2}, \, \forall n \in \mathbb{Z}$$.