Advanced Higher Maths
Methods of Proof

This statement is false for any negative value of \(\raise 0.2pt{n}\small.\)

So, for example, \(\raise 0.2pt{n\!=\!\!\!-\!1}\) is a counterexample. \(\sqrt{(-1)^{2}\ }=1\small,\) not \(-1\small.\)

\(P_{1}\!+\!1=2\!+\!1=3\small,\) which is prime.
\(P_{2}\!+\!1=2.3\!+\!1=7\) (prime).
\(P_{3}\!+\!1=2.3.5\!+\!1=31\) (prime).
\(P_{4}\!+\!1=2.3.5.7\!+\!1=211\) (prime).
\(P_{5}\!+\!1=2.3.5.7.11\!+\!1=2311\) (prime).
\(P_{6}\!+\!1=2.3.5.7.11.13\!+\!1\)
\(\phantom{P_{6}\!+\!1}=30\tiny\,\normalsize 031=59\!\times\!509\) (composite).

So \(\raise 0.2pt{n\!=\!6}\) is a counterexample. Therefore \(\raise 0.2pt{P_{n}\!+\!1}\) is not prime \(\raise 0.2pt{\forall n\!\in\!\mathbb N\small.}\)

Note that this example would be unfair as an exam question. You are not expected to be able to identify whether or not large numbers are prime! However, it illustrates the counterexample method nicely.

This is an example of direct proof which also demonstrates how to characterise multiples.

\(\raise 0.2pt{2\vert a}\) so \(\raise 0.2pt{\exists m\!\in\!\mathbb Z}\) such that \(\raise 0.2pt{a\!=\!2m}\)
\(\raise 0.2pt{3\vert b}\) so \(\raise 0.2pt{\exists n\!\in\!\mathbb Z}\) such that \(\raise 0.2pt{b\!=\!3n}\)

\(\raise 0.2pt{\therefore\ ab=(2m)(3n)=6mn}\)

So, as \(\raise 0.2pt{mn\!\in\!\mathbb Z\small,\normalsize\ 6\vert ab}\)

This is an example of direct proof which also demonstrates how to characterise odd and even numbers.

Let the two numbers be \(\raise 0.2pt{a}\) and \(\raise 0.2pt{b}\small.\)

\(\raise 0.2pt{a}\) is odd so \(\raise 0.2pt{a\!=\!2k\!-\!1\small,\normalsize\ k\!\in\!\mathbb Z}\)
\(\raise 0.2pt{b}\) is odd so \(\raise 0.2pt{b\!=\!2l\!-\!1\small,\normalsize\ l\!\in\!\mathbb Z}\)

Now we obtain an expression for the sum of the squares:

$$ \begin{eqnarray} a^2\!+\!b^2 &=& (2k\!-\!1)^2+(2l\!-\!1)^2 \\[6pt] &=& 4k^2\!-\!4k\!+\!1+\!4l^2\!-\!4l\!+\!1\\[6pt] &=& 4k^2\!-\!4k\!+\!4l^2\!-\!4l\!+\!2\\[6pt] &=& 2(2k^2\!-\!2k\!+\!2l^2\!-\!2l\!+\!1)\\[6pt] \end{eqnarray} $$

So \(\raise 0.2pt{a^2\!+\!b^2}\) is a multiple of \(2\small,\) i.e. is even.

Note: It doesn't matter whether you use \(\raise 0.2pt{2k\!-\!1}\) or \(\raise 0.2pt{2k\!+\!1}\) for an odd number.

This example of direct proof requires a little more imagination than the previous two examples.

Think for a moment about a group of three consecutive integers. Each of them is one more than the previous number. The first is one less than the middle. The last is one more than the middle.

So if \(\raise 0.2pt{n}\) is a multiple of \(3\small,\) then:

$$ \begin{eqnarray} n &=& 3k\ (k\!\in\!\mathbb Z) \\[6pt] &=& k+k+k\\[6pt] &=& (k\!-\!1)+k+(k\!+\!1) \\[6pt] \end{eqnarray} $$

And that's it! \(\raise 0.2pt{k\!-\!1\small,\normalsize k}\) and \(\raise 0.2pt{k\!+\!1}\) are three consecutive integers. QED.

This proof was first created about 2300 years ago by the Greek mathematician Euclid of Alexandria.

We assume the negation of what we are trying to prove, and follow logical steps to reach a logical impossibility.

So, suppose \(\sqrt{2\,}\) is rational. Then it can be expressed as a fully simplified fraction \(\large\frac{p}{q}\small,\) where \(p\small,\normalsize q\!\in\!\mathbb Z\small.\)

$$ \begin{eqnarray} \small\frac{p}{q}\normalsize &=& \sqrt{2\,} \\[6pt] \small\frac{p^2}{q^2}\normalsize &=& 2 \\[6pt] p^2 &=& 2q^2 \\[6pt] \end{eqnarray} $$

Now, as \(\raise 0.3pt{q^2\!\in\!\mathbb Z\small,\normalsize}\) \(\raise 0.2pt{p^2}\) is even and so \(\raise 0.2pt{p}\) is even.

So we can express \(\raise 0.2pt{p}\) as \(\raise 0.2pt{2m\small,\normalsize m\!\in\!\mathbb Z\small.}\)

$$ \begin{eqnarray} p^2 &=& 2q^2 \\[6pt] (2m)^2 &=& 2q^2 \\[6pt] 4m^2 &=& 2q^2 \\[6pt] 2m^2 &=& q^2 \\[6pt] \end{eqnarray} $$

Now, as \(\raise 0.2pt{m^2\!\in\!\mathbb Z\small,}\) \(\raise 0.2pt{q^2}\) is even and so \(\raise 0.2pt{q}\) is even.

We have now shown that both \(\raise 0.2pt{p}\) and \(\raise 0.2pt{q}\) are even. However, this contradicts the fact that \(\large\frac{p}{q}\) is fraction that has been reduced to its lowest terms, i.e. that there are no common factors of \(\raise 0.2pt{p}\) and \(\raise 0.2pt{q}\small.\)

Because we have reached a contradiction, our original assumption must be false. Hence \(\sqrt{2\,}\) is irrational. \(\square\)

Like Example 6, this was first proven by Euclid around 300 BCE.

The SQA, in the course specification for Advanced Higher Maths, say: "Candidates would benefit from exposure to proofs that \(\sqrt{2\,}\) is irrational and the infinitude of primes." That's why we have included them on this page.

We assume the negation of what we are trying to prove, and follow logical steps to reach a logical impossibility.

So let us assume that there are \(\raise 0.2pt{n}\) prime numbers: \(\raise 0.3pt{p_1\small,\normalsize\ p_2\small,\normalsize\ p_3,\small\cdots\small,\normalsize\normalsize\ p_{n}\small.}\)

Let \(\raise 0.2pt{P}\) be one more than the product of all the prime numbers. That is, let \(P=p_{1}\small\,\normalsize p_{2}\small\,\normalsize \small\cdots\normalsize\small\,\normalsize p_{n}+1.\)

Now, \(\raise 0.2pt{P}\) is either prime or it is not.

If \(\raise 0.2pt{P}\) is prime, then \(\raise 0.2pt{P}\) is a prime that is greater than any of our \(\raise 0.2pt{n}\) primes. This is a contradiction.

If \(\raise 0.2pt{P}\) is not prime, then it is divisible by one of the primes in our list, which we will call \(\raise 0.2pt{p\small.}\) However, \(\raise 0.2pt{p}\) cannot be any of \(\raise 0.2pt{p_1\small,\normalsize\ p_2\small,\normalsize\ p_3,\small\cdots\small,\normalsize\normalsize\ p_{n}}\) because otherwise \(\raise 0.2pt{p}\) would divide into \(\raise 0.2pt{1}\), which is impossible. So \(\raise 0.2pt{p}\) is some new prime, and again we have a contradiction.

Because in either case we have reached a contradiction, our original assumption must be false. Hence there is an infinity of prime numbers. QED.

The contrapositive statement is:

If \(\raise 0.2pt{n}\) is not a multiple of \(3\) then \(\raise 0.2pt{n^2}\) is not a multiple of \(3\small.\)

So we assume that \(\raise 0.2pt{3\not\mid n}\) and consider these two cases: the remainder when \(\raise 0.2pt{n}\) is divided by \(3\) is either \(1\) or \(2\small.\)

Remainder \(1\) means that \(\raise 0.3pt{n=3k+1}\) for some \(\raise 0.2pt{k\!\in\!\mathbb Z\small.}\) In this case:

$$ \begin{eqnarray} n^2 &=& (3k+1)^2 \\[6pt] &=& 9k^2+6k+1 \\[6pt] &=& 3(3k^2+2k)+1 \\[6pt] \end{eqnarray} $$

So, in this case, \(\raise 0.2pt{n^2}\) is \(1\) greater than a multiple of \(3\small.\) Hence \(\raise 0.2pt{3\not\mid n^2\small.}\)

Remainder \(2\) means that \(\raise 0.2pt{n=3k+2}\) for some \(\raise 0.3pt{k\!\in\!\mathbb Z\small.}\) In this case:

$$ \begin{eqnarray} n^2 &=& (3k+2)^2 \\[6pt] &=& 9k^2+12k+4 \\[6pt] &=& 9k^2+12k+3+1 \\[6pt] &=& 3(3k^2+4k+1)+1 \\[6pt] \end{eqnarray} $$

So, in this second case, \(\raise 0.2pt{n^2}\) is \(1\) greater than a multiple of \(3\small.\) Hence \(\raise 0.2pt{3\not\mid n^2\small.}\)

We have exhaused the only two cases, and in each of them, \(\raise 0.2pt{3\not\mid n^2\small.}\)

We have therefore proven that if \(\raise 0.2pt{3\not\mid n\small,}\) then \(\raise 0.2pt{3\not\mid n^2\small.}\)

By contrapositive, if \(\raise 0.2pt{3\mid n^2\small,}\) then \(\raise 0.2pt{3\mid n\small.\ \square}\)

Note: The Fundamental Theorem of Arithmetic (also known as the Unique Factorisation Theorem) enables a much more elegant proof of this conjecture, but the question told us to use the contrapositive.

The contrapositive statement is:

If \(\raise 0.2pt{p}\) and \(\raise 0.2pt{q}\) are both rational, then \(\raise 0.2pt{pq}\) is rational.

So let \(p=\large\frac{a}{b}\) and let \(q=\large\frac{c}{d}\small,\) where \(\raise 0.2pt{a\small,\normalsize c\!\in\!\mathbb Z}\) and \(\raise 0.2pt{b\small,\normalsize d\!\in\!\mathbb N\small.}\)

Now we multiply the fractions:

$$ \begin{eqnarray} pq &=& \small\frac{a}{b}\normalsize\times\small\frac{c}{d} \\[6pt] &=& \small\frac{ac}{bd}\normalsize \\[6pt] &\in& \mathbb Q \\[6pt] \end{eqnarray} $$

We have therefore proven that if \(\raise 0.2pt{p,q\!\in\!\mathbb Q}\) then \(\raise 0.2pt{pq\!\in\!\mathbb Q\small.}\)

By contrapositive, if \(\raise 0.2pt{pq\!\not\in\!\mathbb Q}\) then \(\raise 0.2pt{p}\) and/or \(\raise 0.2pt{q}\) is irrational.

Base case: \(\raise 0.2pt{\boldsymbol{n\!=\!1}}\)
\(\raise 0.2pt{6^{1}\!+\!4=10\small,}\) which is divisible by \(\raise 0.2pt{10\small.}\)

Induction step:
Assume that \(\raise 0.2pt{10\mid 6^{k}\!+\!4}\) for some \(\raise 0.2pt{k\!\in\!\mathbb N\small.}\)
We will show that \(\raise 0.2pt{10\mid 6^{k+1}\!+\!4\small.}\)

\(\raise 0.2pt{6^{k}\!+\!4=10a\small,}\) say, where \(\raise 0.2pt{a\!\in\!\mathbb Z}\small.\)
So \(\raise 0.2pt{6^{k}=10a\!-\!4\small.}\) Now:

$$ \begin{eqnarray} 6^{k+1}\!+\!4 &=& 6(6^k)\!+\!4 \\[6pt] &=& 6(10a\!-\!4)\!+\!4 \\[6pt] &=& 60a\!-\!24\!+\!4 \\[6pt] &=& 60a\!-\!20 \\[6pt] &=& 10(6a\!-\!2) \\[6pt] \end{eqnarray} $$

As \(\raise 0.2pt{6a\!-\!2\!\in\!\mathbb Z\small,\normalsize\ 10\mid 6^{k+1}\!+\!4\small.}\)

So, the proposition being true for \(n=k\) implies that it is also true for \(n=k\!+\!1\small,\) and as the base case shows that it is true when \(n=1\small,\) the principle of mathematical induction tells us that it is true for all \(n\!\in\!\mathbb N\small.\)

Note: SQA marking instructions are quite fussy about how you word the final conclusion in induction proofs. Don't be tempted to shortcut this sentence!

Base case: \(\raise 0.2pt{\boldsymbol{n\!=\!1}}\)
\(F_1=1\) and \(F_3=2\) so \(F_1=F_3-1\)

Induction step:
Assume that, for some \(\raise 0.2pt{k\!\in\!\mathbb N\small,}\) \(F_1+F_2+\cdots +F_k=F_{k+2}-1\small.\) So:

$$ \begin{eqnarray} && F_1+F_2+\cdots +F_{k+1} \\[6pt] &=& (F_1+F_2+\cdots +F_{k})+F_{k+1} \\[6pt] &=& (F_{k+2}-1)+F_{k+1} \\[6pt] &=& (F_{k+2}+F_{k+1})-1 \\[6pt] &=& F_{k+3}-1 \\[6pt] &=& F_{(k+1)+2}-1 \\[6pt] \end{eqnarray} $$

So, the proposition being true for \(n=k\) implies that it is also true for \(n=k\!+\!1\small,\) and as the base case shows that it is true when \(n=1\small,\) the principle of mathematical induction tells us that it is true for all \(n\!\in\!\mathbb N\small.\)

Base case: \(\raise 0.2pt{\boldsymbol{n\!=\!1}}\)
LHS = \(1(3\!-\!1)=2\)
RHS = \(1^{2}(1\!+\!1)=2\)
So the base case is established.

Induction step:
Assume that the proposition is true for \(\raise 0.2pt{n\!=\!k\small,\normalsize\ k\!\in\!\mathbb N\small.}\) We will show that it is also true for \(\raise 0.2pt{n=k\!+\!1\small.}\)

$$ \begin{eqnarray} && \sum^{\normalsize {k+1}}_{\normalsize {r=1}}\,r(3r\!-\!1)\\[6pt] &=& \sum^{\normalsize {k}}_{\normalsize {r=1}}\,r(3r\!-\!1) + (k\!+\!1)(3(k\!+\!1)\!-\!1) \\[6pt] &=& k^{2}(k\!+\!1) + (k\!+\!1)(3k\!-\!2) \\[6pt] &=& (k\!+\!1)(k^{2}\!+3k\!+2) \\[6pt] &=& (k\!+\!1)(k\!+\!1)(k\!+\!2) \\[6pt] &=& (k\!+\!1)^{2}(k\!+\!2) \\[6pt] \end{eqnarray} $$

So, the proposition being true for \(n=k\) implies that it is also true for \(n=k\!+\!1\small,\) and as the base case shows that it is true when \(n=1\small,\) the principle of mathematical induction tells us that it is true for all \(n\!\in\!\mathbb N\small.\) So:

$$ \sum^{\normalsize {n}}_{\normalsize {r=1}}\,r(3r\!-\!1)=n^{2}(n\!+\!1)\small,\normalsize\:\:\forall n\!\in\!\mathbb N $$

Base case: \(\raise 0.2pt{\boldsymbol{n\!=\!1}}\)
LHS \(=1!\times 1=1\)
RHS \(=(1\!+\!1)!-1=2-1=1\)
So the base case is established.

Induction step:
Assume that, for some \(\raise 0.2pt{n\!=\!k\small,\normalsize\ k\!\in\!\mathbb N\small,}\)

So, the proposition being true for \(n=k\) implies that it is also true for \(n=k\!+\!1\small,\) and as the base case shows that it is true when \(n=1\small,\) the principle of mathematical induction tells us that it is true for all \(n\!\in\!\mathbb N\small.\) Thus:

$$ \sum^{\normalsize {n}}_{\normalsize {r=1}}\,r!\,r=(n\!+\!1)!-1\:\:\forall n\!\in\!\mathbb N $$

(a)  Any \(a\lt 0\) and \(b\gt 0\small,\) where \(\lvert a\rvert\gt\lvert b\rvert\small,\) will serve as a counterexample.

So, for example, \(a=-2\) and \(b=1\) disproves the statement, because \(4 \gt 1\small.\)

(b)  \(n\) is odd so \(\raise 0.2pt{n\!=\!2k\!-\!1\small,\normalsize\ k\in\mathbb Z}\small.\)

$$ \begin{eqnarray} n^2-1 &=& \left(2k-1\right)^2-1\\[6pt] &=& \left(4k^2-4k+1\right)-1\\[6pt] &=& 4k^2-4k\\[6pt] &=& 4(k^2-k) \end{eqnarray} $$

This is a multiple of \(4\) because \(k^2-k \in\mathbb Z\small.\)

Note: You could also use \(\raise 0.2pt{n\!=\!2k\!+\!1\small,\normalsize\ k\in\mathbb Z}\) here. Both are correct representations of an odd number.