什么是线性齐次递推方程？

递推方程中只由数列项的线性变换组成，不包含常数项
$a_n=c_1\ast c_{n-1}+c_2\ast a_{n-2}+...+c_k\ast a_{n-k}$

例如斐波那契数列
$a_n=a_{n-1}+a_{n-2}$

如何求线性齐次递推方程的通项公式？

解特征方程
$x^k=c_1\ast x^{i-1}+c_2\ast x^{i-2}+...+c_k$

获得 m 个根，假设根 $p_i$有$h_i$ 个重根，

那么通项公式为
$a_n={\sum }_{i=1}^m{\sum }_{j=0}^{h_i-1}{C}_{ij}\ast n^j\ast p_i^n$

求解斐波那契数列的通项公式

斐波那契数列
$a_n=a_{n-1}+a_{n-2}$

解特征方程
$x^2=x+1$

解得
$x_1=\frac{1+\sqrt{5}}{2}$
$x_2=\frac{1-\sqrt{5}}{2}$

于是斐波那契数列通解是
$a_n=C_1\ast (\frac{1+\sqrt{5}}{2}{)}^n+C_2\ast (\frac{1-\sqrt{5}}{2}{)}^n$

当 $a_1=1,a_2=1$，可求得 $C_1=\frac{1}{\sqrt{5}},C_2=-\frac{1}{\sqrt{5}}$

题型枚举

1. 求斐波那契数列第 n 项的后三位

解析：直接使用递推公式快速幂算法，并模 1000

2. 求斐波那契数列第 n 项的位数

解析：使用通项公式，由于 $(\frac{1-\sqrt{5}}{2}{)}^n$ 的绝对值小于 1，我们可以根据 $\frac{1}{\sqrt{5}}\ast (\frac{1+\sqrt{5}}{2}{)}^n$ 来估算位数，只需要对 $\frac{1}{\sqrt{5}}\ast (\frac{1+\sqrt{5}}{2}{)}^n$ 求以 10 为底的对数，整数部分就是位数

3. 求斐波那契数列第 n 项的首位

解析：同上题，把小数部分拿出来再求 10 的指数即可

4. 求解 $(1+\sqrt{2}{)}^n$ 的后 3 位

解析：$(1+\sqrt{2}{)}^n+(1-\sqrt{2}{)}^n$ 是递推方程 $a_n=2a_{n-1}+a_{n-2}$ 的通解，由于 $(1-\sqrt{2}{)}^n$ 的绝对值小于 1，所以我们可以使用递推方程快速幂求出 $a_n$ 的解，再判断 $(1-\sqrt{2}{)}^n$ 的符号即可求出结果

总结

如果需要后 n 位的精确值，用递推公式快速幂算法

如果需要前 n 位的值，估算位数，尝试求通项公式，看看能否消掉干扰项，剩下一个指数函数