Find the value of $\binom{2000}{2} + \binom{2000}{5} + \binom{2000}{8} + \cdots \binom{2000}{2000}$ 
Find the value of $\binom{2000}{2} + \binom{2000}{5} + \binom{2000}{8} + \cdots \binom{2000}{2000}$  

I've seen many complex proofs. I am looking for an elementary proof. I know the fact that $\binom{2000}{0} + \binom{2000}{1} + \binom{2000}{2} + \cdots \binom{2000}{2000} = 2^{2000}$. This may help here. 

For $n\ge0$ let
$$a_n=\binom n0+\binom n3+\binom n6+\cdots=\sum_{k=0}^\infty\binom n{3k},$$
$$b_n=\binom n1+\binom n4+\binom n7+\cdots=\sum_{k=0}^\infty\binom n{3k+1},$$
$$c_n=\binom n2+\binom n5+\binom n8+\cdots=\sum_{k=0}^\infty\binom n{3k+2};$$
we seek the value of $c_{2000}.$ Observe that
$$a_n+b_n+c_n=2^n$$
and, for $n\ge1,$ from Pascal's rule we get the recurrences
$$a_n=a_{n-1}+c_{n-1},$$
$$b_n=a_{n-1}+b_{n-1},$$
$$c_n=b_{n-1}+c_{n-1}.$$
Hence, for $n\ge3,$ we have
$$c_n=b_{n-1}+c_{n-1}=a_{n-2}+2b_{n-2}+c_{n-2}=3a_{n-3}+3b_{n-3}+2c_{n-3}$$
$$=3(a_{n-3}+b_{n-3}+c_{n-3})-c_{n-3}=3\cdot2^{n-3}-c_{n-3}$$
and, for $n\ge6,$
$$c_n=3\cdot2^{n-3}-c_{n-3}=3\cdot2^{n-3}-(3\cdot2^{n-6}-c_{n-6})=c_{n-6}+21\cdot2^{n-6},$$
that is:
$$\boxed{c_n=c_{n-6}+21\cdot2^{n-6}}$$
Since $2000\equiv2\pmod6,$ we establish a closed formula for this case, namely
$$\boxed{c_n=\frac{2^n-1}3\text{ when }n\equiv2\pmod6}\ ,$$
by induction.
$c_2=\binom22=1=\frac{2^2-1}3.$
If $c_n=\frac{2^n-1}3,$ then
$$c_{n+6}=c_n+21\cdot2^n=\frac{2^n-1}3+21\cdot2^n=\frac{2^{n+6}-1}3.$$
In particular, when $n=2000,$ we have:
$$\boxed{\sum_{k=0}^\infty\binom{2000}{3k+2}=\sum_{k=0}^{666}\binom{2000}{3k+2}=c_{2000}=\frac{2^{2000}-1}3}$$
By the way, since $c_0=0=\frac{2^0-1}3,$ the identity $c_n=\frac{2^n-1}3$ also holds when $n\equiv0\pmod6.$
The general formula is
$$\boxed{\sum_{k=0}^\infty\binom n{3k+2}=\sum_{k=0}^{\left\lfloor\frac{n-2}3\right\rfloor}\binom n{3k+2}=c_n=\frac{2^n+2\cos\frac{(n+2)\pi}3}3}$$
