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

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Then:

$\ds \sum_k \binom r k \paren {-1}^{r - k} \map {P_r} k = r! \, b_r$

where:

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


Proof

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

$\ds \sum_k \binom r k \binom k n \paren {-1}^{r - k} = \delta_{n r}$

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


Thus when $n \ne r$:

$\ds \sum_k \binom r k \binom k n \paren {-1}^{r - k} = 0$

and so:

$\ds \sum_k \binom r k \paren {-1}^{r - k} \paren {c_0 \binom k 0 + c_1 \binom k 1 + \cdots + c_m \binom k m} = 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$

Since each $c_m \dbinom k m$ is a polynomial of degree $m$, it follows that the only one with a non-zero degree $r$ term is $c_r \dbinom k r$.

The coefficient of $k^r$ in $c_r \dbinom k r$ must be equal to $b_r$, that is:

$b_r = \dfrac {c_r}{r!}$

Hence the result.

$\blacksquare$


Sources