习 题 三3-1 解下列递推关系：（1）⎩⎨⎧===+---1,001071021a a a a a n n n （2）⎩⎨⎧===++--1,00961021a a a a a n n n（3）⎩⎨⎧===+-2,00102a a a a n n （4）⎩⎨⎧==-=--121021a a a a a n n n（5）⎩⎨⎧===-+=---2,1,099210321a a a a a a a n n n n（解）（1）特征方程为010x 7x 2=+-。

解得2x 1=，5x 2=，故通解为n n n B A a 52⋅+⋅=分别令n ＝0，1，并代入初值1010==a a ,得关于系数A 、B 的方程组⎩⎨⎧=+=+1520B A B A 解得31-=A ，31=B 。

所以定解为 n a ＝()n n2531- （2）特征方程为0962=+-x x 。

解得321==x x ，故通解为()n n Bn A a 3⋅+=代入初值得⎩⎨⎧=+=1330B A A 解得0=A ，31=B 。

∴ 13331-==n nn n n a（3）特征方程为012=+x 。

解得i x ±=，故通解为()nn n i B i A a -⋅+⋅=代入初值得⎩⎨⎧=-=+2Bi Ai B A 解得i A -=，i B =。

∴ n a ＝()nn i i i i -+⋅-＝()11---+n n i i ＝()1111---+n n i )(可以看出，此数列为：0，2，0，－2，0，2，0，－2，……。

当然本数列可以不用特征根法求解，直接由解递推关系就可观察出2--=n n a a ，从而由初值即得结果。

（4）用特征根法求解可得解为n a ＝1。

本小题虽然是二阶递推关系，但由于其特殊性，并不一定要用特征根法求解，而用迭代法可能更容易计算出结果。

即0122a a a -=＝2×1－1＝1， 1232a a a -=＝2×1－1＝1，…… 立即可以观察出n a ＝1（n ＝0，1，2，…）。

（5）特征方程为09923=+--x x x 。

解得31-=x ，12=x ，33=x ，故通解为()n nn C B A a 33++-=代入初值得方程组⎪⎩⎪⎨⎧=++=++-=++2991330C B A C B A C B A 解得121-=A ，41-=B ，31=C 。

∴ ()n n n a 331413121⋅+---=＝()[]1131341--+--n n 3-2 求由A ，B ，C ，D 组成的允许重复的排列中AB 至少出现一次的排列数。

（解）设由A ，B ，C ，D 组成的字符串为s ＝()n c c c 21，串的长度为n ，满足条件的串有n a 个，则 n a ＝13-n a ＋()2242--+n n a ＋()3342--+n n a ＋……＋()0042+a即∑-=-=-1012n i i n n a a a ＋()14311--n 化简得221143----+-=-n n n n n a a a a ∴ ⎩⎨⎧====+----1044210221a a a a a a n n n n ,,解之得()()nn nn a 3263233263234---++-=3-3 求n 位二进制数中相邻两位不出现11的数的个数。

（解）设所求的数有n a 个，可将这样的数按左边第一位的值分成两类进行统计： （1） 第一位是0，这类数有1-n a 个；（2） 第一位是1，则按照题目条件，第二位就必须为0，故此类数有2-n a 个。

由加法法则，符合条件的数共有1-n a ＋2-n a 个。

因此，得n a 满足的递推关系为⎩⎨⎧==≥+=--3232121a a n a a a n n n ,,反推可得10=a ，所以⎥⎥⎦⎤⎢⎢⎣⎡⎪⎪⎭⎫ ⎝⎛--⎪⎪⎭⎫ ⎝⎛+=+++22225125151n n n n F a 3-4 利用递推关系求下列和（1）∑==nk n ks 02（解）由原式得⎩⎨⎧==+=-312121s s n s s n n , （3.2.2） 可以看出，1是齐次递推关系1-=n n s s 的特征根，故此非齐次定解问题的特解为*ns ＝()C Bn An n ++2＝Cn Bn An ++23 为了利用待定系数法确定待定常数A 、B 、C ，将*n s 代入（3.2.2）的第一式得()n C Bn An+++23-()()()()11123-+-+-n C n B n A ＝2n即()()C B A n B A An +-+--2332＝2n对任意的n ，上式成立的充分必要条件是n 的同次幂的系数相等，即方程组⎪⎩⎪⎨⎧=+-=-=003213C B A A B A 成立。

解之得 31=A ，21=B ，61=C 。

所以，（3.2.2）的特解为*ns ＝n n n 61213123++＝()()6121++n n n 从而得（3.2.2）的通解()()n n n n A n n n s s s 16121⋅+++=+=*其中A 为任意常数。

再由初值条件11=s 得()()612111++⋅＋A ＝1即0=A 。

所以（3.2.2）的定解，即和式的求和结果为()()6121++=n n n s n（2）()∑=-=nk n k k s 01（解）类似（1）得n s 满足的递推关系为⎩⎨⎧===-=--2021021s s s nn s s n n , 特解仍为*ns ＝()C Bn An n ++2＝()Cn Bn An ++23 但关于待定系数A 、B 、C 的方程则变为⎪⎩⎪⎨⎧=+--=-=013213C B A A B A 解之得 31A =，0B =，31C -=。

即特解为 *ns ＝n n 31313-＝()()311+-n n n 从而通解为n s ＝*ns ＋n s ＝()()311+-n n n ＋A再由初值条件0s 0=得0A =，所以n s ＝()()311+-n n n（3）()∑=+=nk n k k s 02（解）n s 满足的递推关系为⎩⎨⎧==+=--3021021s s n n s s n n ,,其特解为*ns ＝n n n 67233123++＝()()6721++n n n 通解为n s ＝*ns ＋n s ＝()()6721++n n n ＋nA 1⋅其中A 为任意常数。

以初值条件31=s 代入得()()6712111+⨯+⋅＋A ＝3即0=A 。

所以n s ＝()()6721++n n n（4）()()∑=++=nk n k k k s 021（解）n s 满足的递推关系为()()⎩⎨⎧==++=--6021101s s n n n s s n n ,,解之得n s ＝n n n n 234112341234+++＝()()()4321+++n n n n（解）设n 位四进制数中2和3必须出现偶数次的数有n a 个，2出现奇数次3出现偶数次的数为 n b 个，2出现偶数次3出现奇数次的数为 n c 个，两者都出现奇数次的数为 n d 个。

则对于满足题目要求的数而言，可将其按照最高位数字的值分为3类情况分别予以统计：（1）最高位是0或1，那么在后续的1-n 个数字中2和3还必须出现偶数次，这样的四进制数共有2 1-n a 个；（2）最高位是2，后1-n 位必须有奇数个2偶数个3，这样的数有1-n b 个；（3）最高位是3，后1-n 位必须有偶数个2奇数个3，这样的数有1-n c 个。

各类情形，没有重复的数。

由加法法则，得n a 满足的递推关系n a ＝21-n a ＋1-n b ＋1-n c 。

同理也可得n b 、n c 和n d 满足的递推关系，即⎪⎪⎩⎪⎪⎨⎧++=++=++=++=------------1111111111112222n n n n n n n n n n n n n n n n d c b d d c a c d b a b c b a a ， n ≥2 且知初值为21=a ，111==c b ，01=d 。

解之得∴ n a ＝1142--+n n ，（n ≥1）即所求的四进制数的个数。

3-6 试求由a ，b ，c 三个文字组成的n 位符号串中不出现aa 图像的符号串的数目。

（解）用n a 表示满足条件的串的个数，显然，1a ＝3，2a ＝23－1＝8，当n ≥3时，将符合要求的串分为两类：第一类： 第一字母不是a ，这样的串有21-n a 个；第二类： 首字母为a ，次字母必为b 或c ，这样的串有22-n a 个。

综合以上情况有()⎩⎨⎧==+=--8322121a a a a a n n n , 解之得n a ＝()()n n316323316323--+++ba ba ab b a ab b a ++++1000010001000设行列式的值为n d ，则将行列式按第一行展开得n n b a ba abb a ab b a d ++++=10000010001000＝()110000010001000-+++++n b a ba abb a ab b a b a－1100000100000001-+++n b a ba ab b a ab ab＝()2110000010001000--++++-+n n b a ba abb a ab b a ab d b a＝()b a +1-n d －ab 2-n d∴ ()⎩⎨⎧++=+=-+=--222121bab a d b a d abd d b a d n n n , 下面解递推关系，特征方程为()02=++-ab x b a x特征根为()221ba b a x -±+=,＝a ，b对于通解，需根据a 与b 的关系分两种情形进行讨论：（1）b a =≠0：此时特征根a x =为二重根，故通解为 n d ＝()n a Bn A +，其中A 、B 为任意常数。

代入21,=n 时的初值得关于A 、B 的方程组()()⎩⎨⎧=+=+22322a a B A aa B A 解之得1==B A ，所以行列式的值为n d ＝()n a n +1，1≥n（2）b a ≠：有两个不同的特征根a 和b ，通解是n d ＝n n Bb Aa +代入初值得⎩⎨⎧++=++=+2222b ab a B b A a ba bB aA 解之得b a a A -=，ab bB -= 故有n d ＝n n b a b b a b a a -+-＝b a b b a a n n ---++11 ＝nn n n n b ab b a b a a +++++---1221 ，1≥n3-8 在n ×m 方格的棋盘上，放有k 枚相同的车，设任意两枚不能互相吃掉的放法数为F k (n,m )，证明F k (n ，m )满足递推关系F k (n ，m)＝ F k (n -1，m )＋(m -k ＋1) F k-1(n -1，m )（证）将放法分为两类：其一是第一行无棋子，共有()m n F k ,1-种放法；其二是第一行有车（且只能有一个），可以随意选一个车出来，先将其余k －1个车放入下边的n －1行，有()m n F k ,11--种放法，然后再把选出来的车放入第一行的某个格子，但要求该格子所在的列没有车，有()1--k m 列可供选择，故第二类放法总共有()()m n F k m k ,111-+--种。