MHB How Do You Calculate the Sum of Specific Binomial Coefficients?

[anemone]

Here is this week's POTW:

-----

Without using a calculator, evaluate $${2000 \choose 2}+{2000 \choose 5}+{2000 \choose 8}+\cdots+{2000 \choose 2000}.$$

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[anemone]

Congratulations to Opalg for his correct solution, which you can find below::)

Spoiler

[Let $\omega = e^{2\pi i/3} = -\frac12 + \frac{\sqrt3}2i.$ Then $\omega^3 = 1$ and $1+\omega + \omega^2 = 0.$
Apply the binomial formula $$(1+x)^{2000} = \sum_{r=0}^{2000}x^r{2000 \choose r}$$ with $x=1$, $x=\omega$ and $x=\omega^2$, to get $$(1+1)^{2000} + \omega(1+\omega)^{2000}+ \omega^2(1+\omega^2)^{2000} = \sum_{r=0}^{2000}\bigl(1 + \omega^{r+1} + \omega^{2r+2}\bigr) {2000 \choose r}.\qquad(*)$$ On the right side of that equation, if $r$ is a multiple of $3$, say $r=3k$, then $$1 + \omega^{r+1} + \omega^{2r+2} = 1 + \omega^{3k+1} + \omega^{6k+2} = 1+\omega + \omega^2 = 0.$$ If $r = 3k+1$ then $$1 + \omega^{r+1} + \omega^{2r+2} = 1 + \omega^{3k+2} + \omega^{6k+4} = 1 + \omega^2 +\omega = 0.$$ If $r = 3k+2$ then $$1 + \omega^{r+1} + \omega^{2r+2} = 1 + \omega^{3k+3} + \omega^{6k+6} = 1 + 1 + 1 = 3.$$ Therefore all the terms in the starred equation vanish except for those where $r$ is a multiple of $3$ plus $2$.

On the left side of the starred equation, $(1+1)^{2000} = 2^{2000}$.

Next, $\omega(1+\omega)^{2000} = \omega(-\omega^2)^{2000} = (-1)^{2000}\omega^{4001} = \omega^2$ (since $4001 = 3\times1333 + 2$).

Similarly, $\omega^2(1+\omega^2)^{2000} = \omega^2(-\omega)^{2000} = \omega^{2002} = \omega.$

Therefore (*) becomes $$2^{2000} + \omega^2 + \omega = 3\biggl({2000 \choose 2}+{2000 \choose 5}+{2000 \choose 8}+\ldots+{2000 \choose 2000}\biggr),$$ and since $\omega^2 + \omega = -1$ we can conclude that $${2000 \choose 2}+{2000 \choose 5}+{2000 \choose 8}+\ldots+{2000 \choose 2000} = \frac{2^{2000} - 1}3.$$