### What’s the Next Number?

We are all familiar with simple mathematical puzzles that give a short sequence and ask “What is the next number in the sequence”. Simple examples would be

$\displaystyle \begin{array}{rcl} && 1, 3, 5, 7, 9, 11, \dots \\ && 1, 4, 9, 16, 25, \dots \\ && 1, 1, 2, 3, 5, 8, \dots \,, \end{array}$

the sequence of odd numbers, the sequence of squares and the Fibonacci sequence.

The Pitfalls of Generalising

Circle division: ${n}$ points, ${c}$ chords, ${r_G}$ regions.

The idea is to spot the rule by which the terms of the sequence are generated. But the rule is never really determined by the first few terms, so the answer is not unique. Indeed, it is simple to construct a rule that matches the given terms and also generates an arbitrary value for the next term.

Let us ask “How many regions are formed if each of a set of ${N}$ points on a circle is joined by a chord to all the other ${N-1}$ points?” (see figure). For small ${N}$ it is easy to count the regions. It is tempting to assume that the sequence, which begins ${ 1, 2, 4, 8, 16, \dots }$ reveals the general pattern ${R(n) = n^2}$ for all values of ${n.}$ But this formula breaks down for ${n=6}$, when there are 31 regions. Thus, we may argue that the next number in the sequence ${ 1, 2, 4, 8, 16}$ is 31.

Lagrange Polynomials

Suppose the given terms are ${\{a_1, a_2, a_3, \dots , a_n\}}$. Linderholm (1971), in his light-hearted book “Mathematics Made Difficult”, argued that we can define a polynomial ${p(x)}$ that passes through all the points ${(k,a_k)}$ and also through an arbitrary value ${(n+1,A)}$. We first define the polynomial

$\displaystyle p_{j}(x) := \frac{(x-1)}{(j-1)} \frac{(x-2)}{(j-2)} \dots \frac{(x-(j-1))}{(j-(j-1))} \frac{(x-(j+1))}{(j-(j+1))} \dots \frac{(x-n)}{(j-n)} \,.$

For ${i\ne j}$, we have ${p_j(i) = 0}$, and for ${x = j}$ we have ${p_j(j) = 1}$. Now defining

$\displaystyle P(x) := \sum_{j=1}^n a_j p_j(x)$

we see that ${P(k) = a_k}$ for ${k=1, 2, \dots , n}$, so the polynomial ${P(x)}$ interpolates between the given terms ${( a_1, a_2, \dots , a_n )}$.

Now we extend the definitions to include an extra term:

$\displaystyle q_{j}(x) := \frac{(x-1)}{(j-1)} \frac{(x-2)}{(j-2)} \dots \frac{(x-(j-1))}{(j-(j-1))} \frac{(x-(j+1))}{(j-(j+1))} \dots \frac{(x-(n+1))}{(j-(n+1))}$

and

$\displaystyle Q(x) := \sum_{j=1}^n a_j p_j(x) + A\, q_{n+1}(x)$

Then ${Q(k) = P(k) = a_k}$ for ${1\le k\le n}$ and ${Q(n+1) = A}$. Using the polynomial ${Q(x)}$ we can argue that the next term in the sequence ${a_1, a_2, \dots , a_n}$ can take any randomly chosen value ${A}$.

In the figure below (left panel) we plot the sequence ${ 1, 4, 9, 16}$ and the interpolating polynomial ${P_4(x)=x^2}$ that fits all four points.

Then we extend the sequence in an arbitrary fashion, say ${ 1, 4, 9, 16, 50,30,20,40}$, and plot the interpolating polynomial ${P_8(x)}$ that fits all eight points:

$\displaystyle \frac{3427200 - 8614440 x + 8281910 x^2 - 4024839 x^3 + 1083425 x^4 - 163170 x^5 + 12845 x^6 - 411 x^7}{2520}$

The result is shown in the figure (right panel).

Sinc Sequences

The sinc function is defined thus:

$\displaystyle \mathrm{sinc\ } x = \begin{cases} \displaystyle{\frac{\sin x}{x}}, & x \ne 0 \\ \ \ 1, &x = 0 \end{cases}$

We note that ${\mathrm{sinc\ }x}$ oscillates with decaying amplitude as ${|x|}$ increases, and has zeros at ${\{\pm \pi, \pm 2\pi, \dots \}}$. Thus, the function ${\mathrm{sinc\ }\pi(x-m)}$ equals ${1}$ for ${x=m}$ and is zero for all other integer values of ${x}$. It is clear that, given a finite sequence ${S = \{a_1, a_2, \dots , a_n \}}$, the function

$\displaystyle f_n(x) = \sum_{k=1}^{n} a_k\, \mathrm{sinc\ }\pi(x-k)$

takes the values of the sequence ${S}$ at ${x=1, 2, 3, \dots, n}$. We can extend the sequence ${S}$ by appending an arbitrary value, ${\hat S_k = \{a_1, a_2, \dots , a_k, A \}}$, and we can define an interpolating function that takes the values ${ \{a_1, a_2, \dots , a_n, A \}}$ at ${x=1, 2, 3, \dots, n, n+1}$:

$\displaystyle \hat f_n(x) = \sum_{k=1}^{n} [ a_k\,\mathrm{sinc\ }\pi(x-k) ] + A\,\mathrm{sinc\ }\pi(x-(n+1)) \,.$

Using ${\hat f_n(x)}$, we can argue that ${A}$ is the “natural next number” in the sequence ${S = \{a_1, a_2, \dots , a_n \}}$.

For example, we plot the sequence ${ 1, 4, 9, 16}$ and the sinc expansion ${s_4(x)}$ that fits all four points (left panel in figure below). Then we extend the sequence arbitrarily to ${ 1, 4, 9, 16, 50,30,20,40}$ and plot the corresponding sinc sum ${s_8(x)}$ (right panel).

Conclusion

Given the initial terms of a sequence, there are many ways to define a function that fits all the given values and also takes arbitrary subsequent values. This, in purely logical terms, the question “What is the next Number?” does not have a well-defined answer. However, if you apply this logic in your MCQ or your IQ test, you may score badly.

Sources

${\bullet}$ Linderholm, Carl E., 1971: Mathematics Made Difficult. Wolfe Publishing, London. 207 pages SBN: 72340415 1.