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

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

-
For the first, bring all the $A(z)$ stuff to one side. We get $A(z)(1-z-z^2)=1+z$. Then divide both sides by $1-z-z^2$. – André Nicolas Mar 2 '13 at 8:45

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$.
Not sure that this answers the OP's concerns at all. It seems the question is precisely to determine $a_n$ for every $n$ and that the advice to "solve this easily for a0 and a1 and then recursively for ai with i≥2" brings us back exactly at square one, which is the series A(z) itself. Maybe you (or any of the 6 upvoters so far...) could explain how to solve this last recursion. – Did Mar 24 '13 at 10:04
@Did Well, I wouldn't be sure, but, given that the OP didn't ask during the last three weeks, I wouldn't be too worried either. To answer your question now: I think in the present case it's pretty obvious, that the Fibonaccis will do the trick. In the general case it depends: If you want to have $a_n$ for specific $n$'s you just apply the recurrence relation iteratively (that's what I meant in my answer, BTW). (to be continued...) – Elmar Zander Mar 24 '13 at 10:42
If you want to have an explicit form and the equation is $A(z)=q(z)+p(z)A(z)$, where $p$ and $q$ are polynomials, it would be something like $a_n=\sum_{i=1}^m \alpha_i r_i^n$, where the $r_i$ are the roots of $p$ and the $\alpha_i$ can be fitted using the values of $a_0$ to $a_{m-1}$. Of, course this is not so easy if the degree of $p$ is high and needs to be modified a bit, if there are multiple roots or the degree of $q$ is larger than $m$ – Elmar Zander Mar 24 '13 at 10:42
After seeing that my formula was wrong for $a_1$ and correcting it, the sequence is now $1,2,3,5,8,13,21,\ldots$. Anyway, still a shifted Fibonacci series... – Elmar Zander Mar 24 '13 at 10:53
Precisely, I am objecting to "you just apply the recurrence relation iteratively" (certainly you would not do that if asked for $a_{1000}$). But, as you said, to make any progress on this, we need some kind of input from the asker... – Did Mar 24 '13 at 12:21