算法分析中经常遇到需要求解递推式的情况，即将递推式改写为等价的封闭形式。例如汉诺塔问题的时间复杂度递推形式为T(n)=2T(n−1)+1(n≥1)，可以解出封闭形式为T(n)=2n−1(设初始状态T(0)=0)。

因为递推式求解的重要性，许多算法书籍对其有专门介绍。Donald Knuth在Concrete Mathematics一书中多个章节都涉及递推式求解方法。算法导论也在第四章中专门论述的这个主题。

在这些相关论述中，主要介绍了一些启发式方法，这些方法往往需要一些特殊的技巧和灵感才能完成。

而本文将论述一种纯代数式的方法，这种方法将求解递推式转化为求解一个多项式的根和求解一组线性方程组，这样就使得整个求解过程不依赖于太多技巧，因此具有更好的易用性。

本文首先会给出两个例子：如何使用纯代数方法求解斐波那契数列和汉诺塔递推式；然后会借助线性代数论述这种方法背后的数学意义，说明线性递推式与线性方程的内在联系以及这种解法的数学原理；最后将例子中的方法推广到一般情况。

示例

例1：斐波那契数列

斐波那契数列大家应该很熟悉了，这里不再赘述，直接进入问题。

问题

设斐波那契数列为由如下递推式定义的数列：

求解T(n)的封闭形式(也就是斐波那契数列的通项公式)。

求解

首先忽略初始条件，考虑递推式T(n)=T(n−2)+T(n−1)。可以对解的形式进行一个猜测T(n)=qn(这个不是瞎猜的，实际上可以证明线性递推式都遵循这种形式)。那么，递推式可以重写为：

更多请见原文：http://blog.codinglabs.org/articles/linear-algebra-for-recursion.html