Topic 1
Proof
Proofs are fundamental in mathematics as they ensure statements that are universally true can be made. A proof is a logical argument that establishes the truth of a mathematical statement beyond any doubt.
You may be familiar with the Pythagorean theorem, which states that $$a^2 + b^2 = c^2 \, ,$$ where $c$ is the length of the hypotenuse and $a, b$ are the lengths of the other two sides in a right-angled triangle. A proof of this statement will guarantee that it is true for every right-angled triangle and not just special cases.
A statement that has been formally proven is called a theorem. A statement that mathematicians believe to be true, but lacks a proof, is called a conjecture.
There are different ways of proving that a statement is true. We will go through the required methods of proof below.
Proof by Deduction
Start from known facts, or axioms, and apply a series of logical steps to arrive at the desired conclusion.
Prove that the product of two even numbers is even.
Let $p$ and $q$ be integers. Then $2p$ and $2q$ are two even numbers.
The product of two even numbers may therefore be written as
$$(2p)(2q) = 4pq = 2(2pq) \, ,$$ which is a multiple of $2$ and therefore even.
Therefore, the product of two even numbers is even.
$\blacksquare$
Proof by Exhaustion
Show that every individual case is true to show that the statement is true in its entirety.
Given that $p$ is a prime number such that $3 < p < 25$, prove by exhaustion that $(p - 1)(p + 1)$ is a multiple of $12$.
The prime numbers between $3$ and $25$ are $5, 7, 11, 13, 17, 19,$ and $23$.
We now prove that the statement is true for each case.
When $p=5$, $(p-1)(p+1)=(5-1)(5+1)$ $=(4)(6)=24=12(2)$, which is a multiple of $12$.
When $p=7$, $(p-1)(p+1)=(7-1)(7+1)$ $=(6)(8)=48=12(4)$, which is a multiple of $12$.
When $p=11$, $(p-1)(p+1)=(11-1)(11+1)$ $=(10)(12)=120=12(10)$, which is a multiple of $12$.
When $p=13$, $(p-1)(p+1)=(13-1)(13+1)$ $=(12)(14)=168=12(14)$, which is a multiple of $12$.
When $p=17$, $(p-1)(p+1)=(17-1)(17+1)$ $=(16)(18)=288=12(24)$, which is a multiple of $12$.
When $p=19$, $(p-1)(p+1)=(19-1)(19+1)$ $=(18)(20)=360=12(30)$, which is a multiple of $12$.
When $p=23$, $(p-1)(p+1)=(23-1)(23+1)$ $=(22)(24)=528=12(44)$, which is a multiple of $12$.
And so all of the cases satisfy the statement. Therefore, if $p$ is a prime number such that $3 < p < 25$, then $(p - 1)(p + 1)$ is a multiple of $12$. $$\tag*{$\blacksquare$}$$
Prove that for all $n \in \mathbb{N}$, the value of $n^{3} + n + 1$ is always an odd number.
If $n \in \mathbb{N}$, then $n$ is either even or odd.
Let $n$ be even. Then $n = 2k$ where $k \in \mathbb{Z}$.
Then $n^{3} + n + 1 = (2k)^{3} + (2k) + 1$ $= 8k^{3} + 2k + 1$ $= 2(4k^{3} + k) + 1$, which is an odd number.
Let $n$ be odd. Then $n = 2k + 1$ where $k \in \mathbb{Z}$.
Then $n^{3} + n + 1 = $$ (2k + 1)^{3} + (2k + 1) + 1 $ $= 8k^{3} + 3(2k)^{2} + 3(2k) + $$ 1 + 2k + 1 + 1$ $= 8k^{3} + 12k^{2} + 8k + 2 + 1 $ $= 2(4k^{3} + 6k^{2} + 4k + 1) + 1$, which is an odd number.
And so $n^{3} + n + 1$ is odd when $n$ is even and when $n$ is odd.
Therefore, $n^{3} + n + 1$ is odd for all $n \in \mathbb{N}$. $$\tag*{$\blacksquare$}$$
Disproof by Counterexample
Show that a statement is false by providing a single example that contradicts the statement.
Show that the statement
"$n^{2} - n + 1$ is a prime number for all values of $n \in \mathbb{N}$"
is false.Let $n = 5$, then $$ \begin{aligned} n^{2} - n + 1 &= 5^{2} - 5 + 1 \\ &= 25 - 5 + 1 \\ &= 20 + 1 \\ &= 21 \; . \end{aligned} $$
But $21$ is divisible by $3$ and so is not prime.
Hence $n^{2} - n + 1$ is not always prime when $n$ is a natural number.
Therefore, the statement "$n^{2} - n + 1$ is a prime number for all values of $n \in \mathbb{N}$" is false. $$\tag*{$\blacksquare$}$$
Proof by Contradiction (A Level only)
Assume the opposite of what is to be proven (i.e. assume that the statement is false) and then arrive at a contradiction. By showing that the negation of the statement leads to a falsehood or contradiction, it follows that the original statement must be true.
Prove by contradiction that $\sqrt{2}$ is an irrational number.
Assume that $\sqrt{2}$ is a rational number. This means we can write $\sqrt{2} = {a}/{b}$, where $a$ and $b$ are integers and the fraction ${a}/{b}$ is in its simplest form.
We will now show that writing $\sqrt{2}$ in this way leads to a contradiction in terms.
Squaring both sides we get $$ 2 = \frac{a^{2}}{b^{2}} \implies 2b^{2} = a^2 \: .$$
Since $2b^{2}$ is a multiple of $2$ and therefore even, then $a^2$ is also even.
We now use an auxiliary theorem, known as a lemma, to help us in our proof. We use the fact that for an integer $p$, if $p^2$ is even then $p$ is also even. We can use this lemma to now say that the integer $a$ must also be even.
And so $a$ may be written as $a=2k$, where $k$ is an integer.
Hence $$2b^{2} = (2k)^{2} =4k^{2}$$
and so $b^{2}\ = 2k^{2}$ which means $b^{2}$ is even, which means that $b$ is also even.
But $a$ and $b$ are both even and multiples of $2$, so $\sqrt{2} = {a}/{b}$ is not in its simplest form. This is a contradiction since we assumed that $\sqrt{2} = {a}/{b}$, where ${a}/{b}$ is in its simplest form.
Since assuming $\sqrt{2}$ is rational leads to a contradiction, we can therefore conclude that $\sqrt{2}$ is irrational. $$\tag*{$\blacksquare$}$$
Prove by contradiction that there are infinitely many prime numbers.
Assume that there is a finite number of prime numbers $n$, where the prime numbers are listed as $p_1, \; p_2, \;p_3,$$\; \ldots , \;p_n$.
Consider the number $N$, which is product of all the primes in the list plus one, $$N = p_1 \, \cdot \, p_2 \, \cdot \, \ldots \, \cdot \, p_n + 1 \: .$$
By construction, $N$ is not divisible by any of the prime numbers $p_1, p_2, p_3, \ldots, p_n$, since there will always be a remainder of $1$.
Hence $N$ is either a prime but not in the list of primes, or is not prime, but must then be divisible by some prime which is not included in the list. This contradicts our assumption that there are a finite number of primes that we can write as a list.
Since our assumption that there are a finite number of prime numbers leads to a contradiction, we therefore conclude that there are infinitely many prime numbers. $$\tag*{$\blacksquare$}$$