Finding closed form for polynomial coefficients given evaluated values I have a function (in the programming sense) p induced by a polynomial 
$$a_n x^n + \ldots + a_1 x + a_0 $$ of given degree $n$.
Now I would like to find this polynomial's coefficients $a_i$ in order to integrate this polynomial algebraically. I can evaluate p for arbitrary real $x$. Now, obviously, we have $a_0 = p(0)$.
And we get a system of equations evaluating p at $1$, $2$, $\ldots$
But I can't quite figure out a closed form for these coefficients given those evaluated values.
What I would like is something like
$$a_i = \sum\limits_{j = 0}^n c^{(i)}_j p(j)$$
or a recursive formula.
 A: Perhaps this is similar to the Lagrange polynomial case.  
The Chebyshev polynomials, $T_0, \cdots T_n$ are mutually orthogonal with inner product taken as a sum over the zeros of $T_{n+1}$.  The zeros are easily calculated because $T_k(\cos \theta) = \cos k\theta $ (here $x = \cos \theta$).  The polynomials are also easily obtained:
$$ T_0 = 1, T_1(x) = x, T_{n+1}(x) = 2x T_{n}(x) - T_{n-1}(x) $$
If interested in differentiation, the derivative of each $T_k$ is simply $k$ time the corresponding Chebyshev polynomial of the second kind (see Wikipedia).
For your problem if you precompute the first $n$ Chebyshev polynomials and save their coefficients, evaluate you $p(x)$ at the $n+1$ zeros and take inner product against the $n+1$ polynomials $ T_0, \cdots, T_{n} $ you quickly obtain coefficients for $p$ in the basis $T_0, \cdots, T_n$.  Then use you pre-computed table to give you the coefficients for $p(x)$ in terms of $1, x, \cdots, x^n$.  You will need to calculate the norms of each $T_0, \cdots, T_n $ under the inner product - I can't remember if there is a simple form for it or not.
Postscript:  I checked.  The sum inner product over the $n+1$ zeros of $T_{n+1}$, $\omega_0, \cdots \omega_n$ satisfies $$\langle T_i, T_j \rangle = \sum_{r=0}^n T_i(\omega_r)T_j(\omega_r) = \left\{ \array{0 & i\neq j \\ n+1 & i=j=0 \\ (n+1)/2 & i=j  > 0} \right. $$
