递归及递归算法分析.

Presentation on theme: "递归及递归算法分析."— Presentation transcript:

1 递归及递归算法分析

2 主要内容 递归的实现机制 递归算法编制 递归关系式求解

3 递归的实现机制 1.递归的概念 直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。
直接调用自身的算法称为直接递归 间接调用自身的算法称为间接递归

4 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

5 2.子程序的内部实现原理 1）子程序调用的一般形式 一次调用 N次调用 嵌套调用 平行调用 主程序 call A 1： 主程序 call A
2： 主程序 call A 1： 主程序 call B 1： 子程序A 子程序A 子程序B call B 2： 子程序A 子程序A 子程序B call A 2：

6 2）值的回传 实参和形参的数据传递 值的回传通常有两种形式： 传值 实参的值不发生改变 传地址 实参的值发生改变
传值 实参的值不发生改变 传地址 实参的值发生改变 值的回传通常有两种形式： 两次传值方式：按照指定类型为变参设置相应的存储空间，在执行调用时，将实参值传送给变参在返回时将变参的值传给实参。 传地址：在内部将变参用一个地址替换，调用时，先执行地址传送，将实参地址传送给变参，在执行过程中，对变参的操作实际变成对实参的操作。 实参 变参 1 2 实参 变参 X 地址X

7 3)子程序调用的内部操作 执行调用时，系统完成的操作 返回时，系统完成的操作： 返回地址进栈，为子程序的局部变量开辟空间
为子程序准备数据：计算实参值，并将其值送给形参 转入子程序入口地址 返回时，系统完成的操作： 变参或函数的值保存到回传变量中 从栈顶取返回地址 返回调用程序 将回传变量的值送给实参

8 3.递归过程的内部实现原理 程序A if 出口条件 then 简单语句 else 简单语句；call A ； 1：简单语句； endif endA 递归程序的执行令人担心是否引发死循环。担心是多余的！ 因为每次调用，必有一些数据发生变化，直到出现一组数据终止递归。这组数据就是递归出口。 执行到出口条件 开始出栈 1 。。。

9 递归举例 间接递归 proc p1(n){ if n>0 then 直接递归 if odd(n) then p1(n-1);
print n; else p2(n-1);print n; } proc p2(n){ if n>0 then if n mod 3==0 then p1(n-1) else p2(n-1) 直接递归 proc fact（n） if n=0 then return 1 else return n*fact(n-1)

10 递归函数举例 例1 阶乘函数 阶乘函数可递归地定义为： 边界条件 递归方程
例1 阶乘函数 阶乘函数可递归地定义为： 边界条件 递归方程 边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。

11 递归函数举例 例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为： 边界条件 递归方程 第n个Fibonacci数可递归地计算如下： public static int fibonacci(int n) { if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2); }

12 递归函数举例 例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。
Ackerman函数A(n，m)定义如下：

13 前2例中的函数都可以找到相应的非递归方式定义：
例3 Ackerman函数 前2例中的函数都可以找到相应的非递归方式定义： 但本例中的Ackerman函数却无法找到非递归的定义。

14 例3 Ackerman函数 A(n，m)的自变量m的每一个值都定义了一个单变量函数： M=0时，A(n,0)=n+2
M=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n 。 M=3时，类似的可以推出 M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。

15 例3 Ackerman函数 定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。 定义其逆函数α(n)为：α(n)=min{k｜A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。 α(n)在复杂度分析中常遇到。对于通常所见到的正整数n，有α(n)≤4。但在理论上α(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。

16 N! 例4 排列问题 设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。
例4 排列问题 设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。 设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。 N!

17 r1---t(1)=1 r1、r r1perm(R1) r2perm(R2) t(2)=2*t(1) r1、r2、r3 r1perm(R1) r2perm(R2) r3perm(R3) t(3)=3*T(2) …………….. t(n)=n*t(n-1)

18 例5 整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1， ； 2+2+2， ， ； 。

19 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 ?

20 正整数n的划分由n1=n的划分和n1≤n-1的划分组成。
(1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即 (2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。 (3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1≤n-1的划分组成。 (4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1≤m-1 的划分组成。 不包含m 包含m的划分

21 递归算法设计 用递归求解问题的3个要求： proc f（参数表） if 递归出口 then 简单语句；
问题的描述涉及规模 规模发生变化后，问题性质不改变 问题的解决有出口 proc f（参数表） if 递归出口 then 简单语句； else 简单语句；call f（参数表）；简单语句； endif endf

22

23 例6 Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

24 例6 Hanoi塔问题 public static void hanoi(int n, int a, int b, int c) {
if (n > 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } 在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。 当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。 当n＞1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。 由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。 思考题：如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不变，求移动步数最小的方案。

25 n=3 t(3)=7 n=4 t(4)=15 n=10 t(10)=1023 n=16 t(16)=65534

26 递归小结 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

27 递归算法的时间复杂度分析 递归函数求解 简单递归式求解 master method 递推方程的特征方程求解

28 T(n)=2n-1 public static void hanoi(int n, int a, int b, int c) {
if (n > 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } T(n)=2T(n-1)+O(1) n≥1 n=0 T(n)=2n-1 4

29 简单递归式的求解 1.T(n)=T(n-1)+c1 n>1 c2 n=1 2. T(n)=2T(n/2)+c1 n ≥2
3. T(n)=2T(n/2)+Θ(n) n ≥2 O(1) n<2

30 T( n/2 ) + T( n/2 ) + 1 (n > 1) 例1 T(n) = 0 (n = 1)
令2r=n =2rT(1)+2r-1+。。。+2+1 =(1-2r)/(1-2)=n-1 ∴ T( n ) = n - 1

31 例2 递推关系式： 3 T( n/2 ) + k n (n > 1) k ( n = 1) T (n ) = 解上述递推式： T( n ) = 3 T( n/2 ) + k n = 3 [ 3 T( n/22 ) + k (n / 2 ) ] + k n =32T(n/22)+3k(n/2)+kn =       =3rT(n/2r)+(3/2)r-1kn+….+kn =3rk+ (3/2)r-1kn+….+kn = 3 r+1  k - 2 k n = 3 k 3log2n k n  3 k n k n = O( n )

32 例3 T( n/2 ) + T( n/2 ) + (n - 1) (n > 1) T(n) = (n = 1) 设：n = 2r （ r:非负整数）。 有：T(n) = 2 T(n/2 ) + ( n - 1 ) T(n/2) = 2 T(n/22 ) + (n/2 - 1) T(n/22) = 2 T(n/23 ) + (n/22 - 1)       T(n/2r-1) = 2 T(n/2r ) (n/2r-1 - 1) 2r r r-1 +) T( n ) = 2r T(1) + rn - (2r-1 + 2r-2 +    +20) = nlog2n - n +1 = O(nlog n)

33 Master Method T(n)=aT(n/b)+f(n) a≥1b>1 f(n)是一个非负渐进函数
case1：Ǝ Ɛ>0,使f(n)=O(nlog ba-Ɛ) 即0<f(n)<nlog ba-Ɛ 则T(n)=Θ(nlog ba) case2:Ǝ k≥0,使f(n)= Θ(nlog balgnk) 则T(n)=Θ(nlog balgnk+1) case1：Ǝ Ɛ>0,c>0,使f(n)= Ω(nlog ba+Ɛ) ,af(n/b)<cf(n) 则T(n)=Θ(f(n))

34 例1 T(n)=4T(n/2)+n a=4 b=2 f(n)=O(n2-Ɛ)取Ɛ=1 则T(n)=Θ(n2) 例2 T(n)=4T(n/2)+n2 a=4 b=2 f(n)= Θ(n2lgnk)取K=0 则T(n)=Θ(n2lgn) 例3 T(n)=4T(n/2)+n3 a=4 b=2 f(n)=n3= Ω(nlog ba+Ɛ)取Ɛ=1 且4f(n/2)=n3/2<n3 取c=1 则T(n)=Θ(n3)

35 递推方程的特征方程求解 一、常系数线性递推方程的特征方程解法 1. 齐次常系数线性递推方程的特征方程解法
（1）定义：k阶齐次常系数线性递推方程: (R): H(n) = a1H(n - 1) + a2H(n - 2) +   +akH(n - k) 其中： 1）a1, a2,    , ak为常数； 2）ak  0, n  k。 （2）定义：（R）对应的特征方程: (E): xk - a1x k a2 x k    - a k-1 x - ak = 0

36 (3) （R）的通解 1）若(E)有k个互不同的实根x1, x2,    , xk, 则(R) 的通 解是：H(n) = c1x1n + c2 x2n +    + ck xkn 其中： c1， c2 、  、ck 是常数，它由H(n)的初始条件确定（下同）。 2）若(E)存在e重根xp（e  2 ），即:(E)的根是： x1, x2,    x k-e, xp, xp,   , xp 共有e个 则(R)的通解是： H(n) = c1x1n + c2 x2n +    + ck-e xk-en + c k-e+1xpn + c k-e+2 n xpn +    + ck ne-1 xpn

37 3）若(E)有一对共轭虚根 x 1,2 = ( cos  i sin ) ,则： (R)的通解： T(n) = c1n cos n + c2 nsin n 例 求Fibonacci序列的Fn F(n - 1) + F(n - 2) (n > 1) F(n) = ( n = 1) ( n = 0)

38 解：(R): F(n) = F(n -1) + F(n - 2)
(E): x2 - x = 0 (E)的根： x1 = 1/2 + 52 , x2 = 1/2 - 52 因为 x1  x2 所以 F(n) = c1(1/2 + 52)n +c2 (1/2 - 52)n 由 F(0) = 0 和F(1) = 1 知： C1 = 1/ 5 C2 = - 1/ 5 c1 + c2 = 0 c1( 1/2 + 52 ) + c2(1/2 - 52 ) = 1 F(n) = 1/ 5 [ (1/2 + 52)n - (1/2 - 52)n ]

39 (1/2 - 3/3)( 1 - 3)n 2 T( n - 1) + 2 T( n - 2 ) ( n > 2 )
(R): T( n ) = 2 T( n - 1) T( n - 2 ) (E): x2 - 2x - 2 = 0 x1 = 1 + 3, x2 = 1 - 3 因为：x1  x2 T(n) = c1(1 + 3)n + c2( 1 - 3)n 由：T(1) = 3 和 T(2) = 8 得： c1 = 1/2 + 3/3, c2 = 1/2 - 3/3, 故：T(n) = (1/2 + 3/3)(1 + 3)n + (1/2 - 3/3)( 1 - 3)n

40 对（3）递推：Sn-1 - Sn-2 = (n - 1)2 (4)
 K2 k = 0 n 解：由： Sn =  + n (1) 递推：S n-1 =  +(n - 1) (2) 由（1）- （2） 得：Sn - S n-1 = n (3) 对（3）递推：Sn Sn-2 = (n - 1) (4) 由(3) - (4) 得：Sn - 2S n-1 + S n-2 = 2n - 1 反复使用上面的方法，消去等号右边多项式，得： S n - 4Sn-1 + 6Sn-2 - 4Sn-3 + Sn-4 = (R) (E): x4-4x3+6x2-4x+1= (x - 1) 4 = 0 x1 = x2 = x3 = x4 = 1 5

41 因为特征方程的解是四重根，所以： Sn = c11n +c2 n 1n + c3 n2 1n + c4 n3 1n = c1 + c2n + c3n2 + c4n3 由： S0 = 0, S1 = 1, S2 = 5, S3 = 14, 知： c1 = 0 , c2 = 1/6, c3 = 1/2, c4 = 1/3 所以：Sn = 1/6 n ( n + 1 ) (2 n + 1 )

42 2 非齐次常系数线性递推方程的特征方程解法 （1）定义：(R’)为k阶非齐次常系数线性递推方程: (R’): H(n) = a1H(n - 1)+a2H(n - 2)+   +akH(n - k)+f(n) 其中： 1）a1, a2,    , ak为常数； 2）ak  0, n  k, f(n)  0。 （2）（R’）的解结构： 设：（R’）的通解是H(n)，且它有一个特解H*(n)； 而与（R’)相对应的 齐次方程(R)的通解是H’(n)。 则有（R’）的解：H(n) = H’(n) + H*(n)

43 (3) (R’)的特解形式讨论 1）当f(n) 形如bnt( b0, t:非负整数）时，(R’)的特解为： H*(n) = p1nt + p2nt-1+  + pt n + pt+1 其中：p1, p2, ， pt+1是待定系数。 但，当x = 1是(R)的 j 重特征根（j  1）时，其特解应 改设为： H*(n) = p1nt+j + p2nt-1+j+  + pt+1nj 2）当f(n) 形如 b  rn( b0, r 0 ）时，(R’)的特解为： H*(n) = p rn 其中：p是待定系数。 但，当 x = r 是(R’) 对应的(R)的 j 重特征根( j  1)时， (R’)的特解应改设为： H*(n) = p  nj  rn

44 2T( n - 1 ) + k (n > 1) (k:正数）
解：(R’) : T(n) = 2T(n - 1) + k (R) : T(n) = 2T(n - 1) (E): x - 2 = x = 2 (R)的通解： T(n) = c 2n 因为(R’)中，f(n) = k 所以， 设： T*(n) = p 显然， T*(n - 1) = p

45 把T*(n)、T*(n - 1)代入(R’) , 有：p = 2p + k p = - k 故：T*(n) = - k (R’)的通解：T(n) = T’(n) + T*(n) = c 2n - k 由T(1) = k, 把它代入上式， 有：2 c - k = k c = k (R’)的通解：T(n) = k( 2n - 1) = O( 2n )

46 2n T( n -2 ) ( n > 4 ) 例 T(n) = ( n = 3 ) ( n = 4 ) 解：(R’): T(n) = - T(n - 2 ) + 2n-3 (R): T(n) = - T(n - 2 ) (E): x = 0 (R) 的通解：T’(n) = c1cos(n/2) + c2sin(n/2) （ 其中： = 1，  = /2）

47 设：(R’) 的特解是：T*(n) = p 2n 把它代入(R’),有：p 2n = - p 2 n n-3 得：p = 1/10  T(n) = c1cos(n/2) + c2sin(n/2) + 2n/10 由：T(3) = 1 和 T(4) = 2, 知：c1 = 2/5, c2 = -1/5 故： T(n) = 2/5cos(n/2) - 1/5sin(n/2) + 2n/10 （ n > 2 ）

48 例 再求：Sn =  K2 k = 0 n 解：由： Sn =  + n (1) 递推：S n-1 =  +(n - 1) (2) 由（1）- （2） 得：Sn - S n-1 = n (R’) (R): Sn - S n-1 = 0 (E): x - 1 = x = 1 (R)的通解：S’n = c 设：(R’)的特解是：S*n = p1n3 + p2n2 + p3n 代入(R’), 得：p1 = 1/3, p2 = 1/2, p3 = 1/6 (R’)的通解：Sn = p1n3 + p2n2 + p3n + c 由S0 = 0,知：c = 故： Sn = p1n3 + p2n2 + p3n

49 原则：“变换”。 变系数/非线性递推方程的求解 一、变“非线性”为“线性” 例 求H(n)。已知：
H2(n) - 2H2(n - 1) = ( H(n) > 0 , n > 0 ) 解：令：G(n) = H2(n),则有： G(n) - 2G(n - 1) = ( G(n) > 0, n > 0 ) G(0) = 4 解上述递推式，得：G(n) =5 2n - 1 H(n) = 52n - 1

50 二、变“变系数”为“常系数” b (n = 1; b:非负常数） (n - 1) +  1/n T(k - 1) +  1/nT(n-k) (n > 1) k=1 n T(n) =

51 整理、改写上述递推式： T(n) = (n - 1) + 2/n  T(k) n-1 k=1 nT(n) = n(n - 1) + 2  T(k) n-1 k=1 (1) (n-1)T(n-1) = (n-1)(n - 2) + 2  T(k) n-2 k=1 (2) 递推： 由(1) - (2) 得： nT(n) - (n - 1)T(n - 1) = 2(n - 1) + 2T(n - 1) 即： T(n) = T(n - 1) + n+1 1 n 2(n - 1) n(n + 1) (3) 令：Q(n) = T(n), 有：Q(n - 1) = T(n - 1) n+1 1 n

52 代入(3)式：Q(n) = Q(n - 1) + n(n + 1) 2(n - 1) 递推：Q(n - 1) = Q(n - 2) + (n - 1)n 2(n - 2) Q(n - 2) = Q(n - 3) + (n - 2)(n - 1) 2(n - 3)  Q(2) = Q(1) + 2  1 2  3 +) Q(n) - Q(1) =  n k=2 k(k + 1) 2(k - 1)  k=2 n = k+1 4 - k 2 = n+1 4 - 1 + 2  k=3 n k

53 因为：  k=3 n k 1   3 x dx = ln n - ln 3 由：Q(n) = T(n), 及：T(1) = b, 知：Q(1) = 1/2b n+1 1 T(n) = (n + 1) Q(n)  2(n + 1) ln n + (b/ ln 3)(n +1) + 4 = O(n ln n)

54 递归程序的阅读法 用图形方式描述执行轨迹 按次序写出程序在当前调用层上实际执行的语句，并用有向弧表明语句执行次序
对程序中的每个调用语句写出实际调用形式，在其下（右）边写出本次调用的子程序实际执行的语句，用有向弧指示。 被调用子程序执行完有向弧指向其上级（标上形参的值） 变参：再返回路线上增加语句实参=变参 函数： 实参=函数值 最后，顺着有向弧的路径写出结果。

55 例 proc f(w) if w>0 then { f(w-1) print w f(w-1) } end f

56 习题答案  1. 用递推法求解 T(n/2) + b n log2 n (n > 1) T(n) =
b (n = 1) (b:正数) T(n/2) + b n log2 n (n > 1) T(n) = 1. 用递推法求解 答：T(n) = 2b • nlog2n - 2b • n + 3b = O(nlog2n) 2. 求解：T(n)= aT(n/c) + bn (n > 1) b (n = 1) (a, c:正整数；b:正数） 答：当 n = cr(r：非负整数)时，有 T(n) = (bn) ki (k = a/c) i=0 logc n 

57 (1) 当 a<c 时, 因为 ki 收敛于一个常数， T(n) = O(n)
(2) 当 a=c 时， T(n) = bn(r+1) = bn (logcn + 1) = O(n log n) (3) 当 a>c 时, T(n) = bn • (kr+1 - 1) / (k-1) = bk / (k - 1) • ar - bn / (k - 1) = bk/(k - 1) • alogcn - bn/(k - 1) = O ( nlogca ) 用特征方程法求解T(n)。已知： 2 T(n - 1) + n (n > 1) (n = 1) （1）T(n) = 答：T(n) = 2n+1 - ( n + 2 )

58 7T(n – 1) - 12T(n – 2) + 3n (n > 1) 0 (n = 0)
4. 试证：当特征方程(E)包含有二重根 x 1,2 = xp 时，齐次方程(R)通解包含有：T(n)= c1xpn + c2 n xpn 证：设：齐次常系数线性递推方程如下： H(n) = a1H(n-1) + a2H(n-2) + •••••• +akH(n-k) (R) 它所对应的特征方程是： xk - a1xk-1 - a2xk-2 - •••••• - ak-1x - ak = (E) 实际上，我们只要证明x = nxp是(R)的解，即可。 n

59 对(E)两边同乘xn-k (x0)，有： xn - a1xn-1 -a2xn-2 - •••••• - a k-1xn-k+1 - ak xn-k = 0 (M)
对式(M)左边求导，得到： nxn-1 - a1(n-1)xn-2 - a2(n-2)xn-3 - •••••• - ak-1(n-k+1)xn-k - ak(n-k)xn-k (M’) 现证(M’) 等于零： 因为(E)有二重根x1 = x2 = xp， 所以(M)式可改写成 (x - xp)2 • f(x) = (M) 可见， (M’) 式实际上就是： 2(x - xp) • f(x) + (x - xp) 2 • f ’(x) =(x - xp)[2f(x) + (x - xp) • f ’(x)] (N’) 显然，当x = xp仍有(N’)等于零。

60 也就是说，把x = xp代入(M’) ，应当有下式成立：
nxpn-1 - a1(n-1)xpn-2 - a2(n-2)xpn-3 - •••••• - ak-1(n-k+1)xpn-k - ak(n-k)xpn-k-1 = 0 (M’) 等于零，证毕。 上式两端同乘以xp（xp  0），有： nxpn - a1(n-1)xpn-1 - a2(n-2)xpn • • • • • • - ak-1(n-k+1)xpn-k+1- ak(n-k)xpn-k = 0 此式说明， x = nxp是(R)的一个解。 易证， x = xp是(R)的另一个解。 综上，特征方程(E)包含有二重根 x 1,2 = xp 时，齐次方程(R)通解包含有：T(n) = c1xpn + c2 n xpn，证毕。