A formula for any finite sequence of number

In Advanced Problems in Mathematics by Stephen Siklos, pg24, he writes

"Given any finite sequence of numbers, a formula can always be found which will fit all given numbers and which makes the next number (e.g.) 42."

Is there a source or proof for this statement?

• A friend bet me at school that this was impossible. Feb 16 '20 at 6:54

Here's a somewhat intuitive way to think about it, maybe. If I gave you the sequence $$3, 7, 11, 15, 19, \dotsc$$ probably you would find that the difference between adjacent terms is always the same (it's just $$4$$), so a sensible continuation is one where you just keep adding $$4$$.

Similarly, if I gave you the sequence $$2, 5, 9, 14, 20$$, you might notice that the differences between adjacent terms are $$3, 4, 5, 6$$, so a sensible continuation of this sequence is one where you keep adding one to the difference. If we really spell this out, we can find the differences and then their "second-order" differences: $$\begin{equation*} \begin{array}{c} 2 && 5 && 9 && 14 && 20 \\ & 3 && 4 && 5 && 6 \\ && 1 && 1 && 1 \\ \end{array} \end{equation*}$$ Now if I were to give you some totally random sequence of numbers like $$9, 2, 4, 20$$, we can still go through the same process: $$\begin{equation*} \begin{array}{c} 9 && 2 && 4 && 20 \\ & -7 && 2 && 16 \\ && 9 && 14 \\ &&& 5 \\ \end{array} \end{equation*}$$ Well would you look at that! The last row is just constant, and the second to last row is just a straightforward arithmetic progression, and so on. So this sequence is obviously just given by repeatedly adding $$5$$ to the second-order difference. The next second-order differences will be $$19, 24, \dotsc$$, so the next first-order differences will be $$35, 59, \dotsc$$, so the next couple of terms should be $$55, 114, \dotsc$$

Now as it turns out, a sequence whose $$k$$th order differences are constant is precisely just a sequence whose $$n$$th term is given by a polynomial of degree $$k$$. There are various ways to convince yourself of this. You might guess the $$n$$th term has the general form $$a_k n^k + \dotsb a_1 n + a_0$$, giving yourself $$k + 1$$ unknowns. You can then go and make $$k + 1$$ equations by substituting in the values of the terms you know.

Another way of looking it at is by knowing that the closed form for $$\begin{equation*} \sum_{r = 1}^n r^k \end{equation*}$$ is a polynomial of degree $$k + 1$$, which you might prove by induction (hint: consider $$\sum_{r = 1}^n [(r + 1)^{k+1} - r^{k+1}]$$). Then since the $$k - 1$$th order differences are a sum of the $$k$$th order differences, you're basically just increasing the degree each time you go up one.

This means that not only can we justify our pattern (which in some sense would already have been enough) but we can even write down a nice formula for it!

In any case, hopefully this gives a bit of an idea of how to construct a pattern in any given set of numbers. This is why some mathematicians get a bit antsy about "what's the next number" questions, because really you could just add any number and justify it with this construction.

Aside from all of this justification, there's also quite a nice little algorithm you can use to find such a polynomial, that's more constructive than just solving some systems of equations. Say we're given $$k + 1$$ terms, labelled $$a_1, a_2, \dotsc, a_{k + 1}$$.

Define the polynomials $$f_1, \dotsc, f_{k + 1}$$ by $$\begin{equation*} f_i(x) = \prod_{j \in \{1, \dotsc, k + 1\} \setminus \{i\}} (x - j) \end{equation*}$$ Note that each $$f_i$$ is of degree $$k$$, and has the property that for any $$\ell \in \{1, \dotsc, k + 1\} \setminus \{i\}$$, $$f_i(\ell) = 0$$, and also, $$f_i(i) \ne 0$$, as this is a product of nonzero factors.

Now define the sequence $$b_n$$ by $$\begin{equation*} b_n = \sum_{i = 1}^{k + 1} \frac{a_i f_i(n)}{f_i(i)} \end{equation*}$$ This $$n$$th term is a sum of polynomials of degree $$k$$, so is a polynomial of degree at most $$k$$. As noted earlier, for each $$j \in \{1, \dotsc, k + 1\}$$, we have that $$f_i(j) = 0$$ for all $$i \ne j$$ in the sum. Therefore, $$b_j = a_j f_j(j) / f_j(j) = a_j$$, and this polynomial agrees with all of the given $$a_j$$ terms.

• Note that nonpolynomial sequences like $1,2,4,8,16,32,64,\dots$ are not predictable with this method. Feb 15 '20 at 18:48
• @Berci No, that's the point ... The sequence you've provided IS predictable ... I just have a different prediction from you. I predict the next number is ...*127* [not a typo]. The predictor is the sequence with a constant 6th-order difference of 1, starting at 1 on all lower difference orders. Feb 16 '20 at 7:38
• @Berci What's that? You had a different number in mind? 128 perhaps? Sure ... but that answer isn't an inherent part of the sequence you gave. Your answer is no more or less valid than mine. If I give the sequence 1, 2, ? and ask the next number, then both 3 and 4 are valid answers (as is literally any other number) Feb 16 '20 at 7:38
• @Brondahl I know, nevertheless I found it worth to make it a comment. Feb 16 '20 at 7:40

Yes, the Lagrange polynomial of degree $$n$$ can go through any $$n$$+1 points as long as the $$x$$ values are all different. The link gives an explicit construction. Given $$n$$ numbers, make a series of points with $$x$$ values $$1,2,3,4,\ldots n,n+1$$ and $$y$$ values the numbers for the first $$n$$ and $$42$$ for the last.

• I'd just like to add that if the sequence contains more elements than, say, the number of protons in our universe raised to the power of the number of protons in our universe, and raised again to that power, then a formula is unlikely to be found within the lifetime of our universe. Feb 16 '20 at 7:58
• @PatrickT Umm, yeah, an astronomically large sequence will take an astronomically large amount of time. Not very surprising. Simply writing out the sequence itself, let alone finding a formula, couldn't be done in the lifetime of our universe. Also, you seem to be saying (P^P)^P, where P is the number of protons. But that's just the same as P^(P*P). P^(P^P) would be much larger. Feb 16 '20 at 8:14
• Yeah, I meant the latter. Feb 16 '20 at 13:55

Given a sequence of $$a_0 ... a_{n-1}$$, all you have to do is find $$n$$ linearly independent functions $$f_0$$ through $$f_{n-1}$$. Then define a sequence $$c_i$$ by $$\sum_{i=0}^{n-1} c_i f_i(k)= a_k$$ for all $$k$$. In matrix form, that's $$M$$c = a where $$M$$ is a matrix whose entries are given by $$f_i(k)$$ (the two parameters $$i$$ and $$k$$ giving a two dimensional array of numbers), c is the sequence of coefficients, and a is the original given sequence. If the columns of $$M$$ are linearly independent, then a solution for c exists, giving a formula for a.

One can obtain Lagrange polynomials from a special case where $$f_i$$ are powers of $$k$$, but one can use exponential functions, trigometric functions (e.g. discrete Fourier transforms), etc.