algo-aha

二阶递推式 $F(n)=aF(n-1)+bF(n-2)$，先构造再求参数。

假设 $F(n)+yF(n-1)=x(F(n-1)+yF(n-2))$，$F(n)=(x-y)F(n-1)+xyF(n-2)$，设$a=x-y$，$b=xy$，有$b=x(x-a)$，$x^2=ax+b$。

$x^2=ax+b$ 叫做特征方程，解方程得特征根$x_1$和$x_2$，$F(n)$将可以用$x_1$和$x_2$表示成$F(n)=c{x}_1^n+d{x}_2^n$。代入初始值$F(0)$和$F(1)$，求得c和d。