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

Revision en3, by jianglyFans, 2020-07-25 06:24:18

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) ?


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

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)