Top ↑

# Proofs:

## 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

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:

1. The Base/Initial Case: The result is true for the smallest integer (normally 0 or 1)
2. 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