Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

How to get recurrence formula of an array by it's generating function ?

Revision en2, by jianglyFans, 2020-07-24 14:57:03

zscoder introduced Generating functions in Competitive Programming 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) ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English jianglyFans 2020-07-25 06:37:06 42
en3 English jianglyFans 2020-07-25 06:24:18 1362
en2 English jianglyFans 2020-07-24 14:57:03 385 Tiny change: 'ction:\n\n3232\n\frac{3}{2}\n\n\n\n' -> 'ction:\n\n$$\n\frac{3}{2}\n$$\n\n\n' (published)
en1 English jianglyFans 2020-07-24 14:13:19 504 Initial revision (saved to drafts)