Techniques for solving recurrence relations using generating functions

Question

How does one extract coefficients from generating functions that involve exponents. Things like $A(z) = 1+A(z^2)$ or $A(z)= 1+A(z^2)+A(\sqrt z)$?

Answer 1

The general idea would be to expand both sides, and equate coefficients. In the first case cited, this won't work (you get $A(0) = 1 + A(0)$, which is inconsistent, on substituting $x = 0$ on both sides).

For the second one, take $B(z) = A(z^{1/2})$ and $B(z) = \sum_{n \ge 0} b_n z^n$: $$ B(z^2) = 1 + B(z^4) + B(z) $$ This is: $$ \sum_{n \ge 0} b_n z^{2 n} = 1 + \sum_{n \ge 0} b_n z^{4 n} + \sum_{n \ge 0} b_n z^n $$ This gives ($[\ldots]$ is Iverson bracket): $$ b_{2 n} = [n = 0] + b_n + b_{4 n} $$ This gives $b_0 = -1$, but we need $b_1$ and $b_2$ to get the recursion started. This means getting $B'(0)$ and $B''(0)$, but the equation gives $B'(0) = B''(0) = 0$. No solution possible.