# 0.0: Introduction to proofs

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

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.

Example $$\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 $$\neg p$$ and show that $$\neg 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.

Example$$\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{3}$$:

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.$$

### Mathematical Induction

Process of Proof by Induction

Let $$p(n)$$ be a mathematical statement, $$n \in \mathbb{N}$$ i.e., $$n \ge1$$.

1. Prove the statement is true for the lowest value of $$n$$.

2. Assume that $$p(n)$$ is true for all $$n=k$$.

3. Prove $$p(k+1)$$ is true.

##### Example $$\PageIndex{4}$$

Prove $$2^n>n+4$$ for $$n\ge 3, n\in \mathbb{N}$$.

Let $$n=3$$.  Then $$2^3 >3+4$$ is true since clearly $$8>7$$.  Thus the statement is true for $$n=3$$.

Assume that $$2^n > n+4$$ is true for some $$n=k$$.

We will show that $$2^{k+1} > (k+1)+4$$.

Consider $$2^{k+1}=2 \cdot 2^{k} >2 \cdot (k+4)=2k+8$$.

Since $$2k > k+1$$ and $$8 >4$$, we have $$2k+8>(k+1)+4$$.

Thus the statement is true for all $$n=k$$.

By induction, $$2^n > n+4$$ for all $$n\ge 3, n \in \mathbb{Z}$$.◻

##### Example $$\PageIndex{5}$$

Show that $$9|(10^{n+1}+3(10^n)+5), \forall n \ge 1$$.

Let $$n=1$$.  Then $$9|(10^2)+3(10)+5$$, which is $$9|135$$, which is true since $$135=9(15)$$ and $$15 \in \mathbb{Z}$$.

Assume that $$9|(10^{n+1}+3(10^n)+5$$ is true for some $$n=k$$.

We will show that $$10^{k+1+1}+3(10^{k+1})+5=9m$$ for some $$m \in \mathbb{Z}$$.

Consider $$10^{k+1+1}+3(10^{k+1})+5=10(10^{k+1}+3(10^k)+5)-9(5)$$

$$=10(9m)-9(5)$$

$$=9(10m-5)$$, where $$10m-5 \in \mathbb{Z}$$.

By induction, $$9|(10^{n+1}+3(10^n)+5), \forall n \ge 1$$.◻

##### Example $$\PageIndex{6}$$

Show that $$1+2+3+\cdots + n=\frac{n(n+1)}{2}, \; \forall \; n\ge 1$$.

Let $$n=1$$.  Then $$1=\frac{1(1+1)}{2}$$ which is true.

Assume $$1+2+3+\cdots + n=\frac{n(n+1)}{2}$$ is true for some $$n=k$$.

We will show that $$1+2+3+\cdots + n +(n+1)=\frac{(n+1)(n+1+1)}{2}$$

Consider $$1+2+3+\cdots +n+(n+1)=[1+2+3+\cdots+n]+(n+1)$$.

$$=\frac{n(n+1)}{2} +(n+1)$$

$$=\frac{n(n+1)+2(n+1)}{2}$$

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

By induction, $$1+2+3+\cdots + n=\frac{n(n+1)}{2}, \; \forall \; n\ge 1$$.◻

##### Example $$\PageIndex{7}$$

Prove that $$3|(10^{n+1}+10^n+1), \; \forall \; n\ge 1$$.

Let $$n=1$$.  Then $$3|(10^2+10+1)$$ is true since $$111=3(37)$$ and $$37 \in \mathbb{Z}$$.

Assume that $$3|(10^{n+1}+10^n+1)$$ for some $$n=k$$.

We will show that $$10^{k+1+1}+10^{k+1}+1=3m, m\in \mathbb{Z}$$.

Consider $$10^{k+1+1}+10^{k+1}+1=10(10^{k+1}+10^k+1)-9(1)$$

$$=10(3m)-3(3)$$

$$=3(10m-3)$$ where $$10m-3 \in \mathbb{Z}$$.

By induction, $$3|(10^{n+1}+10^n+1), \; \forall \; n\ge 1$$.◻

This page titled 0.0: Introduction to proofs is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.