2

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.

1 Answers1

2

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*}

Markus Scheuer
  • 108,315