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

From ProofWiki
Jump to navigation Jump to search

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

From the corollary to Sum over $k$ of $\dbinom r k \dbinom {s + k} n \left({-1}\right)^{r - k}$:

$\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

From Summation of Powers over Product of Differences:

$\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)}\)