Take the 2-minute tour ×

Consider the generating function f(n) that produces the following values:

f(1) = 1

f(2) = 2

f(3) = 4

Obviously these values can be generated by f(n)= 2^(n-1).

These values can equally well be generated by f(n) = (n^2-n+2)/2, a second order polynomial.

Many (all?) integer series f(k), where k = 1,2,3,..K-1,K can be generated by a polynomial of order K-1.

The integer series 2^(n-1), where n = 1,2,3...K can also be generated by a polynomial of order K-1.

The following interesting thing happens.

If we describe the series 1,2,4 by f(n) = (n^2-n+2)/2 then f(4) = 7

For 1,2,4,8, f(n) = (n^3-3n^2+8n)/6 and f(5) = 15

For 1,2,4,8,16, f(n) = (n^4-6n^3+23n^2-18n) /24 and f(6)=31

For 1,2,4,8,16,32, f(n) = (n^5-10n^4+55n^3-110n^2+184n)/120 and f(7)=63

For 1,2,4,8,16,32,64, f(n) = (n^6-15n^5+115n^4-405n^3+964n^2-660n+720)/720) and f(8)=127

I have verified this till order 14.

Lets add the series "1" and "1,2" for completeness:

For 1, f(n) = 1 and f(2) =1. f(2) = 2* f(1)-1

For 1,2 f(n) = n and f(3) = 3. f(3) = 2 * f(2)-1

This suggests that f(k+1) = 2 * f(k) -1 when f(n) is the k-1 th order polynomial function that generates the values 1,2,4,...2^(k-1).

This raises the question if this is true for all integer series of this type and if so, how to prove it. I hope that I am not overlooking the obvious.

Another observation is that if you write the polynomials that describe the series 1,2,4,8... in a fractional form where all coefficients of n^k in the numerator are integers, then the denominator always seems to be

(K-1)! (1,1,2,6,24,120 etc.)

Can anybody shine some light on these observations please? Thanks a lot in advance

Bob Andriesse

share|improve this question
You write, "Many (all?) integer sequences $f(k)$ where $k = 1, 2, \cdots, n$ can be generated by a polynomial of degree $k-1$." I believe you mean $n-1$, and an explicit form for this polynomial is given by the Lagrange interpolation theorem. (The Wikipedia article on Lagrange polynomials has more details.) –  drvitek Oct 16 '10 at 19:03
These observations are part of the calculus of finite differences: see en.wikipedia.org/wiki/Calculus_of_finite_difference for more information –  Richard Borcherds Oct 16 '10 at 19:18
I remember seeing the original poster's observation as an exercise on an IMO shortlist or in a similar source. Any idea where it was? (Not that it would really matter.) –  darij grinberg Oct 16 '10 at 20:46

2 Answers 2

The second observation is true of all polynomials which interpolate an integer sequence. This is the subject of the method of finite differences, the "main theorem" of which is this: if we define $\Delta f(n) = f(n+1) - f(n)$, then the unique polynomial of degree $n$ which interpolates the sequence $f(0), f(1), ... f(n)$ is

$$f(x) = \sum_{i=0}^{n} \Delta^i f(0) {x \choose i}.$$

(You should think of this as analogous to Taylor expansion. The proof uses the identity $\Delta {x \choose i} = {x \choose i-1}$.) In particular, the $\Delta^i f(0)$ are all integer if and only if $f(0), f(1), ... f(n)$ are all integers, which is the second pattern you observe.

For the powers of $2$ we have $\Delta^i f(0) = 1$ for $1 \le i \le n$, which gives

$$f(x) = \sum_{i=0}^{n} {x \choose i}.$$

It follows that $f(n+1) = 2^{n+1} - 1$, which I think is the first pattern you observe.

share|improve this answer
Btw, it's worth mentioning that the above $f(x)$ counts the numbers of connected components of $\mathbb{R}^n$ minus $x$ hyperplanes in generic position. –  Pietro Majer Oct 16 '10 at 21:41


Well, yes, all of them. Given distinct numbers $a_1, \ldots, a_n$, the polynomial $$p_i(X)= \prod_{j\neq i}\frac{X-a_j}{a_i - a_j}$$ takes value $1$ at $a_i$ and $0$ at $a_j$ for all $j \neq i$. A linear combination of those gives you your desired outcome.

share|improve this answer
I like this construction because it demonstrates that, for a finite field $F$, all of the functions $F \to F$ are polynomial functions. –  Michael Mar 28 '11 at 5:52
More generally, for $(a_1,\ldots,a_n) \in F^n$, the polynomial $p_{(a_1,\ldots,a_n)} = \prod_{i=1}^n \left(\prod_{a \neq a_i} \frac{X_i - a}{a_i - a} \right)$ in $F[X_1,\ldots,X_n]$ evaluates to $1$ or $0$ according as $(X_1,\ldots,X_n)$ is put equal to $(a_1,\ldots,a_n)$ or otherwise. Taking linear combinations, it follows that every function $F^n \to F$ arises from polynomial in $n$ variables. –  Michael Mar 28 '11 at 5:54

Your Answer


