notes
Proof by Deduction

Proof by Deduction

Contents

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 nn \in \mathbb{N}, n 22n+2n^2 - 2n + 2 is positive.

Proof

Let nn \in \mathbb{N}, then:

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

Since (n1) 2(n-1)^2 is positive, (n1) 2+1(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 pp and qq be odd numbers. Then there are nn and mm such that p=2n+1p = 2n+1 and q=2m+1q = 2 m + 1. Then:

pq =(2n+1)(2m+1) =4nm+2n+2m+1 =2(2nm+n+m)+1 \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(2nm+n+m)2(2 n m + n + m) is even, 2(2mn+n+m)+12(2 m n + n + m) + 1 is odd and hence the product pqp 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.