$$\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

[ "stage:draft", "article:topic", "license:ccbyncsa", "showtoc:yes" ]

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

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

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

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

Thus $$n^2$$ is even.

In this technique, we shall assume $$p$$ and   $$\not q$$  are true,  come to a contradiction.

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

​​​​​​​