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. 


Tools used:
  
  
*
  
*The identity ${n\choose i}={n-1\choose i}+{n-1\choose i-1}$
  
*The identity $\sum\limits_{i=0}^n{n\choose i}=2^n$
  

Let $A(n,k)$ denote the sum of the binomial coefficients ${n\choose i}$ over every $0\leqslant i\leqslant n$ such that $i=k\bmod 3$, then we are after $$A(2000,2)$$
The identity ${n\choose i}={n-1\choose i}+{n-1\choose i-1}$ implies that, for every $n\geqslant1$,
$$A(n,k)=A(n-1,k)+A(n-1,k-1)=\left(\sum_{j=0}^2A(n-1,j)\right)-A(n-1,k+1)$$ 
For every $n\geqslant0$, $$\sum_{j=0}^2A(n,j)=\sum_{i=0}^n{n\choose i}=2^n$$ hence 

$$A(n,k)=2^{n-1}-A(n-1,k+1)$$ 

Iterating this, one gets $$A(n,k)=\left(2^{n-1}-2^{n-2}+\cdots+(-1)^{n-1}2^0\right)+(-1)^nA(0,k+n)$$
that is, evaluating the alternating sum in the parenthesis, $$A(n,k)=\tfrac13\cdot(2^n-(-1)^n)+(-1)^nA(0,k+n)$$
Recall that ${0\choose 0}=1$ while ${0\choose i}=0$ for every $i\ne0$ hence $A(0,k)=1$ if $k=0\bmod 3$ and $A(0,k)=0$ otherwise, which yields our final formula for $A(n,k)$ as 

$$A(n,k)=\tfrac13\cdot(2^n-(-1)^n)+(-1)^n\cdot\mathbf 1_{n+k=0\bmod 3}$$ 

For example, $2000+2\ne0\bmod 3$ and $2000=0\bmod 2$ hence 

$$A(2000,2)=\tfrac13\cdot\left(2^{2000}-1\right)$$ 

while $2000+0\ne0\bmod 3$ and $2000+1=0\bmod 3$ hence 
$$A(2000,0)=\tfrac13\cdot\left(2^{2000}-1\right)\qquad A(2000,1)=\tfrac13\cdot\left(2^{2000}+2\right)$$
