Sum over k of r Choose k by s+k Choose n by -1^r-k/Corollary
Jump to navigation
Jump to search
Corollary to Sum over $k$ of $\dbinom r k \dbinom {s + k} n \paren {-1}^{r - k}$
Let $r \in \Z_{\ge 0}, n \in \Z$.
Then:
- $\ds \sum_k \binom r k \binom k n \paren {-1}^{r - k} = \delta_{n r}$
where $\delta_{n r}$ is the Kronecker delta.
Proof
From Sum over $k$ of $\dbinom r k \dbinom {s + k} n \paren {-1}^{r - k}$:
- $\ds \sum_k \binom r k \binom {s + k} n \paren {-1}^{r - k} = \binom s {n - r}$
which holds for $s \in \R, r \in \Z_{\ge 0}, n \in \Z$.
Setting $s = 0$:
- $\ds \sum_k \binom r k \binom k n \paren {-1}^{r - k} = \binom 0 {n - r}$
We have by definition of binomial coefficient that:
- $\dbinom 0 0 = 1$
and:
- $\forall n \in \Z_{\ne 0}: \dbinom 0 n = 0$
So, using Iverson's convention:
- $\dbinom 0 {n - r} = \sqbrk {n = r}$
The result follows by definition of the Kronecker delta.
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: $(33)$