If we have an arbitrary polynomial, $P:\mathbb{N}\to\mathbb{R}$, how can we express $P(x)$ as a linear combination of $\binom{x}{k}$. Is there any easy formula for finding this expression.
I am pretty sure a unique expression is guaranteed to exist because we can start with the highest degree term, let's say $a_nx^n$, and just subtract $n!a_n\binom{x}{n}$ to get an $n-1$ degree polynomial and then keep on repeating this process.
I think the most essential step is finding an expression for $x^n=\sum_{k=0}^n a_k\binom{x}{k}$. I have found by brute force that
$$x^0=\binom{x}{0}$$
$$x^1=\binom{x}{1}$$
$$x^2=2\binom{x}{2}+\binom{x}{1}$$
$$x^3=6\binom{x}{3}+6\binom{x}{2}+\binom{x}{1}$$
I am not sure what the pattern is. It kind of looks like pascal's triangle rows (e.g. $1,2,1$ and $1,6,6,1$ is similar to $1,3,3,1$). However, finding expressions for higher power terms is pretty exhaustive, so I was wondering if there is an easier solution?
Best Answer
We have that (identity was noted in the comments)
$$x^n = \sum_{k=0}^n {x\choose k} {n\brace k} k!$$
This may be seen for $x$ a positive integer and since both sides are polynomials in $x$ (recall that ${x\choose k} = x^{\underline{k}}/k!$) it then holds for all i.e. complex $x.$
For a combinatorial proof, consider a vector of $n$ elements where each element may take on $x$ different values. Clearly we have $x^n$ such vectors. On the other hand we may determine a particular vector by choosing first the $k$ different values that appear, for a factor of ${x\choose k}$ and combine this with a partition of the $n$ slots of the vector into $k$ non-empty sets, for a factor of ${n\brace k}$. The sets in the partition may be matched to the values in $k!$ ways, thus completing the alternate count. We have the special case of $n=0$ which yields one as required.
For an algebraic proof write the RHS as follows:
$$\sum_{k=0}^n {x\choose k} \; k! \; n! [z^n] \frac{(\exp(z)-1)^k}{k!} \\ = n! [z^n] \sum_{k=0}^n {x\choose k} (\exp(z)-1)^k$$
Now if $n\gt x$ we may lower the upper limit of the sum to $x$ as ${x\choose k}$ is zero when $n\ge k\gt x.$ On the other hand if $n\lt x$ we may raise the upper limit to $x$ since $(\exp(z)-1)^k = z^k + \cdots$ and there is no contribution to $[z^n]$ when $x\ge k\gt n.$ We get
$$n! [z^n] \sum_{k=0}^x {x\choose k} (\exp(z)-1)^k = n! [z^n] \exp(xz) = x^n$$
as claimed.