齐次线性递推求通项公式
cancan123456
·
·
个人记录
为照顾那些一看到 \sum 就头晕的同学，本文将不出现任何求和符号。
给定一递推式：
f_n=a_0f_{n-1}+a_1f_{n-2}+\cdots+a_{k-1}f_{n-k}
求 f_n 的通项公式。
有很多种方法。
生成函数法
设 f_n 的生成函数为 F(x)，由
F(x)=f_0x^0+f_1x^1+f_2x^2+\cdots+f_kx^k+\cdots
可知：
a_0x^1F(x)=a_0f_0x^1+a_0f_1x^2+a_0f_2x^3+\cdots+a_0f_{k-1}x^k+\cdots
a_1x^2F(x)=a_1f_0x^2+a_1f_1x^3+a_1f_2x^4+\cdots+a_1f_{k-2}x^k+\cdots
a_2x^3F(x)=a_2f_0x^3+a_2f_1x^4+a_2f_2x^5+\cdots+a_2f_{k-3}x^k+\cdots
\cdots\cdots\cdots\cdots
a_{k-1}x^kF(x)=a_{k-1}f_0x^k+a_{k-1}f_1x^{k+1}+a_{k-1}f_2x^{k+2}+\cdots
将以上各式相加，可得：
(a_0x^1+a_1x^2+a_2x^3+\cdots+a_{k-1}x^k)F(x)=a_0f_0x^1+(a_0f_1+a_1f_0)x^2+(a_0f_2+a_1f_1+a_2f_0)x^3+\cdots+(a_0f_{k-1}+a_1f_{k-2}+\cdots+a_{k-1}f_0)x^{k-1}+f_kx^k+f_{k+1}x^k+\cdots
用
F(x)=f_0x^0+f_1x^1+f_2x^2+\cdots+f_kx^k+\cdots
减去上式，可得：
(1-a_0x^1-a_1x^2-\cdots-a_{k-1}x^k)F(x)=f_0x^0+(f_1-a_0f_0)x^1+(f_2-a_0f_1-a_1f_0)x^2+\cdots+(f_{k-1}-a_0f_{k-1}-a_1f_{k-2}-\cdots-a_{k-1}f_0)
F(x)=\frac{f_0x^0+(f_1-a_0f_0)x^1+(f_2-a_0f_1-a_1f_0)x^2+\cdots+(f_{k-1}-a_0f_{k-1}-a_1f_{k-2}-\cdots-a_{k-1}f_0)}{1-a_0x^1-a_1x^2-\cdots-a_{k-1}x^k}
我们将分母暴力分解成 (1-x_1x)(1-x_2x)\cdots(1-x_kx)，所以：
F(x)=\frac{f_0x^0+(f_1-a_0f_0)x^1+(f_2-a_0f_1-a_1f_0)x^2+\cdots+(f_{k-1}-a_0f_{k-1}-a_1f_{k-2}-\cdots-a_{k-1}f_0)}{(1-x_1x)(1-x_2x)\cdots(1-x_kx)}
然后暴力裂项，即求出 A_1,A_2,\dots,A_k 使得：
F(x)=\frac{A_1}{(1-x_1x)}+\frac{A_2}{(1-x_2x)}+\cdots+\frac{A_k}{(1-x_kx)}
由
\frac1{1-kx}=(kx)^0+(kx)^1+(kx)^2\cdots=k^0x^0+k^1x^1+k^2x^2+\cdots
可得：
F(x)=A_1x_1^0x^0+A_1x_1^1x^1+A_1x_1^2x^2+\cdots+A_2x_2^0x^0+A_2x_2^1x^1+A_3x_3^2x^2+\cdots+A_3x_3^0x^0+A_3x_3^1x^1+A_3x_3^2x^2+\cdots+A_kx_k^0x^0+A_kx_k^1x^1+A_kx_k^2x^2+\cdots
然后提取出 x^n 的系数：
F(x)=(A_1x_1^0+A_2x_2^0+\cdots+A_kx_k^0)x^0+(A_1x_1^1+A_2x_2^1+\cdots+A_kx_k^1)x^1+(A_1x_1^2+A_2x_2^2+\cdots+A_kx_k^2)x^2+\cdots+(A_1x_1^n+A_2x_2^n+\cdots+A_kx_k^n)x^n+\cdots
所以：
f_n=A_1x_1^n+A_2x_2^n+\cdots+A_kx_k^n
我们举几个例子：
- 斐波那契数列
k=2
a_0=1,a_1=1
f_0=0,f_1=1
设 f_n 的生成函数为 F(x)，根据上面的式子很容易得到：
F(x)=\frac{f_0x^0+(f_1-a_0f_0)x^1}{1-a_0x^1-a_1x^2}
F(x)=\frac x{1-x-x^2}
设
(1-x_1x)(1-x_2x)=1-x-x^2
展开可得
1-(x_1+x_2)x+x_1x_2x^2=1-x-x^2
也就是：
\begin{cases}-(x_1+x_2)=-1\\x_1x_2=-1\end{cases}
解得（仅取一组解）：
\begin{cases}x_1=\dfrac{1+\sqrt5}2\\x_2=\dfrac{1-\sqrt5}2\end{cases}
所以：
F(x)=\frac x{\left(1-\dfrac{1+\sqrt5}2x\right)\left(1-\dfrac{1-\sqrt5}2x\right)}
设
F(x)=\frac{A_1}{1-\dfrac{1+\sqrt5}2x}+\frac{A_2}{1-\dfrac{1-\sqrt5}2x}
则：
F(x)=\frac{\left(1-\dfrac{1-\sqrt5}2x\right)A_1+\left(1-\dfrac{1+\sqrt5}2x\right)A_1}{\left(1-\dfrac{1+\sqrt5}2x\right)\left(1-\dfrac{1-\sqrt5}2x\right)}
F(x)=\frac{A_1-\dfrac{1-\sqrt5}2A_1x+A_2-\dfrac{1+\sqrt5}2A_2x}{\left(1-\dfrac{1+\sqrt5}2x\right)\left(1-\dfrac{1-\sqrt5}2x\right)}
F(x)=\frac{(A_1+A_2)-\left(\dfrac{1-\sqrt5}2A_1+\dfrac{1+\sqrt5}2A_2\right)x}{\left(1-\dfrac{1+\sqrt5}2x\right)\left(1-\dfrac{1-\sqrt5}2x\right)}
所以：
\begin{cases}A_1+A_2=0\\-\left(\dfrac{1-\sqrt5}2A_1+\dfrac{1+\sqrt5}2A_2\right)=1\end{cases}
解得：
\begin{cases}A_1=\dfrac1{\sqrt5}\\A_2=-\dfrac1{\sqrt5}\end{cases}
所以：
F(x)=\frac{\dfrac1{\sqrt5}}{1-\dfrac{1+\sqrt5}2x}-\frac{\dfrac1{\sqrt5}}{1-\dfrac{1-\sqrt5}2x}
a_n=\frac1{\sqrt5}\left[\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right]
- A084247
k=2
a_0=2,a_1=-1
f_0=1,f_1=2
设 f_n 的生成函数为 F(x)，则：
F(x)=\frac1{1-2x+x^2}
F(x)=\frac{A_1}{1-x}+\frac{A_2}{1-x}
然后好像算不出来了……
我们发现这种情况是因为 1-2x+x^2 出现了重根，所以我们给出如下定理：
结束
结束
结束
结束
结束
结束
结束