递推式的一般代数解法

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