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