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$

1 Answer 1

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$
4
  • $\begingroup$ Is there a closed form of the answer - not in a summation form? $\endgroup$ Jan 4, 2016 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$ Jan 4, 2016 at 0:54
  • $\begingroup$ @TheMathTroll: You're right of course. Typo corrected. $\endgroup$ Jan 4, 2016 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$ Jan 4, 2016 at 2:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .