Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

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

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
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 '11 at 1:19
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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