Sum over k of r Choose k by s+k Choose n by -1^r-k

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $s \in \R, r \in \Z_{\ge 0}, n \in \Z$.

Then:

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

where $\dbinom r k$ etc. are binomial coefficients.


Corollary

$\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

The proof proceeds by induction on $r$.

For all $r \in \Z_{>0}$, let $\map P r$ be the proposition:

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


Basis for the Induction

$\map P 0$ is the case:

\(\ds \sum_k \binom 0 k \binom {s + k} n \paren {-1}^{0 - k}\) \(=\) \(\ds \delta_{0 k} \binom {s + k} n \paren {-1}^{0 - k}\) Zero Choose n
\(\ds \) \(=\) \(\ds \binom s n\) All terms vanish but for $k = 0$
\(\ds \) \(=\) \(\ds \binom s {n - 0}\)

Thus $\map P 0$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $\map P m$ is true, where $m \ge 0$, then it logically follows that $\map P {m + 1}$ is true.


This is the induction hypothesis:

$\ds \sum_k \binom m k \binom {s + k} n \paren {-1}^{m - k} = \binom s {n - m}$


from which it is to be shown that:

$\ds \sum_k \binom {m + 1} k \binom {s + k} n \paren {-1}^{m + 1 - k} = \binom s {n - \paren {m + 1} }$


Induction Step

This is the induction step:

\(\ds \) \(\) \(\ds \sum_k \binom {m + 1} k \binom {s + k} n \paren {-1}^{m + 1 - k}\)
\(\ds \) \(=\) \(\ds \sum_k \paren {\binom m k + \binom m {k - 1} } \binom {s + k} n \paren {-1}^{m + 1 - k}\) Pascal's Rule
\(\ds \) \(=\) \(\ds \sum_k \binom m k \binom {s + k} n \paren {-1}^{m + 1 - k} + \sum_k \binom m {k - 1} \binom {s + k} n \paren {-1}^{m + 1 - k}\)
\(\ds \) \(=\) \(\ds -\sum_k \binom m k \binom {s + k} n \paren {-1}^{m - k} + \sum_k \binom m {k - 1} \binom {s + k} n \paren {-1}^{m + 1 - k}\)
\(\ds \) \(=\) \(\ds -\binom s {n - m} + \sum_k \binom m {k - 1} \binom {s + k} n \paren {-1}^{m + 1 - k}\) Induction Hypothesis
\(\ds \) \(=\) \(\ds -\binom s {n - m} + \sum_k \binom m {k - 1} \paren {\binom {s + k - 1} n + \binom {s + k - 1} {n - 1} } \paren {-1}^{m + 1 - k}\) Pascal's Rule
\(\ds \) \(=\) \(\ds -\binom s {n - m} + \sum_k \binom m {k - 1} \binom {s + k - 1} n \paren {-1}^{m - \paren {k - 1} }\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds \sum_k \binom m {k - 1} \binom {s + k - 1} {n - 1} \paren {-1}^{m - \paren {k - 1} }\)
\(\ds \) \(=\) \(\ds -\binom s {n - m} + \sum_k \binom m k \binom {s + k} n \paren {-1}^{m - k} + \sum_k \binom m k \binom {s + k} {n - 1} \paren {-1}^{m - k}\) Translation of Index Variable of Summation
\(\ds \) \(=\) \(\ds -\binom s {n - m} + \binom s {n - m} + \binom s {n - 1 - m}\) Induction Hypothesis
\(\ds \) \(=\) \(\ds \binom s {n - \paren {m + 1} }\) simplifying

So $\map P m \implies \map P {m + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

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

for all $s \in \R, r \in \Z_{\ge 0}, n \in \Z$.

$\blacksquare$


Sources