2
$\begingroup$

Find the sum of $\binom{200k}{0}+\binom{200k}{100}+\binom{200k}{200}+...+\binom{200k}{200k}$ and $\binom{200k}{1}+\binom{200k}{101}+\binom{200k}{201}+...+\binom{200k}{200k-99}$ in terms of $k$.

I've tried to do generating functions but I don't get to make the terms cancel out for some reason. This problems seems quite well known but I do not know what terms to search.

$\endgroup$
2
$\begingroup$

We consider the generating series $F(x)$ with \begin{align*} F(x)=(1+x)^{200k}=\sum_{m=0}^{200k}\binom{200k}{m}x^{m} \end{align*}

In order to pick every $100$-th term of the generating series we use the $100$-th roots of unity \begin{align*} \omega_j=e^{\frac{2j\pi }{100}i}\qquad\qquad 0\leq j < 100 \end{align*} and the relationship \begin{align*} \frac{1}{100}\sum_{j=0}^{99}\omega^n_j= \begin{cases}1&100|n\\0&\text{else}\end{cases}\qquad\qquad n>0\tag{1} \end{align*}

We obtain \begin{align*} \frac{1}{100}\sum_{j=0}^{99}F_k(\omega_j x)&=\frac{1}{100}\sum_{j=0}^{99}(1+\omega_jx)^{200k}\\ &=\frac{1}{100}\sum_{j=0}^{99}\sum_{m=0}^{200k}\binom{200k}{m}(\omega_jx)^{m}\\ &=\frac{1}{100}\sum_{m=0}^{200k}\binom{200k}{m}x^m\sum_{j=0}^{99}\omega_j^{m}\tag{2}\\ &=\sum_{m=0}^{2k}\binom{200k}{100m}x^{100m}\\ \end{align*}

Comment:

  • In (2) we rearrange the sums and use the cancellation property of the roots of unity from (1).

Setting $x=1$ we conclude

\begin{align*} \sum_{m=0}^{2k}\binom{200k}{100m}=\sum_{j=0}^{99}(1+e^{\frac{2j\pi }{100}i})^{200k} \end{align*}

Hint: For the second sum consider \begin{align*} \frac{1}{100}\sum_{j=0}^{99}\left(\omega_j\right)^{-1}(1+\omega_jx)^{200k} \end{align*}

$\endgroup$
  • $\begingroup$ Is there a closed form of the answer - not in a summation form? $\endgroup$ – The Math Troll Jan 4 '16 at 0:49
  • $\begingroup$ I think the (1) of your answer is incorrect. Setting n=100 makes your quantity 101/100. Did you mean to take the summation only from 0 to 99? $\endgroup$ – The Math Troll Jan 4 '16 at 0:54
  • $\begingroup$ @TheMathTroll: You're right of course. Typo corrected. $\endgroup$ – Markus Scheuer Jan 4 '16 at 2:04
  • $\begingroup$ @TheMathTroll: I'm not aware of a more compact formulation. You may want to look at example 4 on page 51 in H.Wilf's Generatingfunctionology. $\endgroup$ – Markus Scheuer Jan 4 '16 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.