4
$\begingroup$

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!

  • 1
    Take backward differences and let t = 0. It's essentially the same as computing Taylor series coefficients.2011-02-18
  • 0
    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.2011-02-20
  • 0
    @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!2012-01-06
  • 0
    @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.2012-01-06

1 Answers 1