Finding generating series from equation How can I solve $f(x)=(1+x+x^2)f(x^2)$, where $f$ is a generating series of a set?  I just need the technique, not necessarily the solution.
 A: $$f(x)=\frac{1-x^3}{1-x}f(x^2)=\frac{1-x^3}{1-x}\frac{1-x^6}{1-x^2}f(x^4)=
\cdots.$$
Therefore
$$f(x)=f(0)\prod_{k=0}^\infty\frac{1-x^{3\cdot 2^k}}{1-x^{2^k}}.$$
A: $$f(x)=(1+x+x^2)f(x^2) \\
f(x)=\sum_{i\geq 0} a_{i} x^i$$
Therefore
$$\sum_{i\geq 0} a_{i} x^i=(1+x+x^2)\sum_{i\geq 0} a_{i} (x^2)^i$$
which we rewrite as
$$\sum_{i\geq 0} a_{i} x^i = \sum_{i\geq 0} a_{i} x^{2i} + \sum_{i\geq 0} a_{i} x^{2i+1} + \sum_{i\geq 0} a_{i} x^{2i+2}$$
Extracting coefficients of $x^{2k}$ on both sides, we have $$a_{2k} = a_k + [k > 0] a_{k-1}$$
and extracting coefficients of $x^{2k+1}$ we have $$a_{2k+1} = a_k$$
Therefore $$\begin{eqnarray}a_1 &&&=& a_0 \\
a_2 &=& a_1 + a_0 &=& 2a_0 \\
a_3 &=& a_1 &=& a_0 \\
a_4 &=& a_2 + a_1 &=& 3a_0 \\
a_5 &=& a_2 &=& 2a_0 \\
a_6 &=& a_3 + a_2 &=& 3a_0 \\
a_7 &=& a_3 &=& a_0 \\
a_8 &=& a_4 + a_3 &=& 4a_0
\end{eqnarray}$$
etc.
A simple computer program to generate 80 terms and a search of OEIS (assuming $a_0 = 1$) gives one hit: A002487 (skipping the initial $0$). The comments, references, and formulae give you a lot of ways to continue researching. However, I will note that Arie Werksma claims that the generating function of this sequence satisfies the desired functional equation:

a(k+1)*a(2^n - k) - a(k)*a(2^n - (k+1)) = 1; a(2^n - k) + a(k) = a(2^(n+1) + k). Both formulas hold for 0 <= k <= 2^n - 1. G.f.: G(z) = a(1) + a(2)*z + a(3)*z^2 + ... + a(k+1)*z^k + ... Define f(z) = (1 + z + z^2), then G(z) = lim f(z)*f(z^2)*f(z^4)* ... *f(z^(2^n))*... = (1 + z + z^2)*G(z^2). - Arie Werksma (werksma(AT)tiscali.nl), Apr 11 2008

A: $f(x) = a_0 + a_1 x + a_2 x^2 + \cdots$
$f(x^2) = a_0 + a_1 x^2 + a_2 x^4 + \cdots$
so $(1 + x + x^2) f(x^2) = a_0 + a_1 x + a_2 x^2 + \cdots + a_0 x + a_1 x^2 + a_2 x^3 + \cdots + a_0 x^2 + a_1 x^3 + a_2 x^4 + \cdots$
Given $f(x) = (1 + x + x^2) f(x^2)$ we equate the following powers of $x$:
$x^0$ therefore:  $a_0 = a_0$
$x^1$ therefore:  $a_1 = a_1 + a_0$
But these two equations shows that $a_0 = 0$ ($\checkmark$).
$x^2$ therefore:  $a_2 = a_2 + a_1 + \underbrace{a_0}_{=0}$
Thus $a_1 = 0$ ($\checkmark$).
Can you continue?
