Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose $f$ is an unknown polynomial of degree $n$ (in one indeterminate) but the sequence $\{ f(k) \}_{k \in \mathbb{N}}$ is given. It is a nice exercise to show that one needs only the first $n+1$ terms of the sequence to determine the coefficients of $f$. That is, simply solve the matrix equation $A\mathbf{x} = b$, where $\mathbf{b} = (f(0), \dots, f(n))^{\top}$, $A$ is the Vandermonde matrix of $(i^{j})_{i,j = 0, \dots, n}$ and $\mathbf{x} = (c_{0}, \dots, c_{n})^{\top}$ (the unknown coefficients of $f$).

Question: Is there a closed form expression for the coefficients of a finite degree polynomial $f$ in terms of the sequence $\{ f(k) \}_{k \in \mathbb{N}}$ that doesn't involve matrix inversion or differentiation or explicitly calculating the polynomial in question?

(Motivation) The Ehrhart polynomial counts the number of integer lattice points intersecting a dilate of a polytope and can be calculated by the residue of an associated complex rational function (see M. Beck's articles on the subject). Some of the coefficients of the Ehrhart polynomial can be related to an $n$-volume, a relative area and the euler characteristic of said polytope. However, computing coefficients of the Ehrhart polynomial is not a particularly easy task. Having simple formulas for them, say in terms of the residues above would be nice to have at one's disposal. A reasonable starting point is answering the question above.

Thanks!

share|improve this question

1 Answer 1

up vote 6 down vote accepted

Yes; you can take finite differences. Let $\Delta f(x) = f(x+1) - f(x)$.

Theorem: $$f(x) = \sum_{k=0}^{n} \Delta^k f(0) {x \choose k}$$

where ${x \choose k}$ is the polynomial $\frac{x(x-1)...(x-(k-1))}{k!}$.

Proof. Observe that $\Delta {x \choose k} = {x \choose k-1}$. Take $k$ finite differences of both sides and set $x = 0$.

In practice, this means you can work out what $f$ is by writing down a finite difference table. This is really easy to do by hand, and then the top row of the table tells you what the coefficients $\Delta^k f(0)$ are above. In linear algebra terms, what we are doing is using a basis with respect to which the matrix $A$ is upper-triangular, and this makes life much easier.

There is also a known explicit formula for the inverse of $A$ which is equivalent to the Lagrange interpolation formula. This is sometimes useful for theoretical reasons (e.g. as a way to control the behavior of the interpolation polynomial or to deduce certain identities).


You can extract a "closed form" for the coefficients of $f$ using either of the two methods above, although I think using finite differences is slightly nicer. We have

$${x \choose k} = \frac{1}{k!} \sum_{i=0}^{k} s(k, i) x^i$$

where $s(k, i)$ are the Stirling numbers of the first kind. This gives

$$[x^i] f(x) = \sum_{k=i}^{n} \Delta^k f(0) \frac{s(k, i)}{k!}$$

where

$$\Delta^k f(0) = \sum_{j=0}^{k} (-1)^{k-j} {k \choose j} f(j).$$

So $[x^i] f(x) = \sum_{j=0}^{n} a_{i,j} f(j)$ where

$$a_{i,j} = \sum_{k=j}^{n} (-1)^{k-j} {k \choose j} \frac{s(k, i)}{k!}.$$

I don't know whether this sum can be simplified further.

share|improve this answer

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.