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

3 Answers

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

---

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.

$\endgroup$ 4 $\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$ 3 $\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

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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