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

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 ?

• @insipidintegrator no it does not answer my question .. please try to see my problem
– user1077888
Jul 12, 2022 at 19:28
• @insipidintegrator my problem is on simplification , before wrting a comment , try to read the question
– user1077888
Jul 12, 2022 at 19:30
• Do you see how to show $(1+w)^{1000}=(w^{-2}+w^2)^{1000}$? Jul 12, 2022 at 19:48
• @BrianMoehring i cannot see it directly , how did you derive it ?
– user1077888
Jul 12, 2022 at 19:50
• In short, multiply the left side by $(w^2)^{1000}=1$ and then note $w^3=w^{-2}$. Do you see why that's more helpful as a form, at least to get an expression in terms of real numbers? Jul 12, 2022 at 20:01

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}$$.

• It seems that this answer gives non-integer value because of cosine and "u" ,but the expected answer must be integer. How will you solve this issue ?
– user1077888
Jul 12, 2022 at 20:31
• @ulahh As a mathematical problem, there is no issue to solve. E.g. if you've ever seen Binet's formula for Fibonacci numbers, you've seen another instance when the closed form of an integer includes powers of non-integers. If your context requires integer arithmetic, there may be a way of efficiently calculating your value (I haven't tried) but that requirement would definitely need to be in the original post. Jul 12, 2022 at 20:54
• @BrianMoehring i have edited
– user1077888
Jul 12, 2022 at 21:33
• To get closer to an integer here, note that $u=\phi-1$, and $u^2=\phi^2-2\phi+1=2-\phi$. Also, $\cos \frac{\tau}{10} = \frac{\phi}{2}$. A bit of rearrangement gives: $$N=2^{1000}-\phi^{1001}+\left(\frac{1}{\phi}\right)^{1000}$$ Now the fun part: $\phi^{k+1}-\left(\frac{1}{\phi}\right)^k \approx L_k$, that is, the $k$th Lucas number. The final solution then is $2^{1000}-L_{1001}$. Jul 13, 2022 at 4:25
• Apologies; I missed a factor of $5$ in there somehow. The solution is $\frac15 (2^{1000} - L_{1001})$ Jul 13, 2022 at 23:36

$$\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}}$$.

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.