$(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}$$

You can also prove this based on what you've already observed about the relationship with Pascal's Triangle:

Let $ A(i,n) = \sum P_{3k + i }$ for the coefficients of $ ( 1 + x + x^2 ) ^n$.
Then show by induction that
$$ A(0, n ) = A(1, n) = A(2, n) = A(0, n-1 ) + A(1, n-1) + A(2,n-1) = 3^{n-1}.$$

In fact, the $(1+x)^n$ analogue is the well known fact that the sum of the even terms and odd terms in Pascal's triangle are both $2^{n-1}$.
