Sum over k of r Choose k by s-kt Choose r by -1^k

From ProofWiki
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$.




Sources