# Integral interpolation by polynomial

This question arises from a discussion with my friends on a commonly encountered IQ test questions: "What's the next number in this series 2,6,12,20,...". Here a "number" usually means an integer. I was wondering whether there is a systematical way to solve such problems.Let us call a point on a plane integer point if all the components of it are integers. I want to know the following:

Give a finite set of integer points, Can we always find a corresponding polynomial that passes all these points and maps integers to integers?

-
Presumably the points are supposed to have different x coordinates ... –  Ricky Demer Apr 28 '11 at 21:46
Perhaps you are referring to Newton Polynomials? –  Alex R. Apr 28 '11 at 22:10
Somewhat related question: mathoverflow.net/questions/4442/… –  quid May 3 '11 at 13:39

Let the points be $(x_j, y_j), j=1\ldots n$. If the $x_j$ are consecutive, the Lagrange interpolating polynomial will take integers to integers: easy proof by induction, using the difference operator $\Delta(p)(x) = p(x+1) - p(x)$. If not, choose arbitrary integers for the $y$ values to fill in the gaps.

-
Alternatively, if the $x_i$ are consecutive, you can express the values of the Lagrange polynomials as binomial coefficients (which are integers). –  Joël Cohen Apr 29 '11 at 1:19

Just to make a few comments:

1) As noted, If we have a list of values $a_0,a_1,\cdots, a_n$ of integers then there is a (unique) polynomial $f(t)$ of degree no more than $n$ with integer coefficients which maps integers to integers and such that $f(k)=k$ for $0 \le k \le n$.

2) There is a method involving the differences and differences of the differences etc. which reveals $f(n)$ as an integer linear combination of the polynomials $\binom{t}{j}$ for $0 \le j \le n$. Furthermore, the polynomials of this form are exactly the polynomials sending integers to integers. These (specialized) Newton Polynomials are very similar to the Taylor series which uses the basis $\frac{t^k}{k!}$

3) If you just want the next term (as predicted by this polynomial) then you don't need to explicitly find the polynomial, just extend the differences. Many test takers realize this. $$\begin{matrix}2&\ &6&\ &12&\ &20&\ &\mathbf{30}\\\ &4&&6&&8&&\mathbf{10}&\\\ &&2&&2&&\mathbf{2}&&\end{matrix}$$ corresponds to $f(n)=2+4n+2\binom{n}{2}=n^2+3n+2$

4) There is also a polynomial of degree 3 that gives $2,6,12,20,\mathbf{2011}$ so there is no unique extension.

5) If the given sequence is $1,2,4,8,?$ then the polynomial interpolation gives $15$ next from $\binom n0+\binom n1+\binom n2+\binom n3$ although most tests would favor another continuation.

-
On 5, the polynomial interpolation is actually a very useful sequence, the so-called "cake numbers". –  Charles May 3 '11 at 18:28
and 1,2,4,8,16,31 are 4 dimensional cake numbers... –  Aaron Meyerowitz May 3 '11 at 19:23
Conway and Guy show how to extend the method of differences in different directions (literally) in "The Book of Numbers" and deal with some non-polynomial sequences. –  Mark Bennet May 3 '11 at 19:33
Something feels wrong here - in (1) I presume you mean $f(k)=a_k$, and in this case the polynomial doesn't always have integer coefficients - for instance, as you note, ${n\choose 2} = \frac{n(n-1)}2$ is always an integer, but its coefficients certainly aren't integers. –  Steven Stadnicki Aug 18 '14 at 15:34
It does not give a polynomial like $a_o+a_1n+a_2n^2\cdots$ with $a_0,a_1,a_2$ integers but it does give such of the form $a_0+a_1\binom{n}1+a_2\binom{n}2\cdots$ and these are exactly the polynomials which map integers to integers. In your case starting from $0,0,1,3,6,10$ we discover after taking differences $0,0,1,3,6,10,\mathbf{15}$ from shifted rows $0,1,2,3,4,\mathbf{5}$ then $1,1,1,1,\mathbf{1}$ then $0,0,0,0,0,0,\cdots.$ So we get the next term(s) and, if desired, the formula $0+0\binom{n}1+1\binom{n}2.$ –  Aaron Meyerowitz Aug 18 '14 at 21:07

It's a topic I liked to cover when I was still teaching junior-level Algebra, even if it didn't fit in well with the other topics. You start with a function defined on the set of integers from $0$ to $n$ inclusive, and end with a polynomial of degree $\le n$ that agrees at those $n+1$ points, and if the values you started with are integers, your function always sends integers to integers. You take successive differences, as indicated by Robert Israel above, and then you list $f(0)$, $\Delta f(0)$, $\Delta^2f(0)$, up to $\Delta^n$, and use these as coefficients, which you multiply to $C_0(x)=1$, $C_1(x)=x$, $C_2(x)=x(x-1)/2$, etc., the binomial polynomials. Your assignment is to try it out for a few examples, and then prove that the method works.

-
I like to work this in when I can. It is nice to compare it to Taylor series: $f(x)=\sum D^nf\ (0)\frac{x^n}{n!}$ vs $f(x)=\sum \Delta^nf\ (0)\frac{(x)_n}{n!}$ Where $(x)_3=x(x-1)(x-2)$ is the falling factorial. –  Aaron Meyerowitz May 3 '11 at 7:10