## Integral interpolation by polynomial

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 2011 at 21:46

1
Perhaps you are referring to Newton Polynomials? – Alex R. Apr 28 2011 at 22:10

2
en.wikipedia.org/wiki/Lagrange_polynomial – J.C. Ottem Apr 28 2011 at 23:04
Somewhat related question: mathoverflow.net/questions/4442/… – quid May 3 2011 at 13:39

## 3 Answers

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.

-

1
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 2011 at 1:19

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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 2011 at 18:28
and 1,2,4,8,16,31 are 4 dimensional cake numbers...  – Aaron Meyerowitz May 3 2011 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 2011 at 19:33

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 2011 at 7:10
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 31, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9151257276535034, "perplexity_flag": "head"}