Insanely huge binomials!

Consider $\displaystyle \left(1+z\right)^{2000} = \sum^{2000}_{r=0} {2000 \choose r} z^r$ .

Putting $z = 1$ into the above equation yields

\begin{aligned} && 2^{2000} &= \sum^{2000}_{r=0} {2000 \choose r} &&\tag{1} \end{aligned}

Let $1, \omega, \omega^2$ be the distinct roots of $z^3 = 1$ .

Consider

$\begin{aligned} & & z\left(1+z\right)^{2000} & = \sum^{2000}_{r=0} {2000 \choose r} z^{r+1} \end{aligned}$ .

Putting $z= \omega$ and $z = \omega^2$ respectively yields

\begin{aligned} && \omega (1+\omega)^{2000} &= \sum^{2000}_{r=0} {2000 \choose r} \omega^{r+1}&& \tag{2} \\ && \omega^2 (1+\omega^2)^{2000} &= \sum^{2000}_{r=0} {2000 \choose r} \omega^{2(r+1)} &&\tag{3} \end{aligned}

Note that $\omega^2 + \omega + 1 = 0$ and also that $\left(\omega^n\right)^2 + \omega^n + 1 = 0$ for $n$ is not divisible by $3$ . These two are important in the following.

Adding up the right-hand sides of $(1), (2) \text{ and } (3)$ yields

$\begin{aligned} & \sum^{2000}_{r=0} {2000 \choose r} + \sum^{2000}_{r=0} {2000 \choose r} \omega^{r+1} + \sum^{2000}_{r=0} {2000 \choose r}\omega^{2(r+1)} \\ = &\sum^{2000}_{r=0} {2000 \choose r} \left( \omega^{2(r+1)}+ \omega^{r+1} + 1\right)\\ =& 3 \sum^{666}_{r=0} {2000 \choose 3r+2} \end{aligned}$

where we exploit $\omega^{2(r+1)} + \omega^{r+1} +1 = \left(\omega^{r+1}\right)^2 + \omega^{r+1} +1 = \left\{ \begin{array}{cc} 0, & r\neq 3k - 1 \\ 3, & r = 3k- 1\end{array}\right. \text { where } k \text{ is a positive integer.}$

Hence

$\begin{aligned} \sum^{666}_{r=0} {2000 \choose 3r+2} &= \frac{2^{2000} + \omega (1+\omega)^{2000}+ \omega^2(1+\omega^2)^{2000} }{3}\\ &= \frac{2^{2000} + \omega (-\omega^2)^{2000}+ \omega^2 (\omega)^{2000} }{3}\\ &= \frac{2^2000 + \omega^{4001} + \omega^{2002}}{3}\\ &= \frac{2^{2000} + \omega^2 + \omega}{3}\\ &= \frac{2^{2000} + (-1)}{3}\\ &= \frac{2^{2000} - 1}{3} \end{aligned}$

Then now consider

\begin{aligned} \frac{2^{2000} -1}{3} & = \frac{1}{3} \sum^{1999}_{r=0} 2^{r} \\ &= \frac{1}{3} \sum^{199}_{r=0}2^{10r}\left(1+ 2 + 2^4 + \cdots + 2^9\right)\\ &= \frac{1}{3} \sum^{199}_{r=0}2^{10r} \cdot (2^{10} - 1)\\ &= \frac{1023}{3} \sum^{199}_{r=0} 1024^r\\ &\equiv 341 \sum^{199}_{r=0} 24^r \quad \quad \tag{mod 1000}\\ &= 341 \left(1 + 24 + 24^2 + 24^3 + \cdots + 24^{198} + 24^{199}\right)\\ &= 341 \left[1+ 24 + \overbrace{\left(24^2 + 24^3\right) + \cdots + \left(24^{198} + 24^{199}\right) }^{99 \text{ brackets }} \right]\\ &\equiv 341 \left(25 + \overbrace{400 + \cdots + 400}^{99 \text{ terms }} \right) \quad \quad \tag{ mod 1000 }\\ &= 341 \left(400 \times 99 +25\right)\\ &= 341 \left(40 \times 990 +25\right)\\ &\equiv 341 \left[40 \times (-10) +25\right]\ \tag{ mod 1000 }\\ &= 341 \left(-400 +25\right)\\ &\equiv 341 \left(600 +25\right) \tag{ mod 1000}\\ &\equiv 125 \tag{ mod 1000 }\end{aligned}

where we use $24^{2n} + 24^{2n+1} = 24^{2n} (25) = 24^{2(n-1)} \times 14400 \equiv 400\ (\text{mod 1000})$ for all natural numbers $n$ .

The hint is to use cube roots of unity, but really great problem :).

Fantastic problem Sharky!