1.1 Proof

Proof

A proof is a method of validating the truthfulness of a given statement

Topic overview

Understand and use the structure of mathematical proof, proceeding from given assumptions through a series of logical steps to a conclusion

Methods of proof

Proof by deduction

Proving a statement through simplification and the application of well known mathematical principles (e.g $x^2$ will always be positive)

Example:

Using completion of the square, prove that $n^2-6n+10$ is positive for all values of $n$

$n^2-6n+10 > 0$ $n^2-6n > -10$ $n^2-6n+9 > -1$ $(n-3)^2 > -1$ Because n is always squared, now value of n will result in $(n-3)^2$ being $\leq -1$

Proof by exhaustion

Proving a statement by exhaustion involes trying every possibility to validate a proof. This is only possible on functions with a countable domain and can be very inefficient for functions with a large domain.

Example:

Supppose $x$ and $y$ are odd integers less than 7, prove that their sum is divisible by 2

Possible unique pairs:

x 1 3 5 1 1 3 5 3 5
y 1 3 5 3 5 1 1 5 3
Sum 2 6 10 4 6 4 6 8 8
Divisible by 2? Yes Yes Yes Yes Yes Yes Yes Yes Yes

Disproof by counter example

Proving a statement to be false by applying basic mathematical principles.

Example:

Show that the statement “$n^2-n+1$ is a prime number for all values of $n$” is untrue. Method 1:

$n = 5$ $5^2-5+1 = 25-5+1 = 21$ $21$ is not prime because $3*7 = 21$

Method 2:

$n^2-n+1 = n(n - 1) + 1