# Computing the Coefficients of a Polynomial in the Binomial Basis

Let $f(t) = \sum_{i = 0}^{n} c_i \ t^i$ be a degree $n$ polynomial. In the binomial basis, we can write $f(t) = \sum_{k = 0}^{n} h_k \ \binom{t + n - k}{n}$. Using the calculus of finite differences, I can prove that the coefficient $c_i$ can be computed from $\{ h_0, \dots, h_n \}$ by the equation $$c_i = \frac{1}{n!} \sum_{k = 0}^{n} \left( \sum_{\ell = i}^{n} s(n,\ell) \binom{\ell}{i} (n-k)^{\ell - i} \right) h_k,$$ where $s(n,\ell)$ is the (signed) Stirling Number of the first kind. I'd like to have the inverse formula. That is, how does one compute $h_k$ as a function of $\{ c_0, \dots, c_n \}$?

Thanks.

Update: Thanks to the suggestions below, I can prove \begin{eqnarray} f(t) = \sum_{i = 0}^{n} \sum_{k = 0}^{i} \sum_{j = k}^{i} c_{i} k! \binom{i}{j} r^{i-j} S(j,k) \binom{t - r}{k} \end{eqnarray} for any positive integer $r$. I'm not sure how to convert this into an expansion in the basis $\left \{ \binom{t + n - k}{k} \right\}$ or $\left\{ \binom{t + n -k}{n} \right\}$, since I believe that $r$ cannot depend on $k$. Any ideas are certainly appreciated!

-
Take backward differences and let t = 0. It's essentially the same as computing Taylor series coefficients. –  Qiaochu Yuan Feb 18 '11 at 16:39
Thanks. I'll try that. –  user02138 Feb 18 '11 at 16:40
I haven't had the time to think through this all the way through myself, but I was going to try choosing a different $r$ for each value of $i$ in $\sum_{i=0}^n c_i t^i$. You would need $r$ to range from $0$ to $-n$ to cover all possible values of $t+n-k$. Then maybe you could combine these and reindex to get the basis change you want. –  Mike Spivey Feb 20 '11 at 14:49
@Srivatsan, it is great that you tidy up posts and tags, but remember to do this a couple of posts at a time only, as otherwise you get the front page covered with old questions and force the new ones to be bumped off. (Also, while I also cringe a bit when I see things like x_{n}, there is really no point in editing that into x_n—in particular, both forms are correct! –  Mariano Suárez-Alvarez Jan 6 '12 at 6:32
@Mariano Oops, sorry about flooding the main page. I got carried away; I'll stop for now. // The reason for the edit was not really x_{n} vs. x_n (that was just a bonus) but to remove the [algebra] tag and replace it by something else. –  Srivatsan Jan 6 '12 at 6:35

Since $\binom{t+n-k}{k} = \frac{(t+n-k)!}{k! (t+n-2k)!} = \frac{(t+n-k)^{\underline{k}}}{k!}$, your problem reduces to how to find the coefficients $s_0, s_1, \ldots, s_n$ such that $$t^n = \sum_{k=0}^n s_k (t+n-k)^{\underline{k}}.$$
If you had $n-k = 0$, this would involve the Stirling numbers of the second kind $S(n,k)$ via the formula $$t^n = \sum_{k=0}^n S(n,k) t^{\underline{k}}.$$
$$t^n = \sum_{k=0}^n S(n,k;r) (t-r)^{\underline{k}},$$ and $$S(n,k;r) = \sum_{j=k}^n \binom{n}{j} r^{n-j} S(j,k),$$ where $S(j,k)$ is (again) a Stirling number of the second kind. Note that the second equation is dual (as it should be!) to the expression inside the parentheses in your question.