Sum over k of r Choose k by s-kt Choose r by -1^k
Jump to navigation
Jump to search
Theorem
Let $r \in \Z_{\ge 0}$.
Then:
- $\ds \sum_k \binom r k \binom {s - k t} r \paren {-1}^k = t^r$
where $\dbinom r k$ etc. are binomial coefficients.
Proof
From Sum over $k$ of $\dbinom r k \paren {-1}^k$ by Polynomial:
- $\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$.
This theorem requires a proof. 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. |
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: $(35)$