[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{2 + 3 z - z^2 - z \sqrt{1 - 12 z + 4 z^2}{2}↵
$$↵
↵
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) ?
↵
But sometime the generating function is somewhat complicated, for instance, the array http://oeis.org/A054726 which has generating function:↵
↵
$$↵
1 + \frac{
$$↵
↵
$$↵
↵
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) ?
