n

n1

n1

由于这两种方法是 等价的，故可得
|T|

k
2


2

。证毕。
k1

2

3

1.24题 A={(a, b)|a, b∈Z, 0≤a≤9,0≤b≤5} (a) 求x-y平面上以A作顶点的长方形的数目.
(b)
求
x-y
平面上以
A
作顶点的正方形数目
.

解(a)：如图(a)，从图中可以看出，对于x-y平面上满足题意的任一顶点A(a,b),除它本 身以外，横坐标取值有9种
可能，纵坐标取值有5种可能。顶点A(a,b)与和它不在同一水平线或垂 直线上的任一点(x,y)均可构成一个长方形。故满
足要求的长方形的数目为9×5=45个。
解(b)：如下图(b)，网格左边是b的取值，下面是a的取值。网格里是x- y平面上对应每个顶点A(a,b)所得的正方
形的数目。

1.26题 S={1,2,……，1000}，a,b∈S,使ab≡0 mod 5,求数偶{a,b}的数目
解：根据题意，ab可以整除5，2*C（200，1）*1000=400000
1.25题 平面上有15个点P
1
,P
2
。。。Ｐ
15
，其中P
1
P
2
P
3
P
4
P5
共线，此外不存在3点共线的。
(1)求至少过15个点中两点的直线的数目 (2)求由15个点中3点组成的三角形的数目
解：1)由题意知：P
1
P
2
P
3
P
4
P
5
共线，此外不存在3点共线的，所 以与这五点分别相连的其他的十点的直线数目为：
5*10=50。另外十个点两两相连得直线数目为： C
10
2
=45
又因为P
1
P
2
P3
P
4
P
5
共线，所以可算作一条至少2点相连的直线
所以至少过15个点中两点的直线的数目=50+45+1=96
2)有三种情况 a：没 有P
1
P
2
P
3
P
4
P
5
这五个点的三角个数：C
10
3
=120
b：有这五个点的其中一个点：5*C
10
2
225 c：有着五个点的两个点：10*C
5
2
=100
由15个点中3点组成的三角形的数目=425
故数目为C(15,2)-C(5,2)+1
(b) C(5,0)C(10,3)+C(5,1)C(10,2)+C(5,2)C(10,1)
1.27 题 6位男宾，5位女宾围一圆桌而坐，（1）女宾不相邻有多少种方案？（2）所有女宾 在一起有多少种方案？（3）
一女宾A和两位男宾相邻又有多少种方案？
解 ：（1）若5位女宾不相邻，先考虑6位男宾围圆桌而做的方案数，然后女宾插入 Q（6，6）*6*5*4*3*2=86400
（2）把5位女宾看成一个整体，然后插入 Q（6，6）*6*P(5,5)=86400
（3）C（5，1）*C（6，2）*Q（8，8）=194000
C(5,1)*C(6,2)*C(5,2)*P(4,2)*7！
1.28题 k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数。
解：若每个圆桌的的人数相等，则 每个桌子有n个人。因为圆周排列的个数为
因此本题的结果为
p
r
n
r

(kn)!(kn)!

k
。
nnnn
1.29 题 从n个对象中取个r做圆排列，求其方案数目。1<=r<=n
解：c(n,r)*Q（r,r） =c(n,r)*(r-1)!
1.31题 试证任意r个相邻数的连乘：
(n1)(n2)(nr)
被r！除尽.
证明：由 P（n ,r）=n*(n-1)…（n-r+1） 可知：（n+1）（n+2）…（n+r）= p（n+r,r）=c（n+r,r）* r!
所以 [（n+1）（n+2）…（n+r）]r!= p（n+r,r） r! = c（n+r,r）
故任意个相邻数连乘可被r！除尽。

5

1．30题 （1）





= nr


n


r


n1< br>

n

n



， 1rn；（2）=（n-r+1）r, 1

r

n；(3)




r1


r

r1


n1


n


 
=n(n-r)

r


, 0

r

n；

r




n 1


n

解：（1）：


r1

=nr*((n-1)!((r-1)!(n-r)!))= n!(r!(n-r)!)=上式 所以两式相等

r



n!(r!(n-r)!) nr



（2）：





n!(r!(n-r)!) (n-r+1)r



n


r


n


=（n-r+1）r*( (n!)((r-1)!(n-r+1)!))= n!(r!(n-r)!)=上式 所以两式相等


r1


n1


n

（3）：


r


=（n-1）!(r!(n -r-1)!))= n!(r!(n-r)!)=上式 所以两式相等

r



n!(r!(n-r)!) n（n-r）



1.32题 在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y必须夹在两个x之间，问这样的排列数等于多少？
解：满足y必须加在两个x之间应为 x y x y x 然后再把a ，b ，c ，d ，e ，f插入，a插入时有6种选择，
b插入时有7种选择，c插入时有8种选择，d插入时有9种选择， e插入时有10种选择，f插入时有11种选择，
由此可得排列数 N=11*10*9*8*7*6=11!5!
1.33题 已知r，n，k都是正整数，
rnk
，将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有
多少种方案？
解：首先从r个球中取出nk个球放入n个盒中，因为球是无区别的。因此只有一种排列方案。剩下的球 ，每个球
(r-nk)
放的时候都有n中可能。因此方案数为
n
.
1.34 题 在r,s,t,u,v,w,x,y,z的排列中求y居于x和z中间的排列数
解 ： 2*（5+4+3+2+1）*6！=2430
1.35题 凸十边形的任意三条对角线不共点。试求这凸十边形的对角线相交于多少个点？
解：根据题意，1个顶点有7条对角线，与它相邻的顶点有7条对角线，这样的点2个；
与它不相邻的顶点有6条对角线（有1条与它重复的），这样的点8个；
因此 （2* C（7，1）* C（7，1）+8* C（6，1）* C（7，1））*（9+1） =4340
1.36题 试证一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数
证明：设N=P
1
a1
P
2
a2
。。。P
n
an
，P
1
，P
2
，。。。P
n
是n 个不同的素数，每个能整除尽数n的正整数都可以选取每个素数
P
i
从0到a
i
次，即每个素数都有a
i
+1种选择，所以能整除n的正整数的数目为(a
1
+1)(a
2
+1)。。。(a
i
+1)个。而设M=N
2
=P
1
2a1

P
2
2a2
。。。P< br>n
2an
，能被(2a
1
+1)(2a
2
+1)。。 。2(a
i
+1)个整除。所以一整数是另外一整数的平方的必要条件是除尽他的数的
数目是整数。
1.37题 .给出



n

r

n1

r1

n2

r2

nm

rm


nr1< br>


++
+…+
=

的组合意义。



m

0

m1

1

m2
 
2

0

m


m
解： Y
B（m,n+r+1-m）

P’

P(k,r)

0 k m X
rk

如上图所示，

表示（0，0）点到P点的路径数； 

k


P点到P’点只有一步；


nmmk


nk


nr1

表示（0，0）点到B点的路径数。




mk

=

mk

表示P’点到B点的路径数;< br>

m





所以0点到 B点的路径由0点到P点再从P点到P’点，最后从P’点到达B点。

0
M

rk

nk

M


k
*1*


mk


=


0

n

r

n1

r1

n2

r2

nm

rm


nr1

 

++
+…+

m

0

m1

1

m2

2

0< br>


m


=


m< br>



6

1.41 题 分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法。
解：利用“字典序法”生成下一排列的算法 ，计算该排列的对应序号，生成已知排列序号算法：
设 int M为每一排列的对应序号初始时：P
1
_
P
2
_
...P
i-1
_
P
i
_
P
i+1< br>_
...P
n
_
(其中P
1
_
2
_
.i-1
_
i
_
i+1
_
n
_
)M =1（初始化）
I. 满足关系式P
j-1
j
的j的 最大值，设为i , 即i=max{ j | P
j-1
j
}
II.
满足关系式P
i-1
k
的k的 最大值，设为j, 即j=max{ j | P
i-1
k
}

III.
使P
i-1
与 P
j
互换得(p
_
)

= P
1
_
P
2
_
...P
i-1
_
P
i
_
P
i+1
_
...P
n
_
IV. (p
_
)

= P
1
_
P
2
_< br>...P
i-1
_
P
i
_
P
i+1
_
...P
n
_
中的P
i
_
P
i+1< br>_
...P
n
_
部分的顺序逆转，得下一排列。
V. 判断(p
_
)排列是否与给定排列相同 ，相同则输出M， ELSE M=M+1 GOTO Ι
（2）给定序列号计算排列算法：
设 Int M为每一排列的对应序号，M=N （N为给定序号）
设 Int K为循环次数
FOR （K=1；K++；K <=N ）
{
满足关系式P
j-1
j
的j的 最大值，设为i , 即i=max{ j | P
j-1
j
}
满足关系式P
i-1
k
的k的 最大值，设为j, 即j=max{ j | P
i-1
k
}

使P
i-1
与 P
j
互换得(p
_
)

= P
1
_
P
2
_
...P
i-1
_
P
i
_
P
i+1
_
...P
n
_
(p
_
)

= P
1
_
P
2
_
...P
i-1
_
P
i
_
P
i+1
_
...P
n
_
中的P
i
_
P< br>i+1
_
...P
n
_
部分的顺序逆转，得下一排列
}
输出(p
_
)排列。

r

r1

r2

n

n1

1.38题 给出



的组合意义。
< br>



r

r

r

r





r1



解：设A={
a
1
,
a
2< br>,….,
a
nr1
,……,
a
n1
},从A中取r+1个元素组合成C，考虑以下n-r+1种情况：
(1)
a
1< br>∈C，则A需要从A{
a
1
}中取r个配合，构成C，共




种可能

n


r
(2)
a
1
c
，
a
2
c,
则需要 从
A{a
1
,a
2
}
中取r-1个，加上
a2
构成C，共


n1


r
< br>
中可能 ……

(n-r)
a
1
,a
2
,...,a
nr1
C，a
nr
C，
则需从 A{
a
1
,a
2
,...,a
nr
}中取r个组 合，再加上
a
nr
构成C，共

r

(nr 1)a
1
,a
2
,...,a
nr
C,
这时只 有


=1种可能。

r



r1


r


种可能。

故


r


+…+


r


+
< br>
r1




r


+


r


+


r


=





（法二）C(n+1,r+1)是指从n+1个元素a
1
, a
2
,…,a
n+1
中任取r+1个进行组合的方案数。
左边：若 一定要选a
n+1
,则方案数为C(n,r).若不选a
n+1
,一定要选a
n
, 则方案数为C(n-1,r).
若不选a
n+1
,a
n
,…a
r+2
, 则方案数为C(r,r). 所有这些可能性相加就得到了总方案数。
1.39 题 证明(m,0 )C(m,n)+C(m,1)C(m-1,n-1)+…+C(m,n)C(m-n,0)=2
nC(m,n)
证明：由公式C(n,l)C(l,r)=C(n,r)C(n-r,l-r) 其中：l>=r 得： C(m,0)C(m,n)=C(m,n)C(n,0)
同理： C(m,1)C(m-1,n-1)=C(m,n)C(n,1) … C(m,n)C(m-n,0)=C(m,n)C(n,n)
由上知：左边=[C(n,0)+C(n,1)+ … +C(n,n)]C(m,n)
nn22 n
n1
n
由
(xy)
=C(n,0)
x
+C (n,1)
xy
+C(n,2)
xy
+…+C(n,n)
y

n
令x=y=1 可得 C(n,0) +C(n,1) +C(n,2) +…+C(n,n)=
2
左边=2
n
C(m,n)=右边 命题得证。
1.40题 从n个人中选r个围成一圆圈，问有多少种不同的方案？
解：圆排列:共有P(n,r)r种不同的方案。

1.48题 在由n个0及n个1构成的字符串中，在任意前k个字符中，0的个数不少于1的个数的字符串有多少？
解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线, 故方案数为
C(2n,n)-C(2n,n-1。

7

n
n1


n2

r1


r


n1


1.42题 (a) 按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法.
(b) 写出按照邻位对换法由给定排列生成其下一个排列的算法.
解：1：给定排列求相应序号：
设 Int I为每一排列的对应序号 I=1 （初始化）
假定A[1：n]和E[2 ：n]；D[2：n]；B[1：n]都是整数数组，其中B[1：n]为给定序列
S
1
： A[1]1
i从2到n作
始 A[i]i，D[i]i，E[i]1 终；
S
2
： q0；
判断A[1：n]是否与B[1：n]相等
若相等则输出I值
否则II1；
S
3
： k从n降到2作
始 D[k]D[k]E[k]; pD[k];
若 pk 则作E[k]-1;
否则作
始 若p0 则作
始 E[k]1, qq1 终
否则作
始 ppq; rA[p]; A[p]A[p1];
A[p1]r; 转S
2
终

终
终
2：给定序号求相应排列：
设 Int I为每一排列的对应序号 I=1 （初始化） M为给定序列号
假定A[1：n]和E[2：n]；D[2：n]；都是整数数组
S
1
： A[1]1
i从2到n作
始 A[i]i，D[i]i，E[i]1 终；
S
2
： q0；
判断 I 是否与 M 相等
若相等则 i从1到n输出A[i]；
否则II1；
S
3
： k从n降到2作
始 D[k]D[k]E[k]; pD[k];
若 pk 则作E[k]-1;
否则作
始 若p0 则作
始 E[k]1, qq1 终
否则作
始 ppq; rA[p]; A[p]A[p1];
A[p1]r; 转S
2
终

终
终
(a) 由给定排列生成其下一个排列的算法
从排列 pp
1
p
2

p
n
生成下一个排列

S
1
： 若在 pp
1
p
2

p
n
中无一处于活动状态则停止。
S

2
： 求处于活动状态各数中的数值最大者，
设为m， m 和它箭头所指一侧相数邻互换位置。
S
3
： 比 m 大的数一律改变箭指头向的 转；S
1
。

8
M=N


N1
或
N1
若N是奇数
22
1.4 3题 对于给定的正整数N，证明，当
K

时，C(N,K)是最大值。 
N
若N是偶数


2
证明：要证明C（N，K）是最 大值，只需证明C（N，K）大于C（N，K-1）即可
根据以往证明大小值的经验，可以用相减或是 相除的方法来证明，就此题，相减不合适，采用相除可以消除等式
中的一些项
C（N，K） C（N，K-1）=（N！K！（N-K）！）*（（K-1）！（N-K+1）！N！） =（N-K+1）K
当n为偶数，k=n2时 （N-K+1）K=（（n+2）n）*（2n）=（n+2）n >1
当n为奇数,k=(n-1)2时 （N-K+1）K=((n+3)2) * (2(n-1))=1+4(n-1) >1
当n为奇数, k=(n+1)2时 （N-K+1）K=((n+1)2) * (2(n+1)) =1
综上所述,当n取以上三种情况, C（N，K）取最大值
3
n
1
1.46题 证明在由字母表{0,1,2}生成的长度为n的字符串中. (a) 0出现偶数次的字符串有个；
2
n

n

n

n

(b )

2
n


2
n1
...

2
nq

31
，其中
q2
< br>n

.

2

2

0

2

q

证：(a)归纳法：当n=1时,0出现偶数次的字 符串有(3
1
+1)2=2个(即1,2),成立。
假设当n=k时,0出现偶数次 的字符串有(3
k
+1)2种。总的字符串有3种。0出现奇数次的字符串有(3
k< br>-1)2种。
当n=k+1时，0出现偶数次的字符串包括两部分：
n=k时,0出 现偶数次再增加一位不是0的，共有2(3
k
+1)2种，0出现奇数次再增加一位0,共有( 3
k
-1)2种。
所以共有2(3
k
+1)2+(3
k< br>-1)2=(3
k+1
+1)2种，证毕。
(b) 等式左边第m项是0出现m次的字符串数，总和就是0出现偶数次的字符串数，
右边由(a)得是0出现偶数次的字符串数，两边显然相等。
()!
(2n)!
(3n)!
1.44题 （a）用组合方法证明
n
和
nn
都是整数。 （b）证明
n
n1
是整数。
223
(n!)
(2n) !2
n
n!(2n1)!!
n!(2n1)!!
解：(a) ①方法一：因为：
(2n)!2n!(2n1)!!
所以
n

22
n
n
2
n!(2n1)!!
是整数，因此
(2n)!
是整数。
n
2
方法二：设有2n个不同球放入n个不同的盒子里 ，每盒两个，这个方案数应该是整数。
对2n个球进行排列得到方案数为(2n)!。
而把2个球放入同一个盒子里不计顺序，
应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2 次。
得到2n个不同球放入n个不同的盒子里，每盒两个的方案数
(2n)!

n
2
②若有3n个不同的球,放入n个不同盒子,每个盒子放三个，这个方案应该是整数。
对这3n个球进行排列得到方案数为(3n)!。
而把3个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，
n个盒子内部的排列共重复计算了3！次。
得到3n个不同的球放入n个不同的盒子里，每盒 三个的方案数
2
(3n)!(3n)!


(3!)
n
3
n
2
n
(b) 有
n
个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。 < br>按前面(a)的方法，应该得到(n
2
)!(n!)
n
是整数。另外由 于n个盒子相同，放入不同的盒子是没有区别的，
应该把n个盒子的排列数n!除去。
因此得到(n
2
)!(n!)
n+1
是整数。
1.49 题 在1到n的自然数中选取不同且互不相邻的k个数,有多少种选取方案？
解: 设从1-n中 选取互不相邻的k个数的方案为g(n,k)。若选n，则方案为g(n-2,k-1),若不选n,则方案数位 g(n-1,k).
显然g(n,k)=g(n-2,k-1)+g(n-1,k)，且只有当n≥2 k-1时,g(n,k)>0,否则g(n,k)=0,可给定初始值g(2k-1,k)=1,g(2k-2, k)=0.


9

1.45题 (a) 在2n个球中，有n个相同. 求从这2n个球中选取n个的方案数.
(b)
在
3n+1
个球中，有
n
个相同
.
求从这
3n+1
个球中选取
n
个的方案数
.
解(a）：有n个相同就有n个不相同
取n个不相同和0个相同的为C(n,n), 取n-1个不相同的球和1个相同的球为C(n,n-1)，等等。
n
所以总的方案数为
C

n,0

C

n,1

 C

n,n

2

解(b）：方法同上，方案数为< br>C

2n1,0

C

2n1,1

C

2n1,n


由于C(2n+1,0)=C(2n+1,2n+1),… ,C(2n+1,n)=C(2n+1,n+1)
C2n1,0C2n1,1C2n1,2n12
2n1


则
C

2n1,0

C
2n1,1

C

2n1,n


1
2
2n1
2
2n

2
1.47题 5台教学机器m个学生使用，使用第一台和第二台的人数相等，有多少种分配方案？
解：当使用第1台 机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，
剩余 的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3
(m-2n)
。
所以总的方案数为

C(m,2n)C(2n,n)3
n0
q(m2n)

m

q



2

1.50题 (1)在有5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个？
(2)在有m个0，n个1组成的字符串中，出现01或10的总次数为k的字符串，有多少个？ 解：(1)、先将5个00000排成一排，1若插在两个0中间，即：“010”则出现2个“01”或“ 10”；
若插在两端，则出现1个“01”或“10”；要使出现“01”，“10”总次数为4，有两种办法：
1、把两个1插入0的空当内，剩下的1插入1的后面（类似010111000）。
2、把 1个1插入0的空当，再取两个1分别插入两端，剩下的1插入1的前面。（类似10100011）。
21
由1和2得：
3*C
4
3*C
4
30

(2)、m个0产生m-1个空当。
若k为偶数时：要得到出现“01”与“10”总次数为 k，可以先按上题中1的情况讨论，则在m-1个空当中分别插入
k
个1即可，也就是
C
k
2
m1
。剩下的
2
1如何插入的问题与书P20页的 定理1.2类似(在n个不同元素中取r个允许重复的组
合，其组合数为（C（n+r-1,r)），在 这里无区别的球的个数也就是剩下的1的个数（即n-
k
），盒子的个数也就是插入
2
到m-1个空当中的1的个数(即
k
)，则得出剩下的1的插入方法有
C2
k
2
n1
n
。即第一种情况的总的插入方法为：
C
k2
2
m1
k2
2
2
。
n 1
n
k
2
m1
*C
k
2
n1
n
。
同理可得，按2的情况讨论后的第二种情况的总的插入方法为：
C
1和2得总的插入方法为：
C
k
2
m1
*C
*C
k
2
n1
n
C
k2
2
m1
*C
k2
2
2
n1
n
。
若k为奇数时：则必 有且只有一个1插入字符串的头或尾,剩下的1按照1的方法插入,只有这样才能使k为奇数。
所以插 入的总方法为：
2*C
k1
2
m1
*C
k1
2
。
n1
n
1.51 题 从N={1,2,…,20}中选出3个数，使得没有两个数相邻，问有多少种方案？
解：相当于从N ={1,2,…,20}个数中取3个作不相邻的组合，故方案数为C(20-3+1,3)=C(18,3)种
1.52题 从s={1,2,n}中连取k个数，使之没有两个数相邻，求不同方案数。
解：在n个数中选k个数，使之没有两个数相邻，相当于在n-k+1位置中插入k个数，k个数中没有俩个数相 邻。
有
C
nk1

k
(nk1)!
种方 案。有定理1.4直接可得。
k!
1.53题 把n个无区别的球放进有标志1，2，…，n的n个盒子中，每个盒子可放多于一个球，求有多少种方案？ 解：把n个无标志的球放进n个有标志的盒子中，每个盒子允许多于一个球是允许重复的组合所以是

nn1


2n1



n

=


n






10

1.54题 .m个1，n个0进行排列，求1不相邻的排列数.设n>m.
解：相当于n个0排列后,使m个1做 不相邻的插入，共产生n+1个位置.第一个1插入有n+1种情况，
第二个是n种情况…第m个1插入就有n-m+1种情况。
所以是（n+1）（n）（n-1）…（n-m+1），即此题解为p
n+1
m
。
1.55题 偶数位的对称数，即从左向右读法与从优向左的读法相同，如3223。试证这样的数可被11整除。
证明： 根据所有偶数位置上的数字及所有奇数位置上的数字分别相加，再求出两个和的差，
如果所得的差能被11整除，那么这个整数必能被11整除。
例如12344321，偶数位上是：2，4，3，1。奇数位上是：1，3，4，2
因为对 称数是偶数个，所以偶数为相加与奇数为相加的和是相等的，他们的差是零，而零能能被任何数整除，
所以原题成立。证毕。
1.56 题 n个男人与n个女人沿一圆桌坐下，问两个女人之间 坐1个男人的方案数。又m个女人n个男人，且m沿一圆桌坐下，求无两个女人并坐的方案数。
解：根据题意，两个女人之间坐1个男人的方案数Q (n,n)* P(n,n)
无两个女人并坐的方案数Q (n,n)* P (n,m)
1.57 题 n个人分别沿着两张圆坐下，一张r人，另一张个n-r人，试问有多少种不同的方案数？
解： C（n,r）*(r-1)!(n-r-1)!
1.58题 一圆周上n个点标以
1 ,2,,n
。每一点与其它n-1个点连以直线，试问这些直线交于圆内有多少点？
解：这些直线交于圆内有C（n,4）个点
每4个点形成矩形，其对角线有一个交点，故圆内交点有：
C(n,4)
n(n 1)(n2)(n3)1
n(n1)(n2)(n3)
432124

因为四个点连在一起构成一个四边形，这个四边形的对角线相交于一个点，
求这些直线交于圆内多少点就是求这些点能构成几个四边形，即转化为从n个点取出四个进行组合



2.1题 求序列{ 0，1，8，27，
n
3
32
}的母函数。
33
解：由序列可得到
G(x)x2x3x
因为
n
3
x
n


1
1xx
2
x
3
x
n


1x
1
()'12x3x
2
4x
3
nx
n1
< br>
1x
1
设
p(x)x()'x2x
2
3x
3
(n1)x
n1
nx
n
1x
'1x

[p(x)]
2

1
x2
2
2
x3
2

22
2n2
n(x1)nx< br>n2

设
q(x)x[p(x)]'x2x3x
3< br>(n1)
2
x
n1
n
2
x
n
1
'1x2

[q(x)]
33
x3
2

3n2
n(x1)nx
n3


x[q(x )]'x2
3
x
2
3
3
x
3
由以上 推理可知
x[q(x)]'
=
(n1)
3
x
n1n
3
x
n

,[7*9
n
4*(6)< br>n
],
所以可通过求得
x[q(x)]'
得到序列的母函数：
G(x)4xxx

32
1
H(x)

F(x)d x[3x
2
4x
3

6

(n3)x
n2
]

11

2.2题 已知序列


,

,
解：
G(x)


3

4



3
< br>3


n3

,,

，求母函数 

3

3*2*14*3*2(n3)*(n2)*(n1 )
n
x

3*2*13*2*13*2*1
1
n
=
[3.2.14.3.2x(n3)(n2)(n1)x]

6
1
2n1

F(x)

G(x)dx [3.2x4.3x(n3)(n2)x]

6
1
2

H(x)

F(x)d

x[
2
3x
3
4x(n
n
3)x]
6
1
I(x)

H(x)dx[x
3
X
4
x
n3
]< br>
6
1
因为
1xx
2

1x
2.3题 已知母函数
G(x)
x
n3

1x
3
11
2
]'''
就是所求序列母函数 所以
I(x)(1xx)
所以
G(x)[
61x
61 x
378x
，求序列{
a
n
}。
13x54x
2
378xAB74
解：
G(x)
=

13x54x
2
19x16x19x16x
17
2
由
1xx
2
x
n3

得
7(1x9(x9)
1x19x
4
4(1(6)x( 6x)
2
(6x)
n
)

16x
所以由 两式相加得：对应序列{
a
n
}={11，39，
x(
n
9 )

)
,[7*9
n
4*(6)
n
],
}
2.4题 已知母函数
G(x)
39x
，求序列{
a
n
}。
2
1x56x
39xAB12
解：
G(x)
= < br>
2
1x56x18x17x18x17x
则
an
=
82*(1)*7

nn
2.5题 设
G< br>n
F
2n
，其中
F
n
是Fibonacci数。证 明：
G
n
3G
n1
G
n2
0
， n=2.3.4…..求{
G
0
,G
1
,G
2
,< br>解：(1).已知
G
n
F
2n
则
G
n
3G
n1
G
n2
=
F
2n
3 F
2n2
F
2n4

}的母函数。
F
2n
F
2n1
F
2n2
F
2n1
F
2n

2
F
n2

F
2n2
F
2n

3
F
n2
则
F
2n
3F
2n2
F
2n4
则
G
n
3G
n1
G
n2
0
< br>(2)．
G(x)G
0
G
1
x

< br>(G
n2
n
n

n1
G
n2
)x
=
G
0
G
1
xx

G
n1
x
n
n2
2

n1
x
2

G
n2

n2
x
n2< br>
=
G
0
G
1
xx

(Gx
n0
G
0
)x

G
n2< br>
2
n2
GGxxG(x)xGxG(x)

x
=
010
n2
=
1xG(x)xG(x)x

G(x)


12
2
1x

2
1xx

2.6题 求序列{1，0，2，0，3，0，
解：序列
a
n
=
}的母函数。
2n

2n

(n1)x
n0

2n
1
1

1

2n
1x11
2n
=

nx

x
=

(2n1)x
< br>x
=
(
=
)'
22
22
22
( 1x)
21x21x
n0n0
n0n0

2.7题 设
G12x3x4x(n1)x
2462n

=1(1- x^2)^2 求
(1x
2
)G,(1x
2
)
2
G

2n
解：设
TG12x3x4xL(n1)x

2 46
L
1x

1
1x1x
1

x

1xx

G



22
(1x)(1x)

1x

1
(1x
2
)1
2222
242n< br>(1x)G(1x)1
所以 1）
(1x)G
2）
1xxx
22
222
(1x)
(1x)1x
2

2.8题 求下列序列的母函数：(1)1,0,1,0,1,0，… (2)0,-1,0,-1,0,-1,… (3)1,-1,1,-1,1,-1,…
解：(1)
G1xxx
(2)
Gxxxx< br>234
242n


1

2
1x
1x


1x
2
x
2
1
352n1


x(1x
2
x< br>4
Lx
2n
L)x
n
111xx
2< br>x
(3)
1xxxx(1)x
(1xxL )x(1xxL)

1x
2
1x1x
2
n
2424

n2

n
23n
2.9题 设G13x6x10x


2


x
证明：(1)
(1x)G12x3x4x(n1)x


23
3
(2)
(1x)G1xxx
(3)因为
(1x)G1
，所以有
G
22n
1
(1x)
3
证明（1）
G13x6x
2

< br>n2

n


x
2

< br>11
(1x)G12x3x
2

32
(1x) (1x)
(n1)x
n


（2）展开(1-x
2
)G= (1+x)(1-2x+x
2
) 当
x
(3)
(1x)G(13x3xx)(13x6x
32 32
1
时 有
)

1x1


1x1 x
=
13x6x
2
10x
3
15x
4< br>3x
2
9x
3
18x
4
30x
5< br>3x9x
2
18x
3
30x
4
x
3
3x
4
6x
5
10x
6
=1
G
1

3
(1x)
23


n3

n

n2

n

2.10 题
H14x10x20x

证明(1)
x(1 x)HG


3

2


x (2) 求H的表达式。
n0


n3

(k3)(k2)(k1)
k
3
6k
2
11k6
证明(1) 设H的第K+1项为h
k
，则h
k
=

=，

3


=
6
3*2*1

设G的前K+1项的和为G
k
，则G
k
=

2

3

k2

g

=+
+…+

k

2

2

2



k0

k

13

而


2


+


2

+…+


2


=1+
2
+

=1+

2
< br>3

k2

3*24*3(k2)*(k1)1
+… +
=1+
[3*2+4*3+…+(k+2)(k+1)]
222
1
(1+ 2
2
+ 3
2
+…+k
2
+3+6+…+3k+2+2+…+2) ①{注释：均为k项，分别为平方数列，等差数列，常数列}
2
(2k
2
 k)(k1)
3k(k1)113k(1k)
=1+[k(k+1)(2k+1)+ +2k] =1+++k
12
2624
(2k
2
k)( k1)9k(k1)12k12k
3
6k
2
11k6
G
= = = h
k


H=
126
1x
(2) 由H=1+4x+10x
2
+20 x
3
+…+(
3
n3
) x
+…=1+
n
4*3*25*4*3
2
(n3)(n2)(n1)
n
x
+ …+
x
+
x
+…
3*2*13*2*13*2*1
x3
x
3
对其3次积分得

H
=，对此积分式3次求 导得H=((( )))’’’。求解完毕。
6(1x)6(1x)
2.11题 a< br>n
=(n+1),G=

2

ax
n
n0

n
=1+4x+…(n+1)
2
x
n
+…,证明 (1-3x+3x
2
-x
2
)G是一个多项式,并求母函数G。

解: G=

ax
=

(n1)
n
n
n0n0

2
x
=

(n2 n1)x

G =
x

nx
n
2n
< br>2n1
+
2x
n0
n1

nx
n0
n1
+

x
n0
n
①

G =xG+
2xx1x1
1
+ G(1－x)= G= 即为所求

(1x)
2
1x
(1x)
2
(1x)
3
223

(1－3x＋3x
2
—x< br>2
)=(1－x)
3


(1－3x＋3x
—x
)G =(1－x)G =(1－x)
3


x1
=x+1 求解完毕。
( 1x)
3
①说明：可以由

nx
2
n1
2n1
=

(n1)
n0
2
x
n


x1
2n
(n1)x
,求序列{ a
n
}的母函数。 2.12题 已知a
n
=

k
, =

3
(1x)
n0k1
n1
解：设序列{ a
n
}的母函数为G(x), 则G(x)= a
0
+a
1
x+a
2
x+…+ a
n
x+ a
n1
x
nn1
+…

a
n
=

k
2
=1+2
2
+3
2
+…+n
2
+(n+1)
2

k1
n1

G(x)= 1+(1+2
2
)x+(1+2
2
+3
2
)x
2< br>+…+(1+2
2
+3
2
+…+n
2
+(n+1)< br>2
) x
n
+…
=1+x+ x
+…x+… +2
x(1+x+ x
+…x+…) +3
x(1+x+ x
+…x+…)+…
+(n+1)x(1+x+ x
+…x+…)+….
= (1+x+ x
+…x+…)(1+2
x+3x
+…+n
x2n2222n1
2n2n
2n22n222n
1
+ (n+1)x
+…) =
1x
2n

(n1)
n0

2
x
n


x1x1x1
12n


(n1)x
= G= G= 即为序列{ a
n
}的母函数。求解完毕。


(1x)
3
n0
(1x)
4
1x
(1x)
3

14


14xx
2
2.13题 已知
a
n


k,



(n 1)
3
x
n
,求序列{a
n
}的母函数。
4
(1x)
k1n0
n1
3
解：B(x)=1
3
+ 2
3
x+3
3
x
2
+……
1: a
0
=1
3
b
0
=1
3

x: a
1
=1
3
+2
3
b
1
=2
3

x
2
: a
2
=1
3
+2
3
+3
3
b
2
=3
3

……
a
0
= b
0

a
1
= b
0
+ b
1

a
2
= b
0
+ b
1
+ b
2

……
A(x)= b
0
(1+x+ x
2
+……)+ b
1
x(1+x+ x
2
+……)+ b
2
x
2
(1+x+ x
2
+……) +……

B(x)
14xx
2
=(1+x+ x
+……)( b
0
+ b
1
x+ b
2
x
+……) =
=
5
1x
(1x)
22
2.14题 已知
{P
n
}的母函数为
x

,

12xx
2
{P
n
}的递推关系
(a)求
P
0
和P
1
;
(b)
求序列
22
解: 特征多项式 K(x)= x-2x-1 x-2x-1=0 解得：r
1
=1+
2
r
2
=1-
2

P(x)=
A
1(12)x
+
B
1(12)x

A+B=0
-A(1-
2
)-B(1+
2
)=1 得：A=
22
, B=-
44
11
22
P(x)= ( -)=
4
1(12)x1(12)x
4
P
n
=
[(1
k0

2)
k
(12)
k< br>]x
k

2
nn
[(1+
2
)-(1-
2
)] P
0
=0, P
1
=1
4
2.15 题 已知
{a
n
}
的母函数为
2
1
,
求序列
{a
n
}
的递推关系
a
0
,a
1
。
2
1xx
解：特征多项式 K(x)= x-x+1
i
3< br>11
3

3
i


x-x+1=0解得： r
1
=+i=cos+isin=e, r
2
=-i= cos- isin= e
3

2
2
2
2
3333


2
A(x)=
AB
+
1r
1
x
1r
2
x
A
1
+A
2
=1, A
1
r
2
+ A
2
r
1
=0 解得：A
1
=1，A
2
=
1
3

a
n
=A
1
cos
1
nnnn
sin

a
0
=1, a
1
=1

+A
2
sin

= cos

+
3333
3
15


m


m1


m2

m n


，

，…，

的母函数为（1-x）
m1
2.16 题 证明序列

，


m


m


m

m
证明：当m=0时，命题成立。

m1k

k

X
=（1-x）
m
， 假设对于m-1，命题成立，即

k0

m1

则G
m
(X)=



mk

k


m1k

k


m1k

k

X
=


X
+


X
=X

G
m
(X)+ （1-x）
m


k0

m

k0

m

k0

m1

m
< br>
(1-X)

G
G
m
(X)=
(X)= （1-x）
m
，
1
1
=（1-x）
m1

m
1X

1X

2
x...n(
2.17题
已知G12x3

x1)
n
...证明 aG() x(1

24
n0

n3
n
)x(

3
)
(b)G

a
n
x,其中a
n


(k1)(n1k)
2n
n0k0
(c )a
n
(
n3
),n{0,1,2,...}

3

n3

n
(a) G(1x)


x
3

n0

证明： 由已知 G12x3x
2

24
(n1)x
n


(1x)
2
n
所以有 G
2
(1x)
4

n
又根据牛顿二项式展开定理 （1x）



x
k

k
k0


k41

k< br>
k3

k
令n4 则有（1x）


x


3

x
3

k0k0

4



n3

G(1x)


x
n
得证
3

n0

24

（b） G 

a
n
x , 其中 a
n


(k1)(n1k)

2n
n0k0
n
证明： 已知 G12x3x
2
(n1)x
n
(1x)
2
A(x)< br> 由性质 ： 若 b
k


a
i
则 B(x)
1x
i0
k

1
1xx
2< br>
1x
ii
1A(x)
G  即 g
i


a
n


1
2
(1x)1x
n0n0
A
iini
1G(x)
C  即 c
i


g
n


a
h



n1

(1x)
3
1x< br>n0n0h0n0
iin
1C(x)
DG  即 d
i


c
n


(h1)
4
(1x)1x
n0n0h0
2


16

可将d
i
表示成如下形式：
c
0
： a
0
(a
0
1)
c
1
： a
0
a
1
(a
1
2)
c
2
： a
0
a
1
a
2
(a
2
3)


c
n
： a
0
a
1
a
2
a
n
(a
n
n1)

d
n


c
i
(i1)(n1i)
i0
n

其中（i1）表示每列上的数值，（n1i）表示（k1）这个数的个数。所以 a
n


(k1)(n1k)成立
k0
n


n3

(c) 证 a
n


n

0,1,2,

3
< br>n




n3

证明： 题目即证


k1

n1k



n

0,1,2,
3

k0
n

n3

(1) 当 n0 时


k1

n1k

1

1 等式成立

3

k0
(2) 假设，当 nm -1 时等式成立 ，即



k1

n1k




k1

mk

1m2(m-1) 3(m-2)
k0k0
nm1
m1

(m2)(m 1)m

m13

m2





3


3
3！

(3) 当 nm 时有


k1

n1k




k1

m1k


k0k0
nm
1（m1）2m3(m1)
1m112(m1)21



k1

mk

12
k0
m1
(m1)1
m1(m1)1

(m1)



k1

mk


k0
m1
(m2)(m1)
2

m3

(m3)(m2) (m1)

m2

3(m2)(m1)

m2< br>
(m2)(m1)






3


3
3！3！2

3



m2

当 nm -1 时等式成立即


k1

mk


< br>
3

k0
m1
(m2)(m1)

m2

(m2)(m1)
所以

< br>k1

mk




22

3

k0

m3

即


k1

m1k



等式成立

3

k0
< br>n3

综合（），（12），（3） a
n


得证

3


17
m
m1

2.18题 用母函数法求下列递推函数关系的解.
(a)a
n
6a
n1
 8a
n2
0
(c)a
n
9a
n2
0(e)a
n
12a
n1
36a
n2
0
(b)a
n
14a
n1
49a
n2
0
(d)a
n
6a
n1
7a
n2
0
< br>(f)a
n
25a
n2
0
解(a)：x
2:a
2
6a
1
8a
0
0
x
3< br>:a
3
6a
2
8a
1
0
x
4
:a
4
6a
3
8a
2
0

)......
0(A(x)a
0
a
1
x)6x(A(x )a
0
)8x
2
A(x)
(16x8x
2
)A(x)a
0
a
1
x6a
0
xa
0(a
1
6a
0
)x
a
n
(a
1
6a
0
)x
ABA(14x)B(12x)(AB)(4A2 B)

16x8x
2
12x14x(12x)(14x) (12x)(14x)
a
0
1
ABa
0
6aa< br>2
2a
0
(6a
0
a
1
)a
1
4a
0
1

所以有

解之得:A=
01
(4a
0
a
1
)
11
(4A2B) a6a
2422
10

42
a
0
1
4
6a
0
a
1
(6a
0
a
1
)4a
0
2a
0
a
1
1
B(a
1
2a
0
)
11
2422
42
1

A(4a
0
a
1
)


2
因此


B
1
(a2a)
10

2

111111
n
故此A(x)(4a
0
a
1
)(a
1
2a
0
)(4a
0
a
1
)

(2x)(a
1
2a
0
)

(4x)
n
212x214x22
n0n0

11


[(4a
0
a
1
)2
n(a
1
2a
0
)4
n
(n2)
22
n0
所以A(x)
解(b)：x
2
:a
214a
1
49a
0
0
x
3
:a
3
14a
2
49a
1
0

x
4:a
4
14a
3
49a
2
0
):.. ....
(A(x)a
0
a
1
x)14x(A(x)a0
)49x
2
A(x)0

(1(4x49x
2
)A(x)a
0
a
1
x14a
0
xa< br>0
(a
1
14a
0
)x
a(a
114a
0
)x
ABA(17x)B(AB)7Ax
所以A(x )
0

114x49x
2
(17x)(17x)< br>2
(17x)
2
(17x)


ABa0
所以有


7Aa
1
14a
0
111
故此A(a
1
14a
0
)Ba
0
A a
0
(a
1
14a
0
)(a
1
7a
0
)
777
故此A(x)
1111
(a
1
14a
0
)(a
1
7a
0
)
71 7x7(17x)
2

n1
11
nn
(a
1
14a
0
)

(7)x(a
1
7a0
)

()(7)(参见题2.16)

1
77n0n0

11


[(a
1
14a< br>0
)(a
1
7a
0
)(n1)](1)
n< br>7
n
x
n
7
n0
7
1
所以an
[a
0
(a
0
a
1
)n](1)< br>n
7
n
7
18

解(c)：x2
:a
2
9a
0
0
x
3
:a3
9a
1
0

x
4
:a
4
9a
2
0
):......
(A(x)a
0
a
1
x)9x
2
A(x)0

所以有(19x)A(x )0
aax
ABA(13x)B(13x)(AB)(3A3B)x
于是A(x)
01
2

19x13x13x(13x)(1 3x)(13x)(13x)
①

ABa
0
故此有

②

3A3Ba
1
②3x①有6A3a
0a
1
11
于是有Aa
0
a
1
③
26
1111
将③代入①有Ba
0
Aa
0
a
0
a
1
a
0
a
1
④
262611

Aaa
10



26
即


B
1
a
1
a
01
26


1111111111
nn
故此A(x)(a0
a
1
)(a
0
a
1
)(a
0
a
1
)

3x(a
0
a
1
)

(1)
n
3
n
x
n
2613x 2613x26
n0
26
n0

1111


[(a
0
a
1
)(a
0
a
1)(1)
n
]3
n
x
n
2626
n0< br>1111
所以a
n
[(a
0
a
1
)( 1)
n
(a
0
a
1
)]3
n
(n 2)
2626
解(d)：x
2
:a
2
6a
17a
0
0
x
3
:a
3
6a
2< br>7a
1
0

x
4
:a
4
6a
3
7a
2
0
):......
(A(x)a
0
a
1
x)6x(A(x)a
0
)7x
2
A(x)0
所以(16x7x
2
)A(x)a
0
a1
x6a
0
x
a(a
1
6a
0
)x
ABA(1x)B(17x)(AB)(A7B)x
因而A(x)
0

16x7x
2
(17x)1x(17x)(1x)( 17x)(1x)
①

ABa
0

故此有

②

A7Ba
1
6a
0
②7①得8A a
1
a
0
1
于是有A(a
0
a
1
)③
8
将③代入①有Ba
0
Aa
0

1
(a
0
a
1
)
1
(7a
0
a
1
)④
88

A
1
(a
0
a
1
)

8
从而

B
1
( 7a
0
a
1
)

8


11 1
nn
111
故此A(x)(a
0
a
1
)( 7a
0
a
1
)(a
0
a
1
)

7x(7a
0
a
1
)

(1)
n
x
n

88
17x
8
1x8
n0 n0



[
1
(a
0
a
1
)7
n

1
(7a
0
a
1
) (1)
n
]x
n
88
n0
所以a
n

1
(a
0
a
1
)7
n

1< br>(7a
0
a
1
)(1)
n
(n2)
8 8


19

解(e)：x
2
:a
2
12a
1
36a
0
0
x
3
:a< br>3
12a
2
36a
1
0
x:a
412a
3
36a
2
0
):......
4
(A(x)a
0
a
1
x)12x(A(x)a
0
)36x
2
A(x)0
于是(112x36x)A(x)a< br>0
a
1
12a
0
x
2

从而A (x)
a
0
(a
1
12a
0
)x
A BA(16x)B(AB)6Ax

222
(112x36x)( 16x)(16x)(16x)(16x)
2
①
②
③
④

ABa
0
故有


6Aa
1
12a
0
1
由②有A2a
0
a
1
6

11
代入③就有Ba
0
Aa
0
(2 a
0
a
1
)a
0
a
1
66
1

A2aa
10


6
即

Ba
1
a
01

6

n1
11111

nn
1
从而A(x)(2a
0< br>a
1
)(a
0
a
1
)(2a
0
)

6x(a
0
a
1
)
()6
n
x
n
2
616x6(16x)6
n0< br>6
n0
1

111
nn


[( 2a
0
a
1
)(a
0
a
1
)(n 1)]6x

[a
0
(a
0
a
1)n]6
n
x
n
666
n0n0
1
所以a
n
[a
0
(a
0
a
1
)n]6
n
(n2)
6


解(f)：x
2
:a
2
25a
0
0
x
3
:a
3
 25a
1
0
x:a
4
25a
2
0
 ):......
2
4

(A(x)a
0
a
1
x)25x
2
A(x)0
故此（125x)A(x)a
0< br>a
1
x
从而A(x)

a
0
a
1
x
ABA(15x)B(15x)(AB)(5A5B)x

22
125x15x15x125x125x
2

1a
1
aA

2
0
10
1

ABa
0

故此

于是有

5A5Ba

1

B
1
a
1
a

01
2

10


1111111111
nn
从而A(x)(a
0
a
1
)(a
0
a1
)(a
0
a
1
)

5x(a
0
a
1
)

(1)
n
5
n
x
n
21015x21015x210
n0
210
n0

1111


[(a
0
a
1
)5< br>n
(a
0
a
1
)(1)
n
5
n
x
n
]x
n
(n2)
210210
n0


20

2.19 题 用特征值法求习题2.18的解。


2
特征值为

1


2
4
1



a
0
AB

A
2
(4a
0
a
1)
从而有

解之得


B
1
(a< br>1
2a
0
)

a
1
2A4B


2
n
11
于是a
n
(4a
0
a
1
)2(a
1
2a
0
)4
n
(n2)
22
(a)特征方程为

2
6

 80通解为：a
n
A2
n
B4
n

(b )特征方程为:

2
14

490特征根为:
1


2
7

Aa
0

a
0
A

从而有

解之得

1
a7(AB)
B(aa
1
)

1
0

7

1
故a
n
[a
0
(a
0
a
1
)n](1)
n
7
n
(n2)
7
通解为a
n
(ABn)(1)
n
7
n

特征根为:

1
3,

2
3通解为a
n
A3
n
B(1)
n
3
n
11

Aaa
10


a
0
AB

26

从而有

解之得


a
1
3A3B

B
1
a
1
a
01
26

111111
故a
n
[(a
0a
1
)(1)
n
(a
0
a
1
)]3
n
[a
0
(1(1)
n
)a
1< br>(1(1)
n
]3
n
(n2)
262626
(d)特征方程为:

2
6

70特征根为:
1
1,

2
7通解为a
n
A(1)
n
B7
n
1

A(7a
0
a
1
)


a
0
AB
11

8< br>从而有

解之得

故a
n
(7a
0
a
1
)(1)
n
(a
0
a
1
) 7
n
(n2)
88

a
1
A7B

B
1
(aa)
01

8

(e) 特征方程为:

2
12

360特征根为:

1
6,

2
6通解为a
n
(ABn)6
n

Aa
0


a
0
A
1

n
从而有

解之得

故a
n
 [a
0
(a
1
a
0
)n]6(n2)
1< br>6
Ba
1
a
0

a
1
6(A B)

6

2
(f)特征方程为:

250 特征根为:

1
5,

2
5通解为a
nA5
n
B(1)
n
5
n

A1
a
0

1
a
1

a
0AB

210
从而有

解之得

故an
[(
1
a
0

1
a
1
) (1)
n
(
1
a
0

1
a
1
)5
n
]
210210
B
1
a
0
1
a
1

a
1
5A5B
210

2.20 题
已知a
n
2a
n1< br>a
n2
0,
(c)特征方程为:

2
90
(a求一般解；)(求满足b)
0
a，01

1
a的特 解；
(c)求满足的a
0
=a
1
=2的特解；

解 (a)：特征方程为:

2
2

10特征根为:
< br>1
12,

2
12
n
通解为a
n< br>A(12)B(12)
n
1

A


AB0
22
解(b)：由a
n
0,a
11得

解之有



(12)A(12)B 1

B
1


22

1
因此 ，特解a
n
[(12)
n
(12)
n
]
2 2


A1

AB2
解(c)：由a
0a
1
2可得

解之有

A(12)B2

B1

(12)
nn
因此，特解a
n
(12)(12)

21

2.21 题
2.21 已知a
n
5
n
d(4)
n
, c和d为常数,nN,
求a
0
5,a
1
2时的c和d及序列 的递推关系


cd0

c2
解:由a
n< br>5,a
1
2得

解之有


5c4 d1

d3
因此，特解a
n
25
n
3 (4)
n
由于特征根为:

1
5,

2
4

故特征方程为:(

5)(

4)0即< br>
2


200
因此对应的递推关系为:a
n< br>a
n1
2a
n2
0或者 a
n
a
n1
20a
n2
2.22 题 已知
a
3
(1)
，c和d为常数，n

N,求{
a
=c
n
n
+d
n
n
}满足的递推关系。
2
解：由题意可知，
a
的特征方程为，（x-3）（x+1）=0,即
n
x< br>-2x-3=0,所以递推关系为
a
-2
a
nn1
-3a
n2
=0
n
n)(3)k和,
1
k是常数n ,N求,a
n
的递推关系{}
2.23 题
a
n
(k
1
k
2

2
解：特 征根为:

1


2
3,故特征方程为:(

3)
2
0,即:

2
6

90 ,

于是递推关系为:a
n
6a
n1
9a< br>n2
0
求解这个递推关系2,
2.24 题
设a
n
2a
n1
a


n2
5,a
0
1,a
1
解： 首先解得
a
2
=8
a
n
-2
a
n1< br>+
a
n2
=5 （1）

a
n1-2
a
n2
+
a
n3
=5 （2）
（1）-（2）
a
n
-3
a
n1
+3
a
n2
-
a
n3
=0
32
建立特征方程为：
x-3x3x-10

解这个方程得：
x
1

1
x
2

-1
x
3

13
nnn
设
a
n
=A(1)+B(-1)+C(13)
a
0
=A+B+C
a
1
=A-B+(13)C
a
2
=A+B+(19)C
解得A= 2 B= 7 C= -9
a
n
=2(1)
n
+7(-1)
n
- 9(13)
n


2.25题 设{a
n
}序列的母函数为
解：
43x
, 但b
0
=a,b
1
=a
1
-a
0
, …,b
n
=a
n
-a
n-1
, …, 求序列{b
n
}的母函数
3
(1x)(1xx)
设B的母函 数是B(n)b
0
b
1
xb
2
x
2
....b
n
x
n
b
0
a
0
x:b< br>1
a
1
a
0
x
2
:b
2
a
2
a
1
x
3
:b
3
a
3
a
2


)
B(x)b
0
 b
1
xb
2
x
2
....b
n
xn
a
0
(a
1
a
0
)x(a
2
a
1
)x
2
.....
即 B(x)b
0
b
1
xb
2
x
2
....b
nx
n
(1x)a
0
(1x)a
1
x.... ..
(1-x)(a
0
a
1
xa
2
x
2
....)（1x）A(x)



22
43x
1xx
3

2.26题 设G=a
0< br>+a
1
x+a
2
x
2
+…,且a
0
=1,a
n
=a
0
a
n-1
+a
1
an-2
+…+a
n-1
a
0
,试证1+xG
2
=G.
证明：因为G=a
0
+a
1
x+a
2
x< br>2
+….
x
2
:a
2
=a
0
a
1
+ a
1
a
0

x
3
:a
3
=a
0
a
2
+ a
1
a
1
+ a
2
a
0

x
4
:a
4
=a
0
a
3
+ a
1
a
2
+ a
2
a
1
+ a
3
a
0

+) …

G-1-X= a
0
+a
1
x-1-X+(a
0
a
1
+ a
1
a
0
) x
2
+ (a
0
a
2
+ a
1
a
1
+ a
2
a
0
) x
3
+…
因为a
0
=1，得a
1
=1
所以G-1-x= (a
0
a
1
+ a
1
a
0
) x
2
+ (a
0
a
2
+ a
1
a
1
+ a
2
a
0
) x
3
+…
=a
0
a
1
x< br>2
+a
1
a
0
x
2
+ a
0
a
2
x
3
+ a
1
a
1
x
3
+ a
2
a
0
x
3
+…
= a
0
(a
1
x
2
+ a
2
x
3
+…)+ a
1
x(a
0
x+a
1
x
2
…)+ a
2
x
2
( a
0
x +…)+…
= a
0
a
1
x
2
+a
0
a
2
x
3
+…+ a
1
x(a
0
x+a
1
x
2
+…)+ a
2
x
2
a
0
x +…
=a
0
a
0
x+a
0
a
1
x
2
+a
0< br>a
2
x
3
+…+a
1
x(a
0
x+ a
1
x
2
…)+ a
2
x
2
a
0
x +…-x
=-x+(a
0
x+a
1
x
2
+…)(a
0
+a
1< br>x +…)=-X+X(a
0
+a
1
x +…) (a
0
+a
1
x +…)
所以：G-1-X=-X+(a
0
+a
1
x +…)
2
x G-1=G
2
x
2.27 题 求下列递推关系的一般解：
(a)a
n
4a
n1
5
n
(b)a
n
6a
n1
53
n
(d)a< br>n
6a
n1
4(6)
n
(f)a
n
4a
n1
74
n
65
n
(h)a
n
4a
n1
(nn
2
)4
n
(i)an
a
n1
4n
3
6n
2
4n1< br>(k)a
n
2a
n1
8a
n2
3(4 )
n
143
n
(l)a
n
6a
n1
9a
n2
3
n
(n)a
n
2a
n1< br>2
n
3
n
4
n
解(a)：特征方程:

40，特征根:

4，齐次通解:a
n
A4
n

非齐次特解:a
n
B4
n
，代入齐次方程可得:B 5
nnnn1
非齐次的通解:a
n
A455A45
(c)a
n
4a
n1
4
n
(g)a
n
6a
n1
(6)
n
(2n3n
2
)
( j)a
n
7a
n1
12a
n2
52
n
43
n

(m)a
n
7a
n1
 9a
n2
3
n
解(b)：特征方程:

60，特征 根:

6，齐次通解:a
n
A(6)
n
，
5
非齐次特解:a
n
B3
n
代入齐次方程可得:B，

3
5
非齐次的通解:a
n
A(6)
n
 3
n
A(6)
n
53
n1
3
解(c )：特征方程:

40,特征根:

4,齐次通解:a
nA4
n
非齐次特解:a
n
(BCn)4
n
( 因为f(n)4
n
,4是一重特征根)

代入齐次方程可得:C1,非齐 次的通解:a
n
A4
n
(Bn)4
n
(AB n)4
n
设新的A为AB,故有a
n
(An)4
n
解(d)：特征方程:

60，特征根:

6，齐次通解:a
n
A(6)
n
非齐次特解:a
n
(BCn)(6)
n
(因为f(n)(6)
n
,6是一重特征根)

代 入齐次方程可得:C4，非齐次的通解:a
n
A(6)
n
(B4 n)(6)
n
(AB4n)(6)
n
设新的A为AB,故有a< br>n
(A4n)(6)
n
解(e)：特征方程:

4 0，特征根:

4，齐次通解:a
n
A4
n
非齐次 特解:a
n
(BCn)4
n
D5
n
(因为f(n )25
n
34
n
,4是一重特征根)

C3< br>代入非齐次方程可得:

即特解为a
n
(B3n)4
n
105
n


D10
非齐次的通解:a
n< br>A4
n
(B3n)4
n
105
n
(A B3n)4
n
25
n1
设新的A为AB,故有a
n(A3n)4
n
25
n1
解(f)：特征方程:

40，特征根:

4，齐次次通解:a
n
A4
n
，
非齐次特解:a
n
(BCn)4
n
D5
n
(因为f(n)74
n
65
n
,4是一重特征根)
C7
代入非齐次方程可得:

即特解为a
n
(B 7n)4
n
305
n


D30
非齐 次的通解:a
n
A4
n
(B7n)4
n
305
n
(AB7n)4
n
305
n
设新的A为AB ,故有a
n
(A7n)4
n
305
n

23

解(g)：特征方程:

60，特征根:

6，齐次次通解:a
n
A(6)
n
非齐次特解:an
(BCnDn
2
En
3
)(6)
n，
代入非齐次方程可得:(BCnDn
2
En
3
)( 6)
n
6[BC(n1)D(n1)
2
E(n1)
3
](6)
n1
(6)
n
[CD(2n1)E(3n< br>2
3n1)](6)
n
[3En
2
(2D3E) n(CDE)]
(6)
n
(2n3n
2
)
< br>C
3
2

3E3



故 有

2D3E2，解之得

D
5
，即非齐次特解为a
n
(B
3
n
5
n
2
n
3
)(6)
n
222

CDE0



E1

n
非齐次的通解:a
n
A(6)(B 
3
n
5
n
2
n
3
)(6)
n
(AB
3
n
5
n
2
n
3< br>)(6)
n
2222
23n
35
设新的A为AB,故有a
n
(Annn)(6)
22
解(h)：特征方程:
< br>40，特征根:

4，齐次通解:a
n
A4
n，
非齐次特解:a
n
(BCnDn
2
En
3< br>)4
n
，代入非齐次方程可得:
(BCnDn
2
En
3
)4
n
6[BC(n1)D(n1)
2
E (n1)
3
]4
n1
4
n
[CD(2n1)E (3n
2
3n1)]
4
n
[3En
2
(2 D3E)n(CDE)]4
n
(nn
2
)

C 
1

3E1
3


故有

2D3E1解之得

D0


CDE0
< br>E
1


3

即非齐次特解为a
n(B
1
n
1
n
3
)4
n
33< br>n
非齐次的通解:a
n
A4(B
1
n
1< br>n
3
)4
n
(AB
1
n
1
n
3
)4
n
3333
3n
11
设新的A为AB, 故有a
n
(Ann)4
33
解(i)：特征方程:

10，特征根:

1，齐次通解:a
n
A1
n
非 齐次特解:a
n
(BCnDn
2
En
3
Fn4
)1
n
BCnDn
2
En
3
F n
4

代入非齐次方程可得:
(BCnDn
2
En< br>3
Fn
4
)[BC(n1)D(n1)
2
E( n1)
3
F(n1)
4
]
[CD(2n1)E(3n
2
3n1)F(4n
3
6n
2
4n1]
4Fn
3
(3E6F)n
2
(2D3E4F)n(CD EF)
4n
3
6n
2
4n1

4F4

C0

3E6F6

D0


故有

解之得

2D3E4F4

E 0


CDEF1

F1
4
即非 齐次特解为a
n
Bn
非齐次的通解:a
n
ABn
4
设新的A为AB,故有a
n
An
4
解(j)：特征方程:< br>
2
7

120，特征根:

1
3 ,

2
4，
齐次通解:a
n
A3
n
B4
n
非齐次特解:a
n
C2
n
(DEn) 3
n
(因为f(n)52
n
43
n
,且3是一重特 征根)
代入非齐次方程可得:
(C2
n
(DEn)3
n]7[C2
n1
(DE(n1)3
n1
]12[C 2
n2
(DE(n2))3
n2
]

C2
n2
(41412)3
n2
[(9D21D12D)(9E n21E(n1)12E(n2))]
C2
n1
3
n1< br>52
n
43
n

C10
于是,可得

即非齐次特解为a
n
102
n
(D12n)3
n

E12
非齐次的通解:a
n
A3
n
 B4
n
102
n
(D12n)3
n
102
n
(AD12n)3
n
B4
n
设新的A为A D,故有a
n
102
n
(A12n)3
n
B 4
n


24

解(k)：特征方程:
< br>2
2

80特征根:

1
4,

2
2齐次通解:a
n
A(4)
n
B2
n
非齐次特解:a
n
(CDn)(4)
n
E3
n
(因为f(n)3(4)
n
143
n
,且-4是一重特 征根)
代入非齐次方程可得:
[(CDn)(4)
n
E3
n
]2[(CD(n1)(4)
n1
E3
n1
]8 [(CD(n2)(4)
n2
E3
n2
]

CCDDD
[(C)(Dn(n1)(n2))](4)
n
E3
n2
(968)(D)(4)
n
7E3
n222222
37
D(4)
n
E3
n
3( 4)
n
143
n
29

3
D10


D2

2
于是,可得

解之得
即非齐次特解为a
n
(C2n)(4)
n
183
n< br>
E18

7
E14


9
非齐次的通解:a
n
A(4)
n
B2
n
(C 2n)(4)
n
183
n
(AC2n)(4)
n
B2
n
183
n
设新的A为AC,故有a
n(A2n)(4)
n
B2
n
183
n
解 (l)：特征方程:

2
6

90特征根:

1


2
3齐次通解:a
n
(ABn)3
n
非齐次特解:a
n
(CDnEn
2
)3
n(因为f(n)3
n
,且3是二重特征根)
代入非齐次方程可得:
(C DnEn
2
)3
n
6(CD(n1)E(n1)
2
]3
n1
9(CD(n2)E(n2)
2
]3n2
[(C2CC)(D2DD)n(E2EE)(2D2D)2E( 2n1)E(4n4)]3
n

E(4n24n4)3
n
n
E23
3
n
故有E
1
即非齐次特解 为a
n
(CDn
1
n
2
)3
n
2 2
n
非齐次的通解:a
n
(ABn)3(CDn
1n
2
)3
n
((AC)(BD)n
1
n< br>2
)3
n
22
2n
1
设新的A为AC,新的B为 BD,故有a
n
(ABnn)3
2
2
解（m）：特征方程 ：

7

90
特征根：

1

713713
,

2


22
齐次 通解：
a
n
A(
713713
)B()
非齐次通解：
a
n
C3
n

22
nn1代入非齐次方程：
C37C39C3
n2
3
n
7
C3
n
(11)3
n
3
1
C()1
3
C3

n
故此非齐次方程的特解为：
a
n
(3)3

于是非齐次方程的通解为：
a
n
A(
713713
)B ()33
n

22
n
解（n）：特征方程：

20
特征根：

2
齐次通解：
a
n
A2

nnn
nnn
非齐次通 解：
a
n
(BCn)2D3E4
（因为
f(n)2 34
，是现齐次的一重特征根）
代入非齐次方程：
(BCn)2
n< br>D3
n
E4
n
2(BC(n1))2
n1< br>2D3
n1
2E4
n1
2111
2
n
CD3
n
(1)E4
n
(1)2
n
CD3
n
E4
n
3232
故有C＝1，D＝3，E＝2
nnn
故此非齐次方程的特解为：
a
n
(Bn)2332 4

234
nnn

nnnnnnn
于是非齐次方 程的通解为：
a
n
A2(Bn)23324(ABn)23 324

nnn
令新的A为A＋B，有：
a
n
(An)23324


25

310
2.28
a
n
a
n1
a
n2
，利用置换
b
n
log
2
(a
n
)
求解。
310
【解】：由
a
n
a
n1
a
n2
，两边取对数：
log
2
a
n< br>3log
2
a
n1
10log
2
a
n 2

令：
b
n
log
2
a
n
，则有
b
n
3b
n1
10b
n2
从而
b
n
3b
n1
10b
n2
0

nn
2
特征方程：

3

100
特征根：

1
2,

2
5
齐次通解：
b
n
A(2)B5

将
b
n
log
2
a
n
代入上式，有
log
2
a
n
A(2)
n
B5
n
a
n
2
A(2)
n
B5
n

2.29 题 a
n
=a
n-1
a
n-2
求这个递推关系的解
解：设 b
n
= log
2
a
n

由a
n
=a
n-1
a
n-2
得 b
n
－b
n-1
－b
n-2
=0 k(x)=x
2
－x－1=0
解得：r
1
=

11
(15)
，r
2
=
(15)
b
n
=A(r
1
)
n
+B(r
2
)
n
22
由


b
0
AB
brb2 b(15)b
0
rbb(15)b
0
2b
1
得
A
120

1

,B
101

bArBr
r
1
r
2
r
1
r
2
2525
12

1
n
b
n< br>=
2b
1
(15)b
0
15
n
(1 5)b
0
2b
1
15
()
＋
()
22
25
25
a
n
=2
b
n

2.30 题 解递推式a
n
=a
n-1
2
a
n-2
3

解： 令：

b
n
=log
2
a
n
b
n
=log
2
(a
n-1
2
a
n-2
3
) =2log
2
a
n-1
+3log
2
a
n-2
=2b
n-1
+3b
n-2
2

k(x)=x-2x-3=0
r
1
=3 r
2
=-1
b
n
=A3
n
+B(-1)
n
a
0
=1 b
0
=0
a
1
=2 b
1
=1
A+B=0 (1) 3A-B=1 (2)
由(1) (2)得：
A=14 B=-14
b
n
=(14)3
n
+(-14)(-1)
n
l og
2
a
n
=(14)3
n
+(-14)(-1)
n
n
(14)3
n
(-14)(-1)
a
n
=2
2.31题
a
n

7
a
n1
a12
n2
，
a
0
1
，
a
1
2
，解个递推关系。
【解】：由
a
n

7
a
n1
a
12
n2
，两边取对数：
log
2a
n
7log
2
a
n1
12log
2< br>a
n2

令：
b
n
log
2
a
n
，则有
b
0
log
2
10
，
b
1
log
2
20

b
n
7b
n1
12b
n2

从而
b
n
7b
n1
12b
n2
0

nn
2
特征方程：

7

120
特征根：

1
3,

2
4
齐次通解：
b
n
A3B4

由初值，由


AB0

A1
nn
，解之

于是有
b
n
34


3A4B1
B1
nn
将
b
n
log
2
a
n
代入上式，有
log
2
a
n
34a
n
2
34

nn

26

2.32 解下列递推关系 （a）
a
n
na
n 1
，
a
0
1
，
a
n
?
（b）
a
n
a
n1

【解】：（a）由
an
na
n1
，
a
0
1
，得：
a
n
n!

（b）
a
n
a
n1
11
a7
， （c）
aa
0
nn1
nn
23
1

1


n


特征方程：

10
特征根：

1
齐次通解：
a
n
A1
n
A

2
< br>2


1


2

1
11 1
代入非齐次方程：
BB
nn1n
2
n
222
n
非齐次特解：
a
n
B

B< br>
B2B1

B1

B1

从而非齐次特解：
a
n

A17（c）
a
n
a
n1
11
于是非齐次特解：
aA
n
2
n
2
n
1
a716< br> 所以
a
n
6
n

2
n
1

1


n



3

3


1


3

1

n
3
n
特征方程：

10
特征根：

1
齐次通解：
a
n
A1A
非齐次特解：
a
n
B

B
1111

BB
B3B1
2B1
nn1n
2
33 3
1111
从而非齐次特解：
a
n
()
n
于是非齐次特解：
a
n
A()
n

2
3< br>2
3
代入非齐次方程：
B
2
2
2.37 利用置换
a
n
b
n
解
a
n
(2a< br>n1
3a
n2
)
，
a
0
1
，
a
1
4
。
2
【解】：（置换法）将
a
n
b
n
代入，有
22
(1) 若
b
n
>0,
b
n
(2b
n1
3b
n2
)

b
n
2b
n1
3b
n2

n
2
特征方程：

2

30
特征根：

1
3,

2
1
通解：
b
n
A3B(1)


A

AB1

初值：
b
0
1
，
b
1
2


解得

3AB2< br>

B


故此，
b
n

3
4

1
4
3111
2
3(1)
n
[33
n
(1)
n
]
于是，
an
b
n
[33
n
(1)
n
]
2

44416
22
（2）若
b
n
<0,则有：
b
n
(2b
n1
3b
n2
)

b
n
(2b
n1
3b
n2
)

b
n
2b
n1
3b
n2

A
3
AB1


4
n
从而
b
n
A3B(1)
初值：
b
0
1
，
b
1
2


解得


1
3AB2
B



4
故此，
b
n
[33(1)]
于是，
a
n
b
n



27
1
4
nn2
1
[33
n
(1 )
n
]
2

16