# Sum over k of r Choose k by -1^r-k by Polynomial

## Theorem

Let $r \in \Z_{\ge 0}$.

Then:

$\displaystyle \sum_k \binom r k \left({-1}\right)^{r - k} P_r \left({k}\right) = r! \, b_r$

where:

$P_r \left({k}\right) = b_0 + b_1 k + \cdots + b_r k^r$ is a polynomial in $k$ of degree $r$.

## Proof 1

$\displaystyle \sum_k \binom r k \binom k n \left({-1}\right)^{r - k} = \delta_{n r}$

where $\delta_{n r}$ denotes the Kronecker delta.

Thus when $n \ne r$:

$\displaystyle \sum_k \binom r k \binom k n \left({-1}\right)^{r - k} = 0$

and so:

$\displaystyle \sum_k \binom r k \left({-1}\right)^{r - k} \left({c_0 \binom k 0 + c_1 \binom k 1 + \cdots + c_m \binom k m}\right) = c_r$

as the only term left standing is the $r$th one.

Choosing the coefficients $c_i$ as appropriate, a polynomial in $k$ can be expressed as a summation of binomial coefficients in the form:

$c_0 \dbinom k 0 + c_1 \dbinom k 1 + \cdots + c_m \dbinom k m$

Thus we can rewrite such a polynomial in $k$ as:

$b_0 + b_1 k + \cdots + b_r k^r$

Hence the result.

$\blacksquare$

## Proof 2

$\displaystyle \sum_{j \mathop = 1}^n \begin{pmatrix} {\dfrac { {x_j}^r} {\displaystyle \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \left({x_j - x_k}\right)} } \end{pmatrix} = \begin{cases} 0 & : 0 \le r < n - 1 \\ 1 & : r = n - 1 \\ \displaystyle \sum_{j \mathop = 1}^n x_j & : r = n \end{cases}$

Now we have:

 $\displaystyle \frac {\left({-1}\right)^k \dbinom n k} {n!}$ $=$ $\displaystyle \frac {\left({-1}\right)^k } {k! \left({n - k}\right)!}$ $\displaystyle$ $=$ $\displaystyle \frac {\left({-1}\right)^k } {\displaystyle \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \left({k - j}\right)}$