__Proofs:__

#### CONTENTS

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

**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.

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

**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.

**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`.

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

**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.

**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.

**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.

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