生成函数

组合数学

---

求满足$\ h_0=1,h_1=-2\ $的递推关系

$$h_n=5h_{n-1}-6h_{n-2}$$

我们设$\ g(x)=h_0+h_1x+h_2x^2+h_3x^3+\ldots h_nx^n+\ldots\ $
$\ \ \ \ \ \ g(x)=\ \ \ \ h_0\ +h_1x+h_2x^2+\ \ \ldots \ +h_nx^n+\ \ldots$
$-5xg(x)=\ \ \ \ \ \ \ -5h_0x-5h_1x^2-\ldots\ -5h_{n-1}x^n\ \ldots$
$6x^2g(x)=\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +\ 6h_0x^2+\ldots\ +6h_{n-2}x^n\ \ldots$
$(1-5x+6x^2)g(x)=h_0+(h1-5h_0)x+(h2-5h_1+6h_0)x^2+\ldots+(h_n-5h_{n-1}+6h_{n-2})x^n+\ldots$
由于$\ h_n-5h_{n-1}+6h_{n-2}=0\ $
所以$(1-5x+6x^2)g(x)=h_0+(h1-5h_0)x=1-7x$

$$g(x)=\frac{1-7x}{1-5x+6x^2}=\frac{1-7x}{(1-2x)(1-3x)}$$
我们设 $$g(x)=\frac{a}{1-2x}+\frac{b}{1-3x}$$
联立解方程得 $$g(x)=5\times\frac{1}{1-2x}+(-4)\times\frac{1}{1-3x}$$
$$=5(1+(2x)+(2x)^2+\ldots+(2x)^n+\ldots)-4(1+(3x)+(3x)^2+\ldots+(3x)^n+\ldots)$$
则 $$h_n=5\times 2^n-4\times 3^n$$