Derive coefficients for equivalence of polynomial involving falling factorials

combinatoricsfactorial

I am presently working on a problem that involves use of the falling factorials:$^\dagger$

$$(m-k)_r \equiv (m-k) (m-k-1) (m-k-2) \cdots (m-k-r+1).$$

Taking $m$ as fixed, it is easy to see that $(m-k)_r$ is a polynomial of degree $r$ in $k$. I would like to use this fact to identify the coefficients in the following polynomial equivalence:

$$k^r = \sum_{i=0}^r a_{r,i} \cdot (m-k)_i.$$

Each of the polynomials in the summand is a polynomial with degree no greater than $r$, and so there is clearly an equivalence of this kind (and we clearly have $a_{r,r} = (-1)^r$ to get the correct coefficient on the final polynomial term). However, I am having trouble combining polynomial results for the falling factorial to find the expression for the coefficients $a_{r,i}$.

Question: What is the expression for the coefficient terms $a_{r,i}$? How is this best derived?

$^\dagger$ I am aware of the ambiguity of notation in this area, but in this question I am using the symbol $(m-k)_r$ to denote the falling factorial. Please give answers that adopt the same notation.

Best Answer

We use D.E. Knuth's preferred notation $k^{\underline r}=k(k-1)\cdots(k-r+1)$ to denote the falling factorials and consider \begin{align*} k^r=\sum_{j=0}^r a_{r,j}(m-k)^{\underline{j}}\tag{1} \end{align*}

Substituting $k$ with $m-k$ gives \begin{align*} \sum_{j=0}^r \color{blue}{a_{r,j}}k^{\underline{j}}&=(m-k)^r\tag{2}\\ &=\sum_{p=0}^r\binom{r}{p}(-1)^pk^pm^{r-p}\tag{3}\\ &=\sum_{p=0}^{r}\binom{r}{p}(-1)^p\sum_{q=0}^p{p \brace q}k^{\underline{q}}m^{r-p}\tag{4}\\ &=\sum_{0\leq q\leq p\leq r}(-1)^p\binom{r}{p}{p \brace q}k^{\underline{q}}m^{r-p}\tag{5}\\ &=\sum_{q=0}^{r}\left(\color{blue}{\sum_{p=q}^{r}\binom{r}{p}{p \brace q}(-1)^pm^{r-p}}\right)k^{\underline{q}}\tag{6} \end{align*}

Comment:

  • In (3) we apply the binomial theorem.

  • In (4) we use the representation of powers of $k$ as Stirling numbers of the second kind.

  • In (5) we use a somewhat more convenient representation of the index range as preparation for the next step.

  • In (6) we exchange the sums from (4).

Coefficient comparison of (2) and (6) gives \begin{align*} \color{blue}{a_{r,q}=\sum_{p=q}^{r}\binom{r}{p}{p \brace q}(-1)^pm^{r-p}\qquad\qquad 0\leq q\leq r}\\ \end{align*}

Related Question