特征方程教程
我们常常会遇到一些递推式，例如著名的斐波那契数列： F n + 2 = F n + F n + 1 ( F 1 = 1 , F 2 = 1 ) F n + 2 = F n + F n + 1 ( F 1 = 1 , F 2 = 1 ) .在这种情况下，往往难以推出通项。 如果我们要编程求 F n F n ，只需要矩阵快速幂就行了——可以在 O ( log n ) O ( log n ) 的时间复杂度内求出答案。有没有更“数学”的解法，来求出通项公式呢？ 我们尝试用一种叫做“特征方程”的科技，来解决这类问题。实际上，这玩意很简单，个中原理也不复杂。（有公式恐惧症的不要跑呀，这篇文章没几个公式的） 找规律 首先我们来看一个漂亮的例子： a n + 2 = 5 ⋅ a n + 1 − 6 ⋅ a n a n + 2 = 5 ⋅ a n + 1 − 6 ⋅ a n 真是让人摸不着头脑？那么现在给出一个已知条件： f n = 2 n − 1 f n = 2 n − 1 这个数列满足上述递推式。 { 1 , 2 , 4 , 8 , 16 ⋯ } { 1 , 2 , 4 , 8 , 16 ⋯ } ，代入一看，果然。 有没有更一般的规律？我们来发掘一下…… { 3 ⋅ f n } = { 3 , 6 , 12 , 24 , 48 ⋯ } { 3 ⋅ f n } = { 3 , 6 , 12 , 24 , 48 ⋯ } 这个数列也满足递推式！ 多找几个例子，我们注意到一个事实： 若等比数列 { f n } { f n } 满足递推式，那么 { λ ⋅ f n } { λ ⋅ f n } 也满足递推式。 证明：把原递推式两边都乘上 λ λ 就行了，不碍事。 另一个真相 现在告诉您另一个事实： g n = 3 n − 1 g n = 3 n − 1 这个等比数列，竟然也满足原递推式。 不信么？ { g n } = { 1 , 3 , 9 , 27 , 81 ⋯ } { g n } = { 1 , 3 , 9 , 27 , 81 ⋯ } 代入，发现真的也行！ 根据我们刚刚的结论， { λ ⋅ g n } { λ ⋅ g n } 也是满足递推式的。能不能把 f f 和 g g 综合起来呢？ { 3 f n + 5 g n } = {...