Top ↑
Maths

CONTENTS

Maths

Proofs:

CONTENTS


DISPROOF BY COUNTEREXAMPLE

To disprove a general statement by counterexample:

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.


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:

  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