递归方程组解的渐进阶的求法——差分方程法
这里只考虑形如：
T(n)=c1T(n-1)+c2T(n-2)+…+ ckT(n-k)+f(n)，n≥k (6.18)
的递归方程。其中ci (i=l，2，…，k)为实常数，且ck≠0。它可改写为一个线性常系数k阶非齐次的差分方程：
T(n)-c1T(n-1)- c2T(n-2)-…-ckT(n-k)=f(n)，n≥k (6.19)
(6.19)与线性常系数k阶非齐次常微分方程的结构十分相似，因而解法类同。限于篇幅，这里直接给出(6.19)的解法，略去其正确性的证明。
第一步，求(6.19)所对应的齐次方程：
T(n)-c1T(n-1)- c2T(n-2)-…-ckT(n-k)=0 (6.20)
的基本解系：写出(6.20)的特征方程：
C(t)=tk-c1tk-1-c2tk-2 -…-ck=0 (6.21)
若t=r是(6.21)的m重实根，则得(6.20)的m个基础解rn，nrn，n2rn，…，nm-1rn；若ρeiθ和ρe-iθ是(6.21)的一对l重的共扼复根，则得(6.20)的2l个基础解ρncosnθ，ρnsinnθ，nρncosnθ，nρnsinnθ，…，nl-1ρncosnθ，nl-1ρncosnθ。如此，求出(6.21)的所有的根，就可以得到(6.20)的k个的基础解。而且，这k个基础解构成了(6.20)的基础解系。即(6.20)的任意一个解都可以表示成这k个基础解的线性组合。
第二步，求(6.19)的一个特解。理论上，(6.19)的特解可以用Lagrange常数变易法得到。但其中要用到(6.20)的通解的显式表达，即(6.20)的基础解系的线性组合，十分麻烦。因此在实际中，常常采用试探法，也就是根据f(n)的特点推测特解的形式，留下若干可调的常数，将推测解代人(6.19)后确定。由于(6.19)的特殊性，可以利用迭加原理，将f(n)线性分解为若干个单项之和并求出各单项相应的特解，然后迭加便得到f(n)相应的特解。这使得试探法更为有效。为了方便，这里对三种特殊形式的f(n)，给出(6.19)的相应特解并列在表6-1中，可供直接套用。其中pi，i=1,2,…,s是待定常数。
表6-1 方程(6.19)的常用特解形式
| f(n)的形式 | 条 件 | 方程(6.19)的特解的形式 |
|---|---|---|
| an | C(a)≠0 |  |
| a是C(t)的m重根 |  | |
| ns | C(1)≠0 |  |
| 1是C(t)的m重根 |  | |
| nsan | C(a)≠0 |  |
| a是C(t)的m重根 |  |
第三步，写出(6.19)即(6.18)的通解
(6.22)
其中{
Ti(n)，i=0,1,2,…,n}是(6.20)的基础解系，g(n)是(6.19)的一个特解。然后由(6.18)的初始条件T(i)=Ti ，i=1,2,…,k-1
来确定(6.22)中的待定的组合常数{
ai}，即依靠线性方程组
或
解出{
ai}，并代回(6.22)。其中βj=Tj-g(j)，j=0,1,2,…,k-1。第四步，估计(6.22)的渐近阶，即为所要求。
下面用两个例子加以说明。
例l 考虑递归方程
它的相应特征方程为：
C(t)=t2-t-1=0
解之得两个单根
和
。相应的(6.20)的基础解系为{
F(n)=a0r0n +a1r1n- 8
令其满足初始条件，得二阶线性方程组：
或
或
解之得
，
，从而
于是
。
例2 考虑递归方程
T(n)=4T(n-1)-4T(n-2)+2nn (6.23)
和初始条件T(0)=0，T(1)=4/3。
它对应的特征方程(6.21)为
C(t)=t2-4t+4=0
有一个两重根r =2。故相应的(6.20)的基础解系为{2n，2nn}。由于f(n)=2nn，利用表6-1，相应的(6.19)的一个特解为
T*(n)=n2(p0+p1n)2n，
代人(6.23)，定出p0=1/2，p1=1/6。因此相应的(6.19)的通解为：
T(n)=a02n+a1n2n+n2(1/2+n/6)2n，
令其满足初始条件得a0=a1=0，从而
T(n)=n2(1/2+n/6)2n
于是T(n)=θ(n32n)。