4
$\begingroup$

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) = \frac{n^2-n+2}{2}$ then $f(4) = 7$

For $1,2,4,8$, $f(n) = \frac{n^3-3n^2+8n}{6}$ and $f(5) = 15$

For $1,2,4,8,16$, $f(n) = \frac{n^4-6n^3+23n^2-18n}{24}$ and $f(6)=31$

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

For $1,2,4,8,16,32,64$, $f(n) = \frac{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 \cdot f(1)-1$

For $1,2$, $f(n) = n$ and $f(3) = 3$. $f(3) = 2 \cdot f(2)-1$

This suggests that $f(k+1) = 2 \cdot 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?

$\endgroup$
3
  • 3
    $\begingroup$ 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.) $\endgroup$
    – dvitek
    Oct 16, 2010 at 19:03
  • 4
    $\begingroup$ These observations are part of the calculus of finite differences: see en.wikipedia.org/wiki/Calculus_of_finite_difference for more information $\endgroup$ Oct 16, 2010 at 19:18
  • $\begingroup$ 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.) $\endgroup$ Oct 16, 2010 at 20:46

2 Answers 2

15
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 16, 2010 at 21:41
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I like this construction because it demonstrates that, for a finite field $F$, all of the functions $F \to F$ are polynomial functions. $\endgroup$
    – Michael
    Mar 28, 2011 at 5:52
  • $\begingroup$ 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. $\endgroup$
    – Michael
    Mar 28, 2011 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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