Summation from k to m of 2k-1 Choose k by 2n-2k Choose n-k by -1 over 2k-1

From ProofWiki
Jump to navigation Jump to search

Theorem

$\ds \sum_{k \mathop = 0}^m \binom {2 k - 1} k \binom {2 n - 2 k} {n - k} \dfrac {-1} {2 k - 1} = \dfrac {n - m} {2 n} \dbinom {2 m} m \dbinom {2 n - 2 m} {n - m} + \dfrac 1 2 \dbinom {2 n} n$


Proof

From Summation from k to m of r Choose k by s Choose n-k by nr-(r+s)k:

$\ds \sum_{k \mathop = 0}^m \dbinom r k \dbinom s {n - k} \paren {n r - \paren {r + s} k} = \paren {m + 1} \paren {n - m} \dbinom r {m + 1} \dbinom s {n - m}$


Set $r - \dfrac 1 2$ and $s = -\dfrac 1 2$.

$\ds \sum_{k \mathop = 0}^m \dbinom {1/2} k \dbinom {-1/2} {n - k} \paren {\frac n 2 - \paren {\frac 1 2 - \frac 1 2} k} = \paren {m + 1} \paren {n - m} \dbinom {1/2} {m + 1} \dbinom {-1/2} {n - m}$


Take the left hand side:

\(\ds \) \(\) \(\ds \sum_{k \mathop = 0}^m \dbinom {1/2} k \dbinom {-1/2} {n - k} \paren {\frac n 2 - \paren {\frac 1 2 - \frac 1 2} k}\)
\(\ds \) \(=\) \(\ds \dfrac n 2 \sum_{k \mathop = 0}^m \dbinom {1/2} k \dbinom {-1/2} {n - k}\) immediate simplification
\(\ds \) \(=\) \(\ds \dfrac n 2 \sum_{k \mathop = 0}^m \dbinom {1/2} k \dfrac {\paren {-1}^{n - k} } {4^{n - k} } \dbinom {2 n - 2 k} {n - k}\) Binomial Coefficient of Minus Half
\(\ds \) \(=\) \(\ds \dfrac n 2 \sum_{k \mathop = 0}^m \paren {\dfrac {\paren {-1}^{k - 1} } {2^{2 k - 1} \paren {2 k - 1} } \dbinom {2 k - 1} k - \delta_{k 0} } \dfrac {\paren {-1}^{n - k} } {2^{2 n - 2 k} } \dbinom {2 n - 2 k} {n - k}\) Binomial Coefficient of Half: Corollary
\(\ds \) \(=\) \(\ds \dfrac n 2 \sum_{k \mathop = 0}^m \dfrac {\paren {-1}^{n - 1} } {2^{2 n - 1} \paren {2 k - 1} } \dbinom {2 k - 1} k \dbinom {2 n - 2 k} {n - k} - \dfrac n 2 \dfrac {\paren {-1}^n} {2^{2 n} } \dbinom {2 n} n\) separating out the $\delta_{k 0}$
\(\ds \) \(=\) \(\ds \dfrac {\paren {-1}^n n} {2^{2 n} } \paren {\sum_{k \mathop = 0}^m \dbinom {2 k - 1} k \dbinom {2 n - 2 k} {n - k} \dfrac {-1} {\paren {2 k - 1} } - \dfrac 1 2 \dbinom {2 n} n}\) simplifying


Now the right hand side:

\(\ds \) \(\) \(\ds \paren {m + 1} \paren {n - m} \dbinom {1/2} {m + 1} \dbinom {-1/2} {n - m}\)
\(\ds \) \(=\) \(\ds \paren {m + 1} \paren {n - m} \dbinom {1/2} {m + 1} \dfrac {\paren {-1}^{n - m} } {2^{2 n - 2 m} } \dbinom {2 n - 2 m} {n - m}\) Binomial Coefficient of Minus Half
\(\ds \) \(=\) \(\ds \paren {m + 1} \paren {n - m} \dfrac {\paren {-1}^m} {\paren {2 m + 1} 2^{2 m + 2} } \dbinom {2 m + 2} {m + 1} \dfrac {\paren {-1}^{n - m} } {2^{2 n - 2 m} } \dbinom {2 n - 2 m} {n - m}\) Binomial Coefficient of Half
\(\ds \) \(=\) \(\ds \dfrac 1 {2^{2 n + 2} } \paren {m + 1} \paren {n - m} \dfrac {\paren {-1}^n} {2 m + 1} \dbinom {2 m + 2} {m + 1} \dbinom {2 n - 2 m} {n - m}\) simplification
\(\ds \) \(=\) \(\ds \dfrac 1 {2^{2 n + 2} } \paren {m + 1} \paren {n - m} \dfrac {\paren {-1}^n} {2 m + 1} \dfrac {2 m + 2} {m + 1} \dbinom {2 m + 1} m \dbinom {2 n - 2 m} {n - m}\) Factors of Binomial Coefficient
\(\ds \) \(=\) \(\ds \dfrac {\paren {-1}^n} {2^{2 n + 1} } \paren {n - m} \dfrac {m + 1} {2 m + 1} \dbinom {2 m + 1} m \dbinom {2 n - 2 m} {n - m}\) simplification
\(\ds \) \(=\) \(\ds \dfrac {\paren {-1}^n} {2^{2 n + 1} } \paren {n - m} \dfrac {m + 1} {2 m + 1} \dfrac {2 m + 1} {2 m + 1 - m} \dbinom {2 m} m \dbinom {2 n - 2 m} {n - m}\) Factors of Binomial Coefficient: Corollary 1
\(\ds \) \(=\) \(\ds \dfrac {\paren {-1}^n} {2^{2 n + 1} } \paren {n - m} \dbinom {2 m} m \dbinom {2 n - 2 m} {n - m}\) simplification


Thus we have:

\(\ds \dfrac {\paren {-1}^n n} {2^{2 n} } \paren {\sum_{k \mathop = 0}^m \dbinom {2 k - 1} k \dbinom {2 n - 2 k} {n - k} \dfrac {-1} {\paren {2 k - 1} } - \dfrac 1 2 \dbinom {2 n} n}\) \(=\) \(\ds \dfrac {\paren {-1}^n} {2^{2 n + 1} } \paren {n - m} \dbinom {2 m} m \dbinom {2 n - 2 m} {n - m}\) as the right hand side equals the left hand side
\(\ds \leadsto \ \ \) \(\ds \sum_{k \mathop = 0}^m \dbinom {2 k - 1} k \dbinom {2 n - 2 k} {n - k} \dfrac {-1} {\paren {2 k - 1} } - \dfrac 1 2 \dbinom {2 n} n\) \(=\) \(\ds \dfrac {n - m} {2 n} \dbinom {2 m} m \dbinom {2 n - 2 m} {n - m}\) dividing both sides by $\dfrac {\paren {-1}^n n} {2^{2 n} }$
\(\ds \leadsto \ \ \) \(\ds \sum_{k \mathop = 0}^m \dbinom {2 k - 1} k \dbinom {2 n - 2 k} {n - k} \dfrac {-1} {\paren {2 k - 1} }\) \(=\) \(\ds \dfrac {n - m} {2 n} \dbinom {2 m} m \dbinom {2 n - 2 m} {n - m} + \dfrac 1 2 \dbinom {2 n} n\)

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Summation_from_k_to_m_of_2k-1_Choose_k_by_2n-2k_Choose_n-k_by_-1_over_2k-1&oldid=536511"