Every third binomial: 671 times

Nice problem, whenever we see problems like this, we could use the Roots of Unity . In this case, we use the primitive cube root of $1$ , which we will call $w$ . Therefore $w^2 +w + 1 = 0$ and $w^3 =1$ . We know that:

$(1+1)^{2014}=\binom{2014}{0}+\binom{2014}{1}+\binom{2014}{2}+\dots+\binom{2014}{2014}$ $w^{2}(1+w)^{2014}=\binom{2014}{0}w^{2}+\binom{2014}{1}+\binom{2014}{2}w+\dots+\binom{2014}{2014}$ $w(1+w^{2})^{2014}=\binom{2014}{0}w+\binom{2014}{1}+\binom{2014}{2}w^{2}+\dots+\binom{2014}{2014}$

Also, it's widely known that $\displaystyle \sum_{k=0}^{n} \binom{n}{k}=2^{n}$ .

For convenience, let $\displaystyle \binom{2014}{1}+\binom{2014}{4}+\dots+\binom{2014}{2014}=m$

Adding our first three equations, we get $w^{2}(1+w)^{2014}+w(1+w^{2})^{2014}+2^{2014}=3m$

$\implies w+w^{2}+2^{2014}=3m$

$\implies m=\dfrac{2^{2014}-1}{3}$

And $m \equiv \boxed{461} \pmod{1000}$

Let $a_n, b_n, c_n$ be the sum of the binomial coefficients $\binom{n}{i}$ where $i$ is congruent to $0,1,2$ mod $3$ , respectively. The problem is asking for $b_{2014}$ .

Pascal's identity gives $\begin{aligned} a_n &= c_{n-1} + a_{n-1} \\ b_n &= a_{n-1} + b_{n-1} \\ c_n &= b_{n-1} + c_{n-1} \\ \end{aligned}$ so we can apply recursively to get $\begin{aligned} a_n &= c_{n-2} + 2^{n-2} \\ b_n &= a_{n-2} + 2^{n-2} \\ c_n &= b_{n-2} + 2^{n-2} \\ \end{aligned}$ and applying this three times gives $b_n = 2^{n-2} + 2^{n-4} + 2^{n-6} + b_{n-6}$ .

In particular $\begin{aligned} b_{2014} = 2^{2012} + 2^{2010} + \cdots + 2^4 + b_4 &= 2^{2012} + 2^{2010} + \cdots + 2^4 + 5 \\ &= 2^{2012} + 2^{2010} + \cdots + 2^4 + 2^2 + 1 \\ &= \frac{2^{2014}-1}3 \end{aligned}$ and we can proceed as in the other solution.