How can I solve equations like $A(z)=1+z+(z+z^2)A(z)$?

Question

In the context of generating functions, how would one go about solving equations like:

$$A(z)=1+z+(z+z^2)A(z),$$

or

$$A(z)=1+z+z^2+(z+z^2+z^3)A(z)?$$

Answer 1

The easiest way to solve these equations is, of course, the way Andre pointed out in his comment. If you want to do it by series expansions (I assume this, because you tagged your question "generating functions"), just plug them in: $$\sum_{i=0}^\infty a_i z^i = 1 + z + (z+z^2)\left(\sum_{i=0}^\infty a_i z^i\right)$$ Then get everything into one series on one side: $$ (a_0-1) + (a_1-a_0-1)z + \sum_{i=2}^\infty (a_i-a_{i-1}-a_{i-2}) z^i = 0$$ The coefficients for each term $z^i$ need to be zero, so you can solve this easily for $a_0$ and $a_1$ and then recursively for $a_i$ with $i\geq 2$.