Sum over k of r Choose k by -1^r-k by Polynomial
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 1
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$
Proof 2
From Summation of Powers over Product of Differences:
- $\ds \sum_{j \mathop = 1}^n \begin {pmatrix} {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } } \end {pmatrix} = \begin {cases} 0 & : 0 \le r < n - 1 \\ 1 & : r = n - 1 \\ \ds \sum_{j \mathop = 1}^n x_j & : r = n \end {cases}$
Now we have:
\(\ds \frac {\paren {-1}^k \dbinom n k} {n!}\) | \(=\) | \(\ds \frac {\paren {-1}^k} {k! \paren {n - k}!}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {-1}^k} {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {k - j} }\) |
This theorem requires a proof. In particular: in progress You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |