以下为文化课内容
很多题目中，数列要转化为等差/等比数列解决。
然而使用生成函数可以解决大量数列递推问题。
以(a_n=4a_{n-1}-4a_{n-2})为例。
(a_1=4,a_2=12)
移项得到(a_n-4a_{n-1}+4a_{n-2}=0)
构造多项式(f(x)=sum^{inf}_{i=1}x^ia_i)
(f(x)-4xf(x)+4x^2f(x)=sum_{i=1}^{inf}a_nx^i-sum_{i=2}^{inf}4a_{n-1}x^i+sum_{i=3}^{inf}4a_{n-2}x^i)
(f(x)-4xf(x)+4x^2f(x)=sum_{i=3}^{inf}(a_n-4a_{n-1}+4a_{n-2})x^i+4x+12x^2-16x^2=f(x)-4xf(x)+4x^2f(x)=sum_{i=3}^{inf}(a_n-4a_{n-1}+4a_{n-2})x^i+4x+8x^2=4x-4x^2)
((2x-1)^2f(x)=4x-4x^2)
(f(x)=cfrac{4x-4x^2}{(2x-1)(2x-1)})
(f(x)=(4x-4x^2)cfrac{1}{1-2x}cfrac{1}{1-2x})
(f(x)=(4x-4x^2)(sum_{i=0}^{inf}2^ix^i)(sum_{i=0}^{inf}2^ix^i)=4x(sum_{i=0}^{inf}2^ix^i)(sum_{i=0}^{inf}2^ix^i)-4x^2(sum_{i=0}^{inf}2^ix^i)(sum_{i=0}^{inf}2^ix^i))
([x^i]f(x)=4sum_{j=0}^{i-1}2^{i-1}-4sum_{j=0}^{i-2}2^{i-2}=2^{i+1}i+2^i(i-1)=a_i)
计算量有点大。