递推式的一般代数解法

算法分析中经常遇到需要求解递推式的情况，即将递推式改写为等价的封闭形式。例如汉诺塔问题的时间复杂度递推 形式为 T (n)=2T (n−1)+1 (n≥1) ，可以解出封闭形式为 T (n)=2 n −1 （设初始状态 T (0)=0 ）。 因为递推式求解的重要性，许多算法书籍对其有专门介绍。Donald Knuth在Concrete Mathematics一书中多个章节都 涉及递推式求解方法。算法导论也在第四章中专门论述的这个主题。 在这些相关论述中，主要介绍了一些启发式方法，这些方法往往需要一些特殊的技巧和灵感才能完成。 而本文将论述一种纯代数式的方法，这种方法将求解递推式转化为求解一个多项式的根和求解一组线性方程组，这样 就使得整个求解过程不依赖于太多技巧，因此具有更好的易用性。