<s>[INST] Surprising behaviour of polynomial that generates the series 1,2,4,8,...2^(k-1) 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?
 [/INST] 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.
</s>