# 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.

• Put $x=1,\omega,\omega^2$ and add Oct 25, 2017 at 7:11
• Thanks got the answer Oct 25, 2017 at 7:18

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*}
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$.
\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}$$