<s>[INST] $(1+x+x^2)^n=P_0+P_{1}x + P_{2}x^2+ \cdots +P_{2n}x^{2n}$ Prove that,$ P_0+P_{3}+P_{6}+ \cdots =3^{(n-1)}$ Let's say $$ S_n = (1+x+x^2)^n $$
n=1 $$S_1=1+x+x^2$$
n=2 $$S_2=1+2x+3x^2+2x^3+x^4$$
n=3 $$S_3=1+3x+6x^2+7x^3+6x^4+3x^5+x^6$$
n=4 $$S_4=1+4x+10x^2+16x^3+19x^4+16x^5+10x^6+4x^7+x^8$$
By taking coefficients of the $S_n$ we can form this type of triangle similar to Pascal's Trinagle
$$\begin{matrix}
&&&&&&&&&1\\
&&&&&&&1&&1&&1\\
&&&&&1&&2&&3&&2&&1\\
&&&&1&&3&&6&&7&&6&&3&&1\\
&&1&&4&&10&&16&&19&&16&10&&4&&1
\end{matrix}$$
 [/INST] Let define
$$(1+x+x^2)^{n}=P_0(n)+P_{1}(n)x + P_{2}(n)x^2 \pmod {x^3}$$
with

*

*$P_0(n)= P_0+P_3+\cdots$

*$P_1(n)= P_1+P_4+\cdots$

*$P_2(n)= P_2+P_5+\cdots$
therefore it is easy to check that
$$(1+x+x^2)^{n+1}=P_0(n+1)+P_{1}(n+1)x + P_{2}(n+1)x^2=$$
$$=\left[P_0(n)+P_{1}(n) + P_{2}(n)\right]+\left[P_0(n)+P_{1}(n) + P_{2}(n)\right]x+\left[P_0(n)+P_{1}(n) + P_{2}(n)\right]x^2$$
and since $P_0(1)=P_1(1)=P_2(1)=1$, we easily obtain that

*

*$P_0(1)=1$

*$P_0(2)=3P_0(1)=3$

*$P_0(3)=3P_0(2)=3^2P_0(1)=3^2$

*$\cdots$

*$P_0(n)=3^{n-1}$
</s>