Finding generating series from equation

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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