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

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
add comment

2 Answers

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
add comment

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

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
add comment

Your Answer


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.