1.暴力
2.矩阵
3.母函数
我太菜了,不懂原理
设$F(x)=\sum\limits_{i=0}^{\infty} f(i)x^i$,
有$xF(x)=\sum\limits_{i=1}^{\infty} f(i-1)x^i$,$x^2F(x)=\sum\limits_{i=2}^{\infty} f(i-2)x^i$
那么$F(x)=xF(x)+x^2F(x)+x$,最后一项是$[x^1]$
$F(x)=\frac{x}{1-x-x^2}$,然后需要把分母的x弄掉
$F(x)=\frac{-x}{(x-x_0)(x-x_1)}$此处解出$x_0,x_1$
$F(x)=\frac{A}{x-x_0}+\frac{B}{x-x_1},A+B==-1,Ax_1+Bx_0==0$此处解出$A,B$
$F(x)=\frac{-A}{x_0}\frac{1}{1-\frac{x}{x_0}}+\frac{-B}{x_1}\frac{1}{1-\frac{x}{x_1}}$
此时分母的x已经可以去掉了,因$\frac{1}{1-x}=\sum\limits_{i=0}^{\infty} x^i$
$F(x)=\sum\limits_{i=0}^{\infty} (\frac{-A}{x_0^i}+\frac{-B}{x_1}^i)x^i$故$f(i)=-A(\frac{1}{x_0})^i-B(\frac{1}{x_1})^i$
4.特征根法
我太菜了,同样不懂原理,而且只会二阶
$f_{n+2}=C_1f_{n+1}+C_2f_n$
设$f_{n+2}-xf_{n+1}=y(f_{n+1}-xf_n)$
有$x+y=C_1,xy=-C_2$,把方程中的y消去
得到$x^2=C_1x+C_2$,即特征方程,解出$x_1,x_2$,代入回方程组得到$y_1,y_2$
其实$x_1=y_2,x_2=y_1$
那么
$f_{n+2}-x_1f_{n+1}=y_1(f_{n+1}-x_1f_n)=y_1^{n+1}(f_1-x_1f_0)$
$f_{n+2}-x_2f_{n+1}=y_2(f_{n+1}-x_2f_n)=y_2^{n+1}(f_1-x_2f_0)$
加减消元去掉$f_{n+1}$得
$(x_2-x_1)f_{n+2}=(f_1-x_1f_0)y_1^{n+1}x_2-(f_1-x_2f_0)y_2^{n+1}x_1$
当$(x2-x1)!=0$时,显然已经形成了只关于$x_1,x_2$的通项公式
等于0时,这个网址有讲(不过全网无了貌似暂时没法填坑了)
upd:$x_2==x1$时,$f_{n+2}-xf_{n+1}=x^{n+1](f_1-xf_0)$
$\frac{f_{n+2}}{x^{n+2}}-\frac{f_{n+1}}{x^{n+1}}=\frac{f_1}{x}-f_0$
那么$\frac{f_n}{x^n}$是等差数列
那么可以求出通项公式了懒得写了
来源:https://www.cnblogs.com/yxsplayxs/p/13369882.html