1.暴力
2.矩阵
3.母函数
我太菜了，不懂原理
设$F(x)=sumlimits_{i=0}^{infty} f(i)x^i$,
有$xF(x)=sumlimits_{i=1}^{infty} f(i-1)x^i$，$x^2F(x)=sumlimits_{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}=sumlimits_{i=0}^{infty} x^i$
$F(x)=sumlimits_{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}$是等差数列
那么可以求出通项公式了懒得写了