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

3 Answers 3

up vote 4 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

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
    
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 yesterday
    
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 yesterday

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

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.