14
$\begingroup$

How do I find sums like these?--

$$S=\displaystyle\sum_{k=0}^{39} \dbinom{200}{5k}$$

that is, when there is a summation of binomial coefficients, but with jumps of some terms..?

$\endgroup$
10
$\begingroup$

Note that $(1+x)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}x^k$. Let $\omega = e^{i2\pi/5}$

$(1+1)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}1^k$

$(1+\omega)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}\omega^k$

$(1+\omega^2)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}\omega^{2k}$

$(1+\omega^3)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}\omega^{3k}$

$(1+\omega^4)^{200} = \displaystyle\sum_{k = 0}^{200}\dbinom{200}{k}\omega^{4k}$

Now, since $1^k+\omega^k+\omega^{2k}+\omega^{3k}+\omega^{4k} = 5$ if $k$ is a multiple of $5$ and $0$ otherwise, we can add those $5$ equations together to get:

$\displaystyle\sum_{\substack{k = 0 \\ 5 | k}}^{200}5\dbinom{200}{k} = \sum_{k = 0}^{40}5\dbinom{200}{5k} = 2^{200}+(1+\omega)^{200}+(1+\omega^2)^{200}+(1+\omega^3)^{200}+(1+\omega^4)^{200}$.

Divide by $5$ and subtract $\dbinom{200}{200} = 1$ to get:

$\displaystyle\sum_{k = 0}^{39}\dbinom{200}{5k} = \dfrac{1}{5}\left(2^{200}+(1+\omega)^{200}+(1+\omega^2)^{200}+(1+\omega^3)^{200}+(1+\omega^4)^{200}\right)-1$.

Using the fact that $1+\omega = \phi e^{i\pi/5}$ and $1+\omega^2 = \frac{1}{\phi} e^{i2\pi/5}$, where $\phi = \dfrac{1+\sqrt{5}}{2}$, this simplifies to:

$\displaystyle\sum_{k = 0}^{39}\dbinom{200}{5k} = \dfrac{1}{5}\left(2^{200}+2\phi^{200}+2\phi^{-200}\right)-1$

$\endgroup$
  • $\begingroup$ The answer should be a natural number, right? $\endgroup$ – pkwssis Jul 16 '14 at 6:53
  • 1
    $\begingroup$ It should be if you/I simplify things correctly. $\endgroup$ – JimmyK4542 Jul 16 '14 at 6:58
7
$\begingroup$

Use the Discrete Fourier Transform. You have: $$ S = -1+\sum_{n\equiv 0\pmod{5}}\binom{200}{n}$$ and given that $\omega$ is a primitive fifth root of unity, $$ \begin{eqnarray*}S &=& -1+\frac{1}{5}\sum_{n=0}^{200}\binom{200}{n}(1+\omega^n+\omega^{2n}+\omega^{3n}+\omega^{4n})\\&=&-1+\frac{2^{200}+(1+\omega)^{200}+(1+\omega^2)^{200}+(1+\omega^3)^{200}+(1+\omega^4)^{200}}{5}\\&=&-1+\frac{2^{200}+2L_{200}}{5}, \end{eqnarray*}$$ where $L_{200}$ is the $200$th Lucas number.

$\endgroup$
4
$\begingroup$

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{S\equiv\sum_{k = 0}^{39}{200 \choose 5k}:\ {\large ?}}$

$$ \mbox{Note that}\quad S = -1+ \color{#c00000}{\sum_{k = 0}^{\infty}{200 \choose 5k}}\tag{1} $$

\begin{align} &\color{#c00000}{\sum_{k = 0}^{\infty}{200 \choose 5k}} =\sum_{k = 0}^{\infty}\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{200} \over z^{5k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{200} \over z} \sum_{k = 0}^{\infty}\pars{1 \over z^{5}}^{k} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{200} \over z} \,{1 \over 1 - 1/z^{5}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1}{z^{4}\pars{1 + z}^{200} \over z^{5} - 1} \,{\dd z \over 2\pi\ic} \end{align}

The integrand simple poles are the five roots of $\ds{z^{5} - 1 = 0}$. Namely, $$ z_{n} = \expo{2n\pi\ic/5}\,,\qquad\qquad n=-2,-1,0,1,2. $$ Then,

\begin{align} &\color{#c00000}{\sum_{k = 0}^{\infty}{200 \choose 5k}} =\sum_{n = -2}^{2}\lim_{z \to z_{n}} \bracks{\pars{z - z_{n}}\,{z^{4}\pars{1 + z}^{200} \over z^{5} - 1}} ={1 \over 5}\sum_{n = -2}^{2}\pars{1 + z_{n}}^{200} \\[5mm]&={1 \over 5}\sum_{n = -2}^{2}\pars{1 + \expo{2n\pi\ic/5}}^{200} ={1 \over 5}\sum_{n = -2}^{2}\pars{\expo{-n\pi\ic/5} + \expo{n\pi\ic/5}}^{200} \\[5mm]&={2^{200} \over 5}\sum_{n = -2}^{2}\cos^{200}\pars{n\,{\pi \over 5}} ={2^{200} \over 5}\bracks{1 + 2\cos^{200}\pars{\pi \over 5} +2\cos^{200}\pars{2\pi \over 5}} \end{align}

Replacing this result in $\pars{1}$:

\begin{align} S&\equiv\color{#66f}{\large\sum_{k = 0}^{39}{200 \choose 5k}}\ {\Large =}\ \color{#66f}{\large{2^{200} \over 5} - 1 + {2^{201} \over 5}\,\bracks{\cos^{200}\pars{\pi \over 5} +\cos^{200}\pars{2\pi \over 5}}} \\[5mm]&\approx {\tt 3.2139 \times 10^{59}} \end{align}

$\endgroup$

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.