Calculate $\binom{1000}{3}+\binom{1000}{8}+\binom{1000}{13}+\dots+\binom{1000}{998}=?$ using complex numbers

Question

I am trying to find $$\binom{1000}{3}+\binom{1000}{8}+\binom{1000}{13}+\dots+\binom{1000}{998}=?$$

My work:

Let $\omega=\exp(\displaystyle\frac{2\pi i}{5}) $ and so $\omega^5=1$ . Then $1 + \omega+\omega^2+\omega^3+\omega^4=0$

$$(1+1)^{1000}+w^2(1+w)^{1000}+w^4(1+w^2)^{1000}+w^6(1+w^3)^{1000}+w^8(1+w^4)^{1000}\\=\sum_{k=0}^{1000}\bigg[\binom{1000}{k}+\binom{1000}{k}w^{k+2}+\binom{1000}{k}w^{2k+4}+\binom{1000}{k}w^{3k+6}+\binom{1000}{k}w^{4k+8}\bigg]\\= 5\bigg[\binom{1000}{3}+\binom{1000}{8}+\binom{1000}{13}+\dots+\binom{1000}{998}\bigg]$$

However , when I come to calculate the result of $(1+1)^{1000}+w^2(1+w)^{1000}+w^4(1+w^2)^{1000}+w^6(1+w^3)^{1000}+w^8(1+w^4)^{1000}$ , I stuck in it , because I could not simplify it using $\omega^5=1$ or $1 + \omega+\omega^2+\omega^3+\omega^4=0$.

Hence , I am looking for helps to find a closed formula for the binomial expansion by simplifying $(1+1)^{1000}+w^2(1+w)^{1000}+w^4(1+w^2)^{1000}+w^6(1+w^3)^{1000}+w^8(1+w^4)^{1000}$

ADDENTUM: I want to reach an integer solution, as it is expected from this expression. For example, Find the value of $\binom{2000}{2} + \binom{2000}{5} + \binom{2000}{8} + \cdots \binom{2000}{2000}$ , answer of this question is $(2^{2000}+2)/3$. It is what kind of answer I want to reach. So, can you help me to simplify given expression into this type of integer result answer ?

Thanks in advance !!

Answer 1

For comfort of notation (I am more inclined to make a mistake using $\omega$ because I am accustomed with it being a third root of unity), let $\displaystyle \alpha=e^{\frac{2\pi i}{5}}$.

Then, $\alpha^5=1$ and $\alpha^4+ \alpha^3+ \alpha^2+ \alpha+1=0$. Dividing the latter equation by $\alpha^2$ gives $$\left(\alpha^2+\frac{1}{\alpha^2}\right)+\left(\alpha+\frac{1}{\alpha}\right)+1=0$$ Let $\displaystyle{\alpha}+\frac{1}{\alpha}=u$. Then $$u^2-2+u+1=0\implies u^2+u-1=0$$ and thus $$\displaystyle u=\frac{-1\pm \sqrt 5}{2}$$

Now, the original expression is $$2^{1000}+ {\alpha}^2(1+{\alpha})^{1000}+ \alpha ^4(1+ \alpha ^2)^{1000}+ \alpha ^6(1+ \alpha^3 )^{1000}+ \alpha ^8(1+ \alpha^4 )^{1000}$$$$= 2^{1000}+ {\alpha}^2(1+{\alpha})^{1000}+ \frac{1}{\alpha}( 1+ \alpha ^2)^{1000}+ \alpha(1+ \alpha^3 )^{1000}+ \frac{1}{\alpha^2}(1+ \alpha^4 )^{1000}$$, all using $\alpha^5=1$. Now, put $\alpha^3=\frac{1}{\alpha^2}$ and $\alpha^4=\frac{1}{\alpha}$ so you get $$= 2^{1000}+ {\alpha}^2(1+{\alpha})^{1000}+ \frac{1}{\alpha}( 1+ \alpha ^2)^{1000}+ \alpha(1+ \alpha^2)^{1000}+ \frac{1}{\alpha^2}(1+ \alpha)^{1000}$$ using $\alpha^{1000}=\alpha^{2000}=1$. Now write this as $$2^{1000}+(u^2-2)(1+\alpha)^{1000}+u(1+\alpha^2)^{1000}$$ Divide the last term by $\alpha^{1000}$:$$2^{1000}+(u^2-2)(1+\alpha)^{1000}+u^{1001}$$ Now, let $\alpha=\cos\theta+i\sin\theta$ where $5\theta=2\pi$. Thus, $$(1+\alpha)^{1000}=(1+\cos\theta+i\sin\theta)^{1000}$$$$=(2\cos^2\frac{\theta}{2}+2i\sin\frac{\theta}{2}\cos\frac{\theta}{2})^{1000}=2^{1000}\left(\cos\frac{\theta}{2}\right)^{1000}\left(\cos\frac{\theta}{2}+2i\sin\frac{\theta}{2}\right)^{1000}= 2^{1000}\left(\cos\frac{\theta}{2}\right)^{1000}\left(e^{\frac{2\pi i}{5}}\right)^{1000}= 2^{1000}\left(\cos\frac{\theta}{2}\right)^{1000}. $$

Finally, assimilating everything, we have

Expression $ = 2^{1000}+(u^2-2) 2^{1000}\left(\cos\frac{\pi}{5}\right)^{1000}+u^{1001}. $

Now, to decide the value of $u$, notice that $\alpha+\frac{1}{\alpha}=2\cos\frac{2\pi}{5}=\frac{\sqrt5-1}{2}$.

Answer 2

Hint: observe that

$$(1+w^k)^5 = 1 + \binom{5}{1}w^k + \binom{5}2w^{2k}+\binom{5}{3}w^{3k}+\binom{5}{4}w^{4k}+1 $$ When $k=1,4$ we get $$1 + \binom{5}{1}w + \binom{5}2w^{2}+\binom{5}{3}w^{3}+\binom{5}{4}w^{4}+1$$ Because $\binom{5}{i}=\binom{5}{5-i}$

When $k=2,3$ we get $$1 + \binom{5}{1}w^2 + \binom{5}2w^{2}+\binom{5}{3}w^{1}+\binom{5}{4}w^{3}+1$$

You can write $(1+w^k)^{1000}= \left[(1+w^k)^5\right]^{200}$ And use the above to reduce your expression.

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\on}[1]{\operatorname{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} & \color{#44f}{{1000 \choose 3} + {1000 \choose 8} + {1000 \choose 13} + \cdots + {1000 \choose 998}} \\[5mm] = & \ \sum_{n = 0}^{199}{1000 \choose 5n + 3} = \sum_{n = 0}^{\infty}{1000 \choose 997 - 5n} \\[5mm] = & \ \sum_{n = 0}^{\infty}\ \oint_{\verts{z}\ =\ 1^{-}} {\pars{1 + z}^{1000} \over z^{998 - 5n}} {\dd z \over 2\pi\ic} \\[5mm] = & \ \oint_{\verts{z}\ =\ 1^{-}} {\pars{1 + z}^{1000} \over z^{998}} \sum_{n = 0}^{\infty}\pars{z^{5}}^{n} \,{\dd z \over 2\pi\ic} \\[5mm] = & \ \oint_{\verts{z}\ =\ 1^{-}} {\pars{1 + z}^{1000} \over z^{998}} {1 \over 1 - z^{5}}\,{\dd z \over 2\pi\ic} \\[5mm] \stackrel{z\ \mapsto\ 1/z}{=}\,\, & \ \oint_{\verts{z}\ =\ 1^{+}} {z\pars{1 + z}^{1000} \over z^{5} - 1} {\dd z \over 2\pi\ic} \\[5mm] = & \ \left.{1 \over 5}\sum_{n = -2}^{2}\xi_{n}^{2}\ \pars{1 + \xi_{n}}^{1000}\,\,\right\vert _{\,\xi_{n}\ \equiv\ \exp\pars{2n\pi\ic/5}} \\[5mm] = & \ \bbx{\color{#44f}{\begin{array}{l} \ds{{2^{1000} \over 5} + {2 \over 5}\,\Re\bracks{\expo{2\pi\ic/5}\pars{1 + \expo{2\pi\ic/5}}^{1000}\,}} \\[2mm] \ds{+\ {2 \over 5}\,\Re\bracks{\expo{4\pi\ic/5} \pars{1 + \expo{4\pi\ic/5}}^{1000}\,}} \end{array}}} \\ & \end{align} The final result is, indeed, a big number $\ds{\approx 2.1430 \times 10^{300}}$.