6.2: ‘Mathematical induction’ and ‘scientific induction’

The idea of a “list that goes on for ever” arose in the sequence of powers of 4 back in Problem 16, where we asked

Do the two sequences arising from successive powers of 4:

• the leading digits:

$$\begin{array}{cc}& \mathrm{4,\; 2,\; 6,\; 2,\; 1,\; 4,\; 2,\; 6,\; 2,\; 1,\; 4,\dots ,}\hfill \end{array}$$

and

• the units digits:

$$\begin{array}{cc}& \mathrm{4,\; 6,\; 4,\; 6,\; 4,\; 6,\; 4,\; 6,\dots ,}\hfill \end{array}$$

really “repeat for ever” as they seem to?

This example illustrates the most basic misconception that sometimes arises concerning mathematical induction – namely to confuse it with the kind of pattern spotting that is often called ‘scientific induction’.

In science (as in everyday life), we routinely infer that something that is observed to occur repeatedly, apparently without exception (such as the sun rising every morning; or the Pole star seeming to be fixed in the night sky) may be taken as a “fact”. This kind of “scientific induction” makes perfect sense when trying to understand the world around us – even though the inference is not warranted in a strictly logical sense.

Proof by mathematical induction is quite different. Admittedly, it often requires intelligent guesswork at a preliminary stage to make a guess that allows us to formulate precisely what it is that we should be trying to prove. But this initial guess is separate from the proof, which remains a strictly deductive construction. For example,

the fact that “1”, “$1+3$”, “$1+3+5$”, “$1+3+5+7$”, etc. all appear to be successive squares gives us an idea that perhaps the identity

P(n): $1+3+5+\cdots +($2n-1)=n2
is true, for all $n\ge 1$.

This guess is needed before we can start the proof by mathematical induction. But the process of guessing is not part of the proof. And until we construct the “proof by induction” (Problem 231), we cannot be sure that our guess is correct.

The danger of confusing ‘mathematical induction’ and ‘scientific induction’ may be highlighted to some extent if we consider the proof in Problem 76 above that “we can always construct ever larger prime numbers”, and contrast it with an observation (see Problem 228 below) that is often used in its place – even by authors who should know better.

In Problem 76 we gave a strict construction by mathematical induction:

• we first showed how to begin (with $p_1=2$ say);
• then we showed how, given any finite list of distinct prime numbers $p_1,p_2,p_3,\dots ,p_k$, it is always possible to construct a new prime $p_{k+1}$ (as the smallest prime number dividing $N_k=p_1\times p_2\times p_3\times \cdots \times p_k+1$).

This construction was very carefully worded, so as to be logically correct.

In contrast, one often finds lessons, books and websites that present the essential idea in the above proof, but “simplify” it into a form that encourages anti–mathematical “pattern–spotting” which is all–too–easily misconstrued. For example, some books present the sequence

$$\begin{array}{cc}& (2;)2+1=\mathbf{3};2\times 3+1=\mathbf{7};2\times 3\times 5+1=\mathbf{31};2\times 3\times 5\times 7+1=\mathbf{211};\dots \hfill \end{array}$$

as a way of generating more and more primes.

Problem 228

(a) Are 3, 7, 31, 211 all prime?

(b) $2\times 3\times 5\times 7\times 11+1$ prime?

(c) Is $2\times 3\times 5\times 7\times 11\times 13+1$ prime? A

We have already met two excellent historical examples of the dangers of plausible pattern–spotting in connection with Problem 118. There you proved that:

“if $$2n-1 is prime, then n must be prime.”

You then showed that $2^2-1$, $2^3-1$, $2^5-1$, $2^7-1$ are all prime, but that $2^{11}-1=2047=23\times 89$ is not. This underlines the need to avoid jumping to (possibly false) conclusions, and never to confuse a statement with its converse.

In the same problem you showed that:

“if $a^b+1$ is to be prime and $a\ne 1$, then a must be even, and b must be a power of 2.”

You then looked at the simplest family of such candidate primes namely the sequence of Fermat numbers $f_n$:

$$\begin{array}{cc}& f_0=2^1+1=3,f_1=2^2+1=5,f_2=2^4+1=17,f_3=2^8+1=257,f_4=2^{16}+1.\hfill \end{array}$$

It turned out that, although fo, $f_0,f_1,f_2,f_3,f_4$ are all prime, and although Fermat (1601–1665) claimed (in a letter to Marin Mersenne (1588–1648)) that all Fermat numbers $f_n$ are prime, we have yet to discover a sixth Fermat prime!

There are times when a mathematician may appear to guess a general result on the basis of what looks like very modest evidence (such as noticing that it appears to be true in a few small cases). Such “informed guesses” are almost always rooted in other experience, or in some unnoticed feature of the particular situation, or in some striking analogy: that is, an apparent pattern strikes a chord for reasons that go way beyond the mere numbers. However those with less experience need to realise that apparent patterns or trends are often no more than numerical accidents.

Pell’s equation (John Pell (1611–1685)) provides some dramatic examples.

• If we evaluate the expression “$n^2+1$” for $n=\mathrm{1,2}\mathrm{,\; 3},\dots$, we may notice that the outputs $\mathrm{2,5}\mathrm{,\; 10}\mathrm{,\; 17}\mathrm{,\; 26},\dots$ never give a perfect square. And this is to be expected, since the next square after $n^2$ is

$\begin{array}{cc}& {(n+1)}^2=n^2+2n+1,\hfill \end{array}$

and this is always greater than $n^2+1$.

• However, if we evaluate “$991n^2+1$” for $n=\mathrm{1,\; 2,\; 3,\dots ,}$ we may observe that the outputs never seem to include a perfect square. But this time there is no obvious reason why this should be so – so we may anticipate that this is simply an accident of “small” numbers. And we should hesitate to change our view, even though this accident goes on happening for a very, very, very long time: the smallest value of n for which $$991n2+1 gives rise to a perfect square is apparently

$\begin{array}{cc}& n=12055735790331359447442538767.\hfill \end{array}$