# Expressing polynomials as a linear combination of $\binom{x}{k}$

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?

• What if you think of it in terms of inverting certain matrices? :) Aug 7, 2021 at 19:15
• en.wikipedia.org/wiki/Falling_and_rising_factorials gives formulas for converting between factorial polynomials and ordinary polynomials Aug 7, 2021 at 19:16
• @Wolfgang I'm not sure. I'm not very adept with advanced linear algebra, so if you could give me more hints, I might be able to formulate a solution. Aug 8, 2021 at 1:34
• @saulspatz Looking at the wikipedia page you provided, I found $x^n=\sum_{k=0}^n S(n,k)\binom{x}{k}k!$. However, I was not able to find a proof of this. Do you know how to prove the statement? Aug 8, 2021 at 1:41
• If $P(x)=c_0+c_1x+\dots+c_nx^n$ then you can write $P(x)=a_0+a_1\binom{x}{1}+\dots+a_n\binom{x}{n}$ where $a_i = i!\sum_{k=i}^{n}{k\brace i}c_k$ where ${k\brace i}$ are stirling numbers of second kind - I mentioned it in this post. (it follows from the identity you have found, just mentioning it to link with the existing post)
– Sil
Aug 8, 2021 at 15:06

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.

• Both of these are proofs are amazing. Great job, and thank you! Aug 9, 2021 at 1:00