Sum over k of n+k Choose m+2k by 2k Choose k by -1^k over k+1/Proof 2

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Proof

Let:

$\ds S := \sum_k \binom {n + k} {m + 2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1}$

Then:

\(\ds \binom {2 k + 1} {k + 1}\) \(=\) \(\ds \binom {2 k} k \frac {2 k + 1} {k + 1}\) Factors of Binomial Coefficient
\(\ds \leadsto \ \ \) \(\ds \binom {2 k} k\) \(=\) \(\ds \binom {2 k + 1} {k + 1} \frac {k + 1} {2 k + 1}\)
\(\ds \) \(=\) \(\ds \binom {2 k + 1} k \frac {k + 1} {2 k + 1}\) Symmetry Rule for Binomial Coefficients


Also:

\(\ds \binom {n + k} {m + 2 k}\) \(=\) \(\ds \paren {-1}^{n + k - m - 2 k} \binom {-\paren {m + 2 k + 1} } {n + k - m - 2 k}\) Moving Top Index to Bottom in Binomial Coefficient
\(\ds \) \(=\) \(\ds \paren {-1}^{n - m - k} \binom {- m - 2 k - 1} {n - m - k}\)


Reassembling $S$:

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


Recall Sum over $k$ of $\dbinom {r - t k} k$ by $\dbinom {s - t \paren {n - k} } {n - k}$ by $\dfrac r {r - t k}$:

$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + s - t n} n$

Making the following substitutions:

$r \gets 1$
$t \gets -2$
$n \gets n - m$

we obtain:

\(\ds s + 2 \paren {n - m - k}\) \(=\) \(\ds - m - 2 k - 1\)
\(\ds \leadsto \ \ \) \(\ds s\) \(=\) \(\ds m - 2 n - 1\)
\(\ds \leadsto \ \ \) \(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k}\) \(=\) \(\ds \sum_{k \mathop \ge 0} \binom {1 + 2 k} k \binom {- m - 2 k - 1} {n - m - k} \frac 1 {1 + 2 k}\)


Thus:

\(\ds S\) \(=\) \(\ds \paren {-1}^{n - m} \sum_k \binom {1 + 2 k} k \binom {- m - 2 k - 1} {n - m - k} \frac 1 {1 + 2 k}\)
\(\ds \) \(=\) \(\ds \paren {-1}^{n - m} \binom {1 + \paren {m - 2 n - 1} + 2 \paren {n - m} } {n - m}\)
\(\ds \) \(=\) \(\ds \paren {-1}^{n - m} \binom {- m} {n - m}\)
\(\ds \) \(=\) \(\ds \binom {n - 1} {n - m}\) Negated Upper Index of Binomial Coefficient
\(\ds \) \(=\) \(\ds \binom {n - 1} {m - 1}\) Symmetry Rule for Binomial Coefficients

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_over_k_of_n%2Bk_Choose_m%2B2k_by_2k_Choose_k_by_-1%5Ek_over_k%2B1/Proof_2&oldid=512277"