What is the generating function of the following recurrence relation $$a_n = a_{n - 1} \cdot a_{n - 2} + 3 \hspace{3em} a_0 = 1, a_1 = 3, n \geq 2$$ I tried the method on page 8 of generatingfunctionology by Herbert S. Wilf, Quoting from the book for the convenience of the users looking into this question(p.s : thanks for that:))
Given: a recurrence formula that is to be solved by the method of generating functions.
- Make sure that the set of values of the free variable (say n) for which the given recurrence relation is true, is clearly delineated.
- Give a name to the generating function that you will look for, and write out that function in terms P of the unknown sequence (e.g., call it A(x), and define it to be $\sum_{n=0}^{\infty}a_n \cdot x^n$ ).
- Multiply both sides of the recurrence by $x^n$ , and sum over all values of n for which the recurrence holds.
- Express both sides of the resulting equation explicitly in terms of your generating function A(x).
- Solve the resulting equation for the unknown generating function A(x).
- If you want an exact formula for the sequence that is defined by the given recurrence relation, then attempt to get such a formula by expanding A(x) into a power series by any method you can think of. In particular, if A(x) is a rational function (quotient of two polynomials), then success will result from expanding in partial fractions and then handling each of the resulting terms separately.
multiplying by $x^n$ on LHS was easy, it gave $A(x) - 3x - 1$ assuming $A(x) = \sum_{n=0}^{\infty}a_n \cdot x^n$. But when I try the same on the RHS, i am running into trouble. I get $$RHS = \sum_{n=2}^{\infty}a_{n - 1} \cdot a_{n - 2} \cdot x^n$$. I do not know how to express the intermediate form attained in terms of $A(x)$. Any hints on how this can be achieved? Because I am a beginner in generating functions, I have to ask this : Is it even solvable? Is there a special name for such class of generating functions? Thanks in advance.