If $(1+x+x^2)^{25} =\sum^{50}_{r=0} a_r x^r$ then ....

Question

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.

Answer 1

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

Answer 2

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