Expansion of Binomial Coefficient $(1+x+x^2)^n$ Suppose $n$ is a natural number and consider expansion:
 $$\left(1+x+x^2\right)^n=\sum_{r=0}^{2n}  \ a_r x^r$$ 
Find $\ a_0+  \ a_3+ \ a_6+ \ a_9\ldots$
I used different method, but could not arrive at the answer. 
 A: Note: I think the nice comment from @labbhattacharjee is worth an answer by its own. In order to obtain a formula for
\begin{align*}
a_0+a_3+a_6+\cdots
\end{align*}
with $(1+x+x^2)^n=\sum_{r=0}^{2n}a_rx^n$ it is convenient to consider the third roots of unity
\begin{align*}
1,\,\omega_1=\frac{-1+i\sqrt{3}}{2},\,\omega_2=\frac{-1-i\sqrt{3}}{2}
\end{align*}
which are the zeros of
\begin{align*}
1-x^3=(1-x)(1+x+x^2)
\end{align*}

We observe that following holds
  \begin{align*}
1+\omega_1+\omega_1^2&=0\\
1+\omega_2+\omega_2^2&=0\tag{1}\\
\omega_1^2&=\omega_2\\
1&=\omega_1^3=\omega_2^3
\end{align*}

In order to obtain a formula for $a_0+a_3+a_6+\cdots$ we use the relationship (1) to filter out the coefficients $a_r$ with $r$ not a multiple of $3$. In order to do so, we evaluate the polynomial $(1+x+x^2)^{n}$ at $x=1,\omega_1$ and $\omega_2$.

We obtain
  \begin{align*}
\color{blue}{3^n}&=(1+1+1)^n=a_0+a_1+a_2+a_3+a_4+a_5+a_6+\cdots\\
\color{blue}{0}&=(1+\omega_1+\omega_1^2)^n=a_0+a_1\omega_1+a_2\omega_1^2+a_3+a_4\omega_1+a_5\omega_1^2+a_6+\cdots\\
\color{blue}{0}&=(1+\omega_2+\omega_2^2)^n\\
&=(1+\omega_1^2+\omega_1)^n=a_0+a_1\omega_1^2+a_2\omega_1^1+a_3+a_4\omega_1^2+a_5\omega_1^1+a_6+\cdots
\end{align*}
  Adding up these three equations we obtain
  \begin{align*}
\color{blue}{3^n+0+0}&=3a_0+a_1(1+\omega_1+\omega_1^2)+a_2(1+\omega_1^2+\omega_1)\\
&\qquad +3a_3+a_4(1+\omega_1+\omega_1^2)+a_5(1+\omega_1^2+\omega_1)\\
&\qquad +3a_6+\cdots\\
&=3a_0+3a_3+3a_6+\cdots\\
&\color{blue}{=3(a_0+a_3+a_6+\cdots)}
\end{align*}
We finally conclude
  \begin{align*}
  \color{blue}{a_0+a_3+a_6+\cdots=3^{n-1}\qquad\qquad n\geq 1}
  \end{align*}

A: \begin{align}
[1+x+x^2]
=&
\big[ (1+x)+x^2\big]^n
\\
=&
\sum_{k=0}^{n}\frac{n!}{k!(n-k)!}(1+x)^k\cdot (x^2)^{n-k}
\\
=&
\sum_{k=0}^{n}\frac{n!}{k!(n-k)!}\big(\sum_{i=0}^k\frac{k!}{i!(k-i)!}x^i\big)\cdot (x^2)^{n-k}
\\
=&
\sum_{k=0}^{n}\sum_{i=0}^k\frac{n!}{(n-k)!(k-i)!i!}\cdot x^{2n-2k+i}
\\
\end{align}
Hire $\sum_{i=0}^{0}\frac{n!}{(n-k)!(k-i)!i!}=0$.
This is the same as
$$
\sum_{n\geq k\geq i\geq 0}\frac{n!}{(n-k)!(k-i)!i!}x^{2n-2k+i}
$$
or to $v=n-k$, $u=k-i$ and $t=i$ we have
$$
\sum_{r=0}^{n}\sum_{t+u+v=r}\frac{n!}{v!u!t!}x^{2v+t}
$$
