[user:zscoder,2020-07-24] introduced [Generating functions in Competitive Programming](https://mirror.codeforces.com/blog/entry/77468) in his blog, which give a method to get the formula of general term of a array by it's generating function. ↵
↵
But sometime the generating function is somewhat complicated, for instance, the array http://oeis.org/A054726 which has generating function:↵
↵
$$↵
1 + \frac{3}{2} z - z^2 - \frac{z}{2} \sqrt{1 - 12 z + 4 z^2}↵
$$↵
↵
and we can calculate the first n term by **poly sqrt with fft** in $O(n \log n)$↵
↵
But this array have a recurrence formula:↵
$$↵
a_{n} = \frac{ (12 n - 30) a_{n-1} - (4 n - 16) a_{n-2} }{n-1}↵
$$↵
↵
which will be much easy to calculate.↵
↵
**My question is how can I get recurrence formula by it's generating function in general(or some special form) ? ** ↵
↵
-----------------------------------------------------------------------------------------------------------------------------↵
↵
**I know how to do this now, thanks qwaszx who give me a hint.**↵
↵
If $f(z) = p(z)^{ \frac{1}{m} }$ is generating function of $a_n$, where $p(z)$ is a polynomial. then↵
↵
$$↵
p(z) f'(z) = \frac{1}{m} p(z) p'(z)↵
$$↵
↵
compare the coefficient of $z^n$， and we will get the recurrence formula of $a_n$↵
↵
**Let us calculate the above example**: $f(z) = 1 + \frac{3}{2} z - z^2 - \frac{z}{2} \sqrt{1 - 12 z + 4 z^2}$↵
↵
let $b_n = a_{n+1}$ and $g(z)$ is generating function of $b_n$, then↵
↵
$$↵
g(z) = \sum_{n = 0} ^{\infty} a_{n+1} z ^ {n} = \frac{ f(z) - f(0)}{z} = \frac{3}{2} - z - \frac{1}{2} \sqrt{1 - 12 z + 4 z^2}↵
$$↵
↵
so we get differential of $g(z)$↵
↵
$$↵
g'(z) = -1 - \frac{2z - 3}{\sqrt{1 - 12 z + 4 z^2}} = \frac{3-2z - \sqrt{1 - 12 z + 4 z^2}}{\sqrt{1 - 12 z + 4 z^2}}↵
$$↵
↵
and↵
↵
$$↵
(1 - 12z + 4 z^2) g'(z) = (3-2z - \sqrt{1 - 12 z + 4 z^2}) (\sqrt{1 - 12 z + 4 z^2}) = (3 - 2z) (3-2z - 2g(z)) - (1 - 12z + 4 z^2 = (4z - 6) g(z) + 8↵
$$↵
↵
compare the coefficient of $z^n$, we have $(n + 1)b_{n+1} - 12 n b_n + 4(n-1)b_{n-1} = 4 b_{n-1} - 6 b_n$, so↵
↵
$$↵
(n+1)a_{n+2} = (12 n - 6) a_{n+1} - (4n - 8) a_n↵
$$↵
↵
so we archive our goal: $a_{n} = \frac{ (12 n - 30) a_{n-1} - (4 n - 16) a_{n-2} }{n-1}$↵
↵
↵
But sometime the generating function is somewhat complicated, for instance, the array http://oeis.org/A054726 which has generating function:↵
↵
$$↵
1 + \frac{3}{2} z - z^2 - \frac{z}{2} \sqrt{1 - 12 z + 4 z^2}↵
$$↵
↵
and we can calculate the first n term by **poly sqrt with fft** in $O(n \log n)$↵
↵
But this array have a recurrence formula:↵
$$↵
a_{n} = \frac{ (12 n - 30) a_{n-1} - (4 n - 16) a_{n-2} }{n-1}↵
$$↵
↵
which will be much easy to calculate.↵
↵
**My question is how can I get recurrence formula by it's generating function in general(or some special form) ?
↵
-----------------------------------------------------------------------------------------------------------------------------↵
↵
**I know how to do this now, thanks qwaszx who give me a hint.**↵
↵
If $f(z) = p(z)^{ \frac{1}{m} }$ is generating function of $a_n$, where $p(z)$ is a polynomial. then↵
↵
$$↵
p(z) f'(z) = \frac{1}{m} p(z) p'(z)↵
$$↵
↵
compare the coefficient of $z^n$， and we will get the recurrence formula of $a_n$↵
↵
**Let us calculate the above example**: $f(z) = 1 + \frac{3}{2} z - z^2 - \frac{z}{2} \sqrt{1 - 12 z + 4 z^2}$↵
↵
let $b_n = a_{n+1}$ and $g(z)$ is generating function of $b_n$, then↵
↵
$$↵
g(z) = \sum_{n = 0} ^{\infty} a_{n+1} z ^ {n} = \frac{ f(z) - f(0)}{z} = \frac{3}{2} - z - \frac{1}{2} \sqrt{1 - 12 z + 4 z^2}↵
$$↵
↵
so we get differential of $g(z)$↵
↵
$$↵
g'(z) = -1 - \frac{2z - 3}{\sqrt{1 - 12 z + 4 z^2}} = \frac{3-2z - \sqrt{1 - 12 z + 4 z^2}}{\sqrt{1 - 12 z + 4 z^2}}↵
$$↵
↵
and↵
↵
$$↵
(1 - 12z + 4 z^2) g'(z) = (3-2z - \sqrt{1 - 12 z + 4 z^2}) (\sqrt{1 - 12 z + 4 z^2}) = (3 - 2z) (3-2z - 2g(z)) - (1 - 12z + 4 z^2 = (4z - 6) g(z) + 8↵
$$↵
↵
compare the coefficient of $z^n$, we have $(n + 1)b_{n+1} - 12 n b_n + 4(n-1)b_{n-1} = 4 b_{n-1} - 6 b_n$, so↵
↵
$$↵
(n+1)a_{n+2} = (12 n - 6) a_{n+1} - (4n - 8) a_n↵
$$↵
↵
so we archive our goal: $a_{n} = \frac{ (12 n - 30) a_{n-1} - (4 n - 16) a_{n-2} }{n-1}$↵
↵
