Recurrence relation from Generating function - how to find recurrence relation??

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.

• You could differentiate and solve for $f(x)^2$ in terms of $f'(x)$, then substitute that back into the original recurrence. But I got $$f(x) = \frac{xf'(x)(1-Bx)+C}{1+2Ax^2f'(x)}$$ which is a bit messy. Apr 8, 2018 at 14:00
• @Math1000 I am not clear how to proceed from here, do you know the proof for recurrence of Schröder numbers? Or, do you know of any source? Apr 8, 2018 at 14:13
• I think the recurrence is incorrect. $S(2) = ((6*2 -9)S(1) - (2-3)S(0))/2 = 3.5$
– sku
Apr 10, 2018 at 0:19
• @sku sorry for that, I have corrected it now. Apr 11, 2018 at 5:30

$$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}$$

• Note for readers: $f_1 = 2$, this could help to follow the rearranging indices part of the proof. +1. Apr 10, 2018 at 14:40