Proofs:

Disproof by Counterexample
Proof by Deduction
Proof by Exhaustion
Proof by Contradiction
Proof by Induction

DISPROOF BY COUNTEREXAMPLE

To disprove a general statement by counterexample:

Find one case where the statement is wrong
Demonstrate false implication
Conclude implication is false

EXAMPLE:

e.g.1 Disprove the statement that all numbers $(n^2 + 6)(n^2 + 4)$ are divisible by 5 for $n ∈ NN$ .

When $n = 5$ :
$\begin{align} (5^2 + 6)(5^2 + 4) & = 31 \times 29 \\ & = 899 \end{align}$
899 is not divisible by 5
∴ $(n^2 + 6)(n^2 + 4)$ is not necessarily divisible by 5 for $n ∈ NN$

PROOF BY DEDUCTION

This is a form of proof consisting of a series of facts and mathematical deductions from those facts to prove a given statement.

EXAMPLE:

e.g.1 Prove that the product of three consecutive integers is divisible by 6.

In any pair of consecutive integers, one of them will have a factor of 2
In any triple of consecutive integers, one of them will have a factor of 3
∴ The product of three consecutive integers has factors of 2 and 3
Any number with factors of 2 and 3 is divisible by 2 x 3 = 6
∴ The product of three consecutive integers is divisible by 6

Divisibility can be proved by finding factors

EXAMPLES:

e.g.2 Prove that the difference between squares of integers which differ by 2 is divisible by 4.

Let $n$ be the smaller integer $\begin{align} \text{Difference} & = (n+2)^2 - n^2 \\ & = n^2 + 4n + 4 - n^2 \\ & = 4n + 4 \\ & = 4(n + 1) \end{align}$ This is 4 times an integer.
∴ The difference between squares of integers which differ by 2 is divisible by 4.

e.g.3 Prove that the product of two odd numbers is odd.

Let $n_1$ and $n_2$ be odd numbers

$n_1 = 2k_1 + 1$ , where $k_1$ is an integer
$n_2 = 2k_2 + 1$ , where $k_2$ is an integer $\begin{align} n_1 n_2 & = (2k_1 + 1)(2k_2 + 1) \\ & = 4 k_1 k_2 + 2k_1 + 2k_2 + 1 \\ & = 2(2 k_1 k_2 + k_1 + k_2) + 1 \end{align}$ This is 1 more than 2 times an integer, so it is an odd number.
∴ The product of 2 odd numbers is odd.

PROOF BY EXHAUSTION

Sometimes we can prove results by considering every possible case.

EXAMPLES:

e.g.1 Prove that no two-digit number with sum of digits equal to 11 is a square number.

The number could be: 29, 38, 47, 56, 65, 74, 83 or 92.

None of these numbers are square numbers.
∴ No 2 digit number with sum of digits equal to 11 is a square number

e.g.2 Prove that 97 is a prime number.

We only need to check whether 97 is divisble by any prime numbers below $sqrt(97)$ .
97 is not divisible by 2, 3, 5 or 7.
∴ 97 is prime.

We can consider the integers as being one of two cases - odd or even. We can express even numbers algebraically as $2k$ and odd numbers as $2k + 1$ , for some integer $k$ .

EXAMPLES:

e.g.3 Prove that the square of an integer is always either a multiple of 4, or 1 more than a multiple of 4.

Let $n$ be an integer. $n$ is either odd or even.

Case 1: $n$ is odd

$n = 2k + 1$ , where $k$ is an integer $\begin{align} n^2 & = 4k^2 + 4k + 1 \\ & = 4(k^2 + k) + 1 \end{align}$ This is 1 more than 4 times a whole number.
∴ If $n$ is odd, then $n^2$ is 1 more than a multiple of 4.

Case 2: $n$ is even

$n = 2k$ , where $k$ is an integer
$n^2 = 4k^2$ This is 4 times a whole number.
∴ If $n$ is even, then $n^2$ is a multiple of 4.

∴ The square of an integer is always either a multiple of 4, or 1 more than a multiple of 4.

e.g.4 Prove that the square of an integer is never 1 less than a multiple of 3.

Let $n$ be an integer. $n$ has remainder either 0, 1 or 2 when divided by 3.

Case 1: remainder is 0

$n = 3k$ , where $k$ is an integer $\begin{align} n^2 & = 9k^2 \\ & = 3(3k^2) \end{align}$ This is 3 times a whole number, so it is not 1 less than a multiple of 3

Case 2: remainder is 1

$n = 3k + 1$ , where $k$ is an integer
$\begin{align} n^2 & = 9k^2 + 6k + 1 \\ & = 3(3k^2 + 2k) + 1 \end{align}$ This is 1 more than 3 times a whole number, so it is not 1 less than a multiple of 3.

Case 3: remainder is 2

$n = 3k + 2$ , where $k$ is an integer
$\begin{align} n^2 & = 9k^2 + 12k + 4 \\ & = 3(3k^2 + 4k + 1) + 1 \end{align}$ This is 1 more than 3 times a whole number, so it is not 1 less than a multiple of 3.

∴ The square of an integer is never 1 less than a multiple of 3.

We can split the numberline into a finite number of regions

EXAMPLE:

e.g.5 Prove that $abs(x + 1) + abs(x - 1) > abs(2x) -1$ . $abs(x)$ is the modulus function and represents the absolute value of $x$ , ignoring the sign.

We split our numberline at the points where $abs(x + 1) = 0, abs(x - 1) = 0 and abs(2x) = 0$ . i.e. at $x = -1, x = 1 and x = 0$ .

Case 1: $x < -1$

$\begin{align} |x + 1| + |x - 1| & = -(x + 1) - (x - 1) \\ & = -2x \end{align}$ $-2x > -2x - 1$

∴ The statement is true for $x < -1$ .

Case 2: $-1 ≤ x < 0$

$\begin{align} |x + 1| + |x - 1| & = (x + 1) - (x - 1) \\ & = 2 \end{align}$ $2 ≥ -2x$ for $-1 ≤ x < 0$
∴ $2 > -2x - 1$

∴ The statement is true for $-1 ≤ x < 0$ .

Case 3: $0 ≤ x < 1$

$\begin{align} |x + 1| + |x - 1| & = (x + 1) - (x - 1) \\ & = 2 \end{align}$ $2 > 2x$ for $0 ≤ x < 1$
∴ $2 > 2x - 1$

∴ The statement is true for $0 ≤ x < 1$ .

Case 4: $x ≥ 1$

$\begin{align} |x + 1| + |x - 1| & = (x + 1) + (x - 1) \\ & = 2x \end{align}$ $2x > 2x - 1$

∴ The statement is true for $x ≥ 1$ .

∴ $abs(x + 1) + abs(x - 1) > abs(2x) -1$

PROOF BY CONTRADICTION

One way to prove a statement is true is to assume that the opposite of the statement is true and see what the consequences are. If a consequence contradicts the assumption, the assumption was in fact wrong. If the assumption was wrong, then the original statement must have actually been true.

EXAMPLES:

e.g.1 Prove that $sqrt(2)$ is irrational.

Suppose that $sqrt(2)$ is rational.
Then $sqrt(2) = a/b$ , where $a and b ∈ NN and HCF(a, b) = 1$

$2 = a^2/b^2$
$2b^2 = a^2$

2 is a factor of LHS
⇒ 2 is a factor of RHS
⇒ 2 is a factor $a^2$
⇒ 2 is a factor of $a$
⇒ $a = 2c$ , where $c ∈ NN$

$\begin{align} 2b^2 & = (2c)^2 \\ & = 4c^2 \end{align}$ $b^2 = 2c^2$

2 is a factor is RHS
⇒ 2 is a factor of LHS
⇒ 2 is a factor of $b^2$
⇒ 2 is a factor of $b$

∴ HCF(a, b) ≥ 2 #contradiction
∴ $sqrt(2)$ is irrational

e.g.2 There are 15 subjects to choose from at A-Level. Each student chooses four subjects. Class sizes are limited to 13. Prove that amongst 49 students, there is a subject with at least 2 classes.

Suppose all subjects have at most 1 class.
Then there is space for $15 xx 13 == 195$ students.
There needs to be space for $49 xx 4 = 196$ students. #contradiction
∴ There is a subject with at least 2 classes.

e.g.3 Prove that there are infinitely many primes.

Suppose that there are a finite number of primes.
Then we can make a list containing all the primes $P_1, P_2, P_3, ..., P_n$

Consider $N = P_1 P_2 P_3 ... P_n + 1$

None of the primes in our list divide into $N$ .
∴ $N$ is prime, or has factors not in our list of primes, one of which must be prime.
∴ There are infinitely many primes.

PROOF BY INDUCTION

Mathematical induction is used to prove that a result is true for all integer n. It uses two principles:

The Base/Initial Case: The result is true for the smallest integer (normally 0 or 1)
The Inductive Step: If the result is true for some integer k, that implies the result is true for the next integer, k + 1

It's like setting off an infinite set of dominoes. The first one falls and each domino pushes the next over.

EXAMPLES:

e.g.1 Prove the formula for the triangle numbers, $T_n = 1/2 n(n+1)$ .

Statement: $T_n = 1/2 n(n+1)$

For $n=1$ :

$T_1 = 1$
$1/2 n(n+1) = 1/2 xx 1 xx 2 = 1$

∴ The statement is true for $n = 1$

Suppose the statement is true for $n = k$ .
Then $T_k = 1/2 k(k+1)$
$\begin{align} T_{k+1} & = T_k + (k + 1) \\ & = \frac{1}{2}k(k+1) + (k+1) \\ & = (k + 1)(\frac{1}{2}k + 1) \\ & = \frac{1}{2}(k+1)(k+2) & = \frac{1}{2}(k+1)((k+1)+1) \end{align}$ This is the statement when $n = k+1$
∴ The statement is true for $n = k+1$

Since the statement is true for $n=1$ , and if true for $n=k$ then true for $n=k+1$ , it is true for all positive integer $n$ by mathematical induction.

e.g.2 Prove that if $A = \begin{bmatrix} 2 & 4 \\ 0 & 1 \end{bmatrix}$ , then $A^n = \begin{bmatrix} 2^n & 2^{n+2} - 4 \\ 0 & 1 \end{bmatrix}$

See here for a reminder about matrices.

Statement: $A^n = \begin{bmatrix} 2^n & 2^{n+2} - 4 \\ 0 & 1 \end{bmatrix}$

For $n=1$ :
$A^1 = \begin{bmatrix} 2^1 & 2^3 - 4 \\ 0 & 1 \end{bmatrix} =\begin{bmatrix} 2 & 4 \\ 0 & 1 \end{bmatrix}$ ∴ The statement is true for $n=1$

Suppose the statement is true for $n=k$ .
Then $A^k = \begin{bmatrix} 2^k & 2^{k+2} - 4 \\ 0 & 1 \end{bmatrix}$
$\begin{align} A^{k+1} & = A \times A^k \\ & = \begin{bmatrix} 2 & 4 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 2^k & 2^{k+2} - 4 \\ 0 & 1 \end{bmatrix} \\ & = \begin{bmatrix} 2 \times 2^k + 4 \times 0 & 2(2^{k+2} - 4) + 4 \times 1 \\ 0 \times 2^k + 1 \times 0 & 0(2^{k+2} - 4) + 1 \times 1 \end{bmatrix} \\ & = \begin{bmatrix} 2^{k+1} & 2^{k+3} - 8 + 4 \\ 0 & 1 \end{bmatrix} \\ & = \begin{bmatrix} 2^{k+1} & 2^{(k+1)+2} - 4 \\ 0 & 1 \end{bmatrix} \end{align}$ This is the statement when $n = k+1$
∴ The statement is true for $n = k+1$

Since the statement is true for $n=1$ , and if true for $n=k$ then true for $n=k+1$ , it is true for all positive integer $n$ by mathematical induction.

e.g.3 Prove that $u_n = 5^(3n+1) + 2(-1)^n$ is divisible by 7 for all positive integers $n$ .

For $n=1$ :
$\begin{align} u_1 & = 5^4 + (2 \times -1) \\ & = 623 \\ & = 7 \times 89 \end{align}$ ∴ $u_1$ is divisible by 7
∴ The statement is true for $n=1$

Suppose the statement is true for $n=k$ .
Then $7|u_k$ (Note: $a|b$ means " $a$ divides $b$ ", i.e. there exists an integer $c$ such that $ac=b$ ).
Then $u_k = 7m$ for integer $m$ .
$\begin{align} u_{k+1} & = 5^{3(k+1)+1} + 2(-1)^{k+1} \\ & = 5^{3k+4} + 2(-1)^{k+1} \\ & = 5^3 \times 5^{3k+1} + 2 \times (-1)^k \times -1 \\ & = 125(5^{3k+1}) -2(-1)^k \\ & = 125(u_k - 2(-1)^k) -2(-1)^k \\ & = 125u_k - 250(-1)^k - 2(-1)^k \\ & = 125u_k - 252(-1)^k \\ & = 125 \times 7m - 7 \times 36 \times (-1)^k \\ & = 7(125m - 36(-1)^k) \end{align}$
∴ $7|u_(k+1)$
∴ The statement is true for $n=k+1$

Since the statement is true for $n=1$ , and if true for $n=k$ then true for $n=k+1$ , it is true for all positive integer $n$ by mathematical induction.

With an inequality, the induction hypothesis gives the inequality at the next stage.

EXAMPLE:

e.g.4 Prove that $(1+x)^n > 1 + nx$ for positive integer $n$ > 1 and $x$ > 0.

For $n=2$ :

LHS $= (1 + x)^2 = 1 + 2x + x^2$
RHS $= 1 + 2x$

$1 + 2x + x^2 > 1 + 2x$
∴ The statement is true for $n=2$

Suppose the statement is true for $n=k$ .
Then $(1+x)^k > 1 + kx$

$\begin{align} (1+x)^{k+1} & > (1+x)(1+kx) \\ & > 1 + x + kx + kx^2 \\ & > 1 + (k+1)x + kx^2 \end{align}$
$1 + (k+1)x + kx^2 > 1 + (k+1)x$

$∴ (1+x)^(k+1) > 1 + (k+1)x$

This is the statement when $n=k+1$
∴ The statement is true for $n=k+1$

Since the statement is true for $n=2$ , and if true for $n=k$ then true for $n=k+1$ , it is true for all integer $n > 1$ by mathematical induction.

Back to Maths Home

CONTENTS

Proofs:

CONTENTS

DISPROOF BY COUNTEREXAMPLE

PROOF BY DEDUCTION

PROOF BY EXHAUSTION

PROOF BY CONTRADICTION

PROOF BY INDUCTION