组合数学讲义 3章 递推关系(2)

（证） an＝qn是（3.2.1）的解 qn c1qn 1 ckqn k 0

组合数学讲义

qk c1qk 1 ck 0 q是方程C(x)＝0

的根，即q是（3.2.1）的特征根。

从而给出了一个实用且比较简单的解此类递推关系的方法。 （三） 通解

【定义3.2.2】 若an，an， ，an是（3.2.1）的不同解，且（3.2.1）的任何解都可以表为

1

2

s

1 2 s r1an r2an rsan an，则称an为（3.2.1）

的通解。其中r1,r2, ,rs为任意常数。

此处所说的不同解是指将每一个解an都视为一个无穷维的解向量，而这些向量之间是线性无关的。

i

通解的特征：

① 通解an首先是解；

② 组成通解的所有解向量线性无关；

③ 任何一个具体的解都被包容在通解an中。

§3.2.3 特征根法

思路：通过解式（3.2.1）的特征方程，求得其特征根，再利用特征根构造（3.2.1）的通解。 （一） 特征根为单根情形

设q1,q2, ,qk是（3.2.1）的互不相同的特征根，则（3.2.1）的通解为

nnn

an A1q1 A2q2 Akqk （3.2.3）

其中A1,A2, ,Ak为任意常数（待定）。

（证）首先由定理3.2.1知qi是方程（3.2.1）的解。且由

n

组合数学讲义

性质1知an也是（3.2.1）的解。

再证（3.2.1）的所有解都可以表为（3.2.3）的形式。设bn是（3.2.1）的一个解，且满足初始条件bi＝di，i＝0,1,2, ,k－1。令bn 组

000

A1q1 A2q2 Akqk b0

A1q1 A2q2 Akqk b1

Aqk 1 Aqk 1 Aqk 1 b 1122kkk 1

n

Aq ii，代入初始条件，可得关于Ai的线性方程i 1k

（3.2.4）

其系数行列式为著名的范德蒙（Vandermonde）行列式：

1q1

2

D q1

k 1q1

1q2

2q2

1qk

2qk qj qi 0

1 i j k

k 1k 1q2 qk

n

所以式（3.2.4）有唯一解。即b一定可以表示为(3.2.3)的形式。

由于bn的任意性，故知结论成立。

例3.2.1 求递推关系an 4an 1 an 2 6an 3的通解。 （解）特征方程为x3 4x2 x 6 0，解之得特征根

q1＝－1， q2＝2，q3＝3

n

∴ 通解为 an A 1 B2n C3n

其中，A、B、C为任意常数。

组合数学讲义

若是定解问题，设初值为：a0 5，a1 13，a2 35，带入通解得

A B C 5

A 2B 3C 13 A 4B 9C 35

解得A＝0，B＝2，C＝3，故

an 2 2n 3 3n 2n 1 3n 1

若初值为a0 4，a1＝－1，a2＝7，则

an 3 1 2n

n

求A、B、C的方程组为

A B C 4

A 2B 3C 1 A 4B 9C 7

（二） 重根情形 设特征方程有重根

例3.2.2 求递推关系an 4an 1 4an 2 0的通解。 （解）特征方程x 4x 4 0 特征根q1 q2 2，为二重根 若按单根处理，通解an＝A12 A22

n

n

2

＝

A1 A2 2n＝

A2n，即一个待定常数。要满足两个初始条件

a0 d0,a1 d1，一般是不可能的。

组合数学讲义

实质：两个解向量an 2和an 2是线性相关的。

1 2 aa任务：找两个线性无关的解向量n和n。 令an n2，可以验证an是（3.2.1）的解，且与an 2线性无关。

2

n

1

n

2

n

2 1

n

an 4an 1 4an 2＝n2n－4(n－1)2n 1＋4(n－2)2n 2＝0

10＝2 22

仿单根情形，可证明通解为

an A12n A2n2n

一般情况下，设q是（3.2.1）的k重根，则（3.2.1）的通解为

an A1 A2n Aknk 1qn (3.2.5)

更一般的情形，若式（3.2.1）有t个根，其中qi为ki重根

i 1,2, ,t,

t

ki

i 1j 1

ki k ，那么，通解应为 i 1

t

an Aijnj 1qin

n

A11 A12n A1k1nk1 1q1n A21 A22n A2k2nk2 1q2

At1 At2n Atktnkt 1qtn (3.2.6) 例3.2.3 求an 7an 1 19an 2 25an 3 16an 4 4an 5＝0的通解。

（解）特征方程 x5 7x4 19x3 25x2 16x 4＝0

组合数学讲义

特征根 x＝1（三重），x＝2（二重）

通解 an＝(A11＋A12n＋A13n2)1n＋( A21＋A22n)2n

＝(A11＋A12n＋A13n2)＋( A21＋A22n)2n

（三） 复根情形

q e i ，q ei ，设特征方程有一对共轭（单）复根：则通解中含

Aq B＝A nein B ne in

n

n

＝A cos n isin n

n

＋B cos n isin n

n

＝ A B cos n ＋i A B sin n

n

n

＝A1 故通解为

n

cos n ＋A2 nsin n

an＝A1 ncos n A2 nsin n (3.2.7)

优点：避免了复数运算。尤其是当数列{an}是实数时，

Aq Bq的虚部为零。

一般情形，若q是m重复根，且q也是m重复根，从而通解中必含有下面的项

n

n

n A1 A2n Amnm 1 cos n ＋ B1 B2n Bmnm 1 sin n

小结：表3.2.1

组合数学讲义

2 4 8

解得 q＝＝1±i

2

（方法一）按复根形式：

通解 an＝

A 0

代入初始条件 22

2 A2 B2 1

解之得 A＝0，B＝1，故定解为

0,当n 4m

nn m

＝ 1 22m,当n 4m 1， an 2sin4 m2m 1

12,当n 4m 2,4m 3

m＝0,1,

该数列为

an 2an 1 2an 2 0

例3.2.4 求定解 。

a0 0,a1 1

（解）特征方程 q2－2q＋2＝0

2，

4

n n

2 Acos Bsin

44

n

组合数学讲义

0，1，2，2，0，－4，－8，－8，0，16，－32，－32，

（方法二）按单根形式：通解 an＝A 1 i B 1 i

n

n

i

A A B 0 2 代入初值 ， 即

1 i A 1 i B 1 B i

2

iinn

定解为 an＝ 1 i ＋ 1 i

22

化复数表示形式为实数形式 an

＝

i

2

n n i

2 cos isin

44 2

n

n

n n

2 cos isin

44

n

＝ i

n

2isin＝

4

n

n 2sin

4

例3.2.5 求定解

an 4 i an 1 5 4i an 2 4 5i an 3 4 4i an 4 4ian 5 0

a0 5,a1 6,a2 10,a3 24,a4 50

（解）特征方程为

q5 4 i q4 5 4i q3 4 5i q2 4 4i q 4i

＝0 特征根 q＝2，2，i，i，－i

组合数学讲义

通解 an＝ A Bn 2n C Dn in E i

n

A C E 5

2 A B C D i E( i) 6

代入初始条件 4 A 2B C 2D E 10

8 A 3B C 3D i Ei 24 16 A 4B C 4D E 50

解得 A＝3，B＝0，C＝1，D＝0，E＝1，故定解为

an＝3 2n in i n …… 此处隐藏：1956字，全部文档内容请下载后查看。喜欢就下载吧 ……