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.\)

Video solution by Clelland Maths 

\(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: 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.

Video solution by Clelland Maths 

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}\)

Video solution by Clelland Maths 

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.

Video solution by Clelland Maths 

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.

Video solution by Clelland Maths 

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{gather} \small\frac{p}{q}\normalsize=\sqrt{2\,} \\[6pt] \small\frac{p^2}{q^2}\normalsize=2 \\[6pt] p^2=2q^2 \\[6pt] \end{gather} $$

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{gather} p^2=2q^2 \\[6pt] (2m)^2=2q^2 \\[6pt] 4m^2=2q^2 \\[6pt] 2m^2=q^2 \\[6pt] \end{gather} $$

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\)

Video solution by Clelland Maths 

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

The course specification  for Advanced Higher Maths says: "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\small.\)

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

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 composite, then it is divisible by one of our \(n\) primes. However, this is contradicted by the fact that dividing \(P\) by any of the \(n\) primes would give a remainder of \(1\small,\) so it cannot be divisible by any of the primes.

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

Video solution by Clelland Maths 

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.

Video solution by Clelland Maths 

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\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 at least one of \(\raise 0.2pt{p}\) or \(\raise 0.2pt{q}\) is irrational.

Video solution by Clelland Maths 

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 / Qualifications Scotland marking instructions are quite fussy about how you word the final conclusion in induction proofs. Don't be tempted to shortcut this sentence!

Video solution by Clelland Maths 

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.\)

Video solution by Clelland Maths 

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

Video solution by Clelland Maths 

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

Video solution by Clelland Maths 

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

Video solution by Clelland Maths 

Statement A is false. One counterexample is that \(3^2+4^2=25\small,\) which is not prime.

Statement B can be proven to be true, as follows:

Let the two consecutive integers be \(k\) and \(k\!+\!1\small,\) where \(k\in\mathbb Z\small.\)

Then the sum of their squares is:

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

It is sufficient to note that this is odd \(\forall k\in\mathbb Z\small\) but if you wanted to be ultra-precise, you could write something like the following conclusion:

\(k^2\!+\!k\in\mathbb Z,\) so \(2(k^2\!+\!k)\) is even, \(2(k^2\!+\!k)\!+\!1\) is odd and hence \(k^2+(k\!+\!1)^2\) is odd. QED.