# Proof by Deduction

## Idea

Proof by deduction is the most common form of proof. In it, an argument is constructed in which each statement follows logically from the previous ones.

## Examples

###### Example

For all $n \in \mathbb{N}$, $n^2 - 2n + 2$ is positive.

###### Proof

Let $n \in \mathbb{N}$, then:

\begin{aligned} n^2 - 2n + 2 &= (n - 1)^2 - 1 + 2 \\ &= (n-1)^2 + 1 \end{aligned}

Since $(n-1)^2$ is positive, $(n-1)^2 + 1$ is also positive, and hence the result is true.

###### Example

The product of two odd numbers is again odd.

###### Proof

Let $p$ and $q$ be odd numbers. Then there are $n$ and $m$ such that $p = 2n+1$ and $q = 2 m + 1$. Then:

\begin{aligned} p q &= (2 n + 1)(2 m + 1) \\ &= 4 n m + 2 n + 2 m + 1 \\ &= 2(2 n m + n + m) +1 \end{aligned}

As $2(2 n m + n + m)$ is even, $2(2 m n + n + m) + 1$ is odd and hence the product $p q$ is odd.

Thus the product of two odd numbers is again odd.

## Characteristics

In a proof by deduction, the individual steps should be such that any reasonable person could fill them in. To aid with this, it is common to add explanations alongside. This is particularly important where any assumptions are used.

A proof should end with a conclusion.