If $(1+x+x^2)^{25} =\sum^{50}_{r=0} a_r x^r$ then .... If $$(1+x+x^2)^{25} =\sum^{50}_{r=0} a_r x^r$$ 
then find :
$\sum^{16}_{r=0} a_{3r} =$
My approach : 
let (1+x) =t  therefore, 
$(1+x+x^2)^{25} =\sum^{50}_{r=0} a_r x^r$
=$(1+x+x^2)^{25} = (t+x^2)^{25}$
$= ^{25}C_0t^{25} +^{25}C_1 t^{24}x^2 +^{25}C_2 t^{23}x^4 +\cdots + x^{50}$
Also expanding the right hand side which is $\sum^{50}_{r=0} a_r x^r = a_0x^0 +a_1x+a_2x^2 +\cdots a_{50}x^{50}$
But unable to correlate this with the  given problem i.e how to find $\sum^{16}_{r=0} a_{3r}$ please guide further on this. thanks.
 A: Hint: Evaluate at the two roots of the equation $1+x+x^2=0$ and at $x=1$, that is, at the three cube roots of unity, and add. The key fact is that if $\omega$ is one of the roots of $1+x+x^2=0$, then $\omega^2$ is the other, and $1^k+\omega^k+\omega^{2k}=0$ unless $k$ is divisible by $3$.
A: Here’s an alternative approach.
In $(1+x+x^2)^n$ the coefficient $a_{n,k}$ of $x^k$ is the number of elements in the set $\{0,1,2\}^n$ whose terms sum to a multiple of $k$. (Why?) For $\ell\in\{0,1,2\}$ let 
$$b_\ell(n)=\sum\{a_{n,k}:k\equiv\ell\!\!\!\pmod3\}\;;$$
equivalently, $b_\ell(n)$ is the number of elements in the set $\{0,1,2\}^n$ whose elements have a sum congruent to $\ell$ modulo $3$. It’s not hard to see that
$$b_0(n)=b_1(n)=b_2(n)=b_0(n-1)+b_1(n-1)+b_2(n-1)$$
for $n\ge 1$: for any $\ell,m\in\{0,1,2\}$, each sequence in $\{0,1,2\}^{n-1}$ whose sum is congruent to $\ell$ modulo $3$ can be extended to exactly one sequence in $\{0,1,2\}^n$ whose sum is congruent to $m$ modulo $3$. Moreover, $b_0(0)=1$ and $b_1(0)=a_2(0)=0$, so by an easy induction 
$$b_0(n)=b_1(n)=b_2(n)=3^{n-1}$$
for $n>0$.
