3
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ What if you think of it in terms of inverting certain matrices? :) $\endgroup$
    – Wolfgang
    Aug 7, 2021 at 19:15
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Falling_and_rising_factorials gives formulas for converting between factorial polynomials and ordinary polynomials $\endgroup$
    – saulspatz
    Aug 7, 2021 at 19:16
  • $\begingroup$ @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. $\endgroup$ Aug 8, 2021 at 1:34
  • $\begingroup$ @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? $\endgroup$ Aug 8, 2021 at 1:41
  • 1
    $\begingroup$ 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) $\endgroup$
    – Sil
    Aug 8, 2021 at 15:06

1 Answer 1

2
$\begingroup$

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.

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

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .