6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ A friend bet me at school that this was impossible. $\endgroup$ – Francis Davey Feb 16 at 6:54
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – PatrickT Feb 16 at 7:58
  • 2
    $\begingroup$ @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. $\endgroup$ – Acccumulation Feb 16 at 8:14
  • $\begingroup$ Yeah, I meant the latter. $\endgroup$ – PatrickT Feb 16 at 13:55
11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Note that nonpolynomial sequences like $1,2,4,8,16,32,64,\dots$ are not predictable with this method. $\endgroup$ – Berci Feb 15 at 18:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Brondahl Feb 16 at 7:38
  • 1
    $\begingroup$ @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) $\endgroup$ – Brondahl Feb 16 at 7:38
  • 1
    $\begingroup$ @Brondahl I know, nevertheless I found it worth to make it a comment. $\endgroup$ – Berci Feb 16 at 7:40
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.