Given a generating function equation of the form -
$$ f(x) = A.x.f(x)^2 + B.x.f(x) + C $$
for the sequence $ f(x) = \sum_{n=0}^{\infty} a_n.x^n $. How to find the corresponding recursive relation?
This type of generating function is quite common, for ex- Schröder number's generating function equation is of the form -
$$ f(x) = x.f(x)^2 + x.f(x) + 1 $$, i.e. the former equation with $A=B=C=1$. It has the recursive relation as follows -
$$ S(n)=\frac{1}{n+1}\left((6n-3)S(n-1)-(n-2)S(n-2)\right) $$ with $S(0)=1$ and $S(1)=2$.
I was reading a paper where the author told of differentiating the equation w.r.t to $x$ and then expand to power series in $x$. But, the complete procedure was not clear. Any help is appreciated.
$$f(x) = x.f(x)^2 + x.f(x) + 1 \implies x.f(x)^2 + (x-1)f(x) + 1 = 0$$
$$f(x) = \frac{(1-x) \pm \sqrt{(x-1)^2 - 4x}}{2x} = \frac{(1-x) \pm \sqrt{1-6x+x^2}}{2x}$$
To get recurrence from this (and taking the negative root): $$(1-x) - \sum_{n=0}^{\infty} 2xf_nx^n = (1-3x) - \sum_{n=2}^{\infty} 2f_{n-1}x^n = \sqrt{1-6x+x^2}$$
Squaring we get:
$$(1-3x)^2 + (\sum_{n=2}^{\infty} 2f_{n-1}x^n)^2 - 2(1-3x)\sum_{n=2}^{\infty} 2f_{n-1}x^n = 1 - 6x + x^2$$
$$2x^2 + (\sum_{n=2}^{\infty} f_{n-1}x^n)^2 - \sum_{n=2}^{\infty} f_{n-1}x^n +3x\sum_{n=2}^{\infty} f_{n-1}x^n = 0$$
Rearranging indices, we get:
$$(\sum_{n=2}^{\infty} f_{n-1}x^n)^2 - \sum_{n=3}^{\infty} f_{n-1}x^n +3\sum_{n=3}^{\infty} f_{n-2}x^n = 0$$
Consider first term: $$(\sum_{n=2}^{\infty} f_{n-1}x^n)^2 = (f_1x^2 + f_2x^3 + \ldots f_{n-3}x^{n-2} + ...)(f_1x^2 + f_2x^3 + \ldots f_{n-3}x^{n-2} + ...)$$
The coefficient of $x^n$ will be of the form:
$$\sum_{i=1}^{n-3} f_if_{n-i-2}$$
So we will get:
$$f_{n-1} - 3f_{n-2} = \sum_{i=1}^{n-3} f_if_{n-i-2} = \sum_{i=0}^{n} f_{i+1}f_{n-i+1}$$