最后更新: 2025-01-22 09:09 查看: 153 次纠错评论(0) 课件开VIP

递推关系

递推关系是离散变量之间变化规律中常见的一种方式，与生成函数一样是解决计数问题的有力工具。一般地，对数列 $\left\{u_n\right\}, ~ n=1, ~ 2, ~ \cdots$ ，如从某项开始，根据 $u_n$ 之前的 $k$ 项可推出 $u_n$ 的普遍规律，就称为递推关系。利用递推关系和初值在某些情况下可以求出序列的通项表达式 $u_n$ ，称为该递推关系的解。当然，并不是所有的递推关系都可求出其解，只是某些特殊类型有成熟解法。这里主要介绍解递推关系的几种常用方法。

下面先看两个递推关系的例子。
例7．6 13 世纪初意大利数学家 Fibonacci 研究过著名的兔子繁殖数目问题。设一对一雌一雄小兔刚满 2 个月时，便可繁殖出一雌一雄一对小兔。以后每隔 1 个月生一对一雌一雄小兔。由一对刚出生的小兔开始饲养到第 $n$ 个月，有多少对兔子？

解：设第 $n$ 个月有 $F_n$ 对兔子，它由两部分组成：（1）新生出的小兔，其数目等于能生小兔的大兔对数目，由于小兔满两个月才能繁殖，故数目为第（ $n-2$ ）个月时的兔对数目，即为 $F_{n-2}$ 。（2）原有小兔，其数目等于上月（即第 $n-1$ 个月）的兔对数目，即为 $F_{n-1}$ 。因此可建立如下的递推关系：

$$
F_n=F_{n-2}+F_{n-1}
$$

并有初始条件：$F_1=F_2=1$ 。即这是一个带有初值的递推关系。满足这种递推关系的数列称为Fibonacci数列。
例 7.7 设多重集 $S=\{\infty \cdot a, \infty \cdot b, \infty \llbracket c\}$ ，求其中 $a$ 不相邻的 $n$－排列数。
解：设 $a$ 不相邻的 $n-$ 排列数为 $a_n$ ，则 $a_1=3, a_2=3^2-1=8$ ，当 $n \geqslant 3$ 时，$a$ 不相邻的所有 $n-$排列可分为互不相容的两类：（1）第一个位置排 $b$ 或 $c$ ，剩下的 $n-1$ 个位置 $a$ 不相邻，由 $a_n$ 的定义知，$a$ 不相邻的 $(n-1)$－排列数为 $a_{n-1}$ ，根据乘法原则，这类排列数为 $2 a_{n-1}$ 。（2）第一个位置排 $a$ ，则第二个位置只能排 $b$ 或 $c$ ，而剩下的 $n-2$ 个位置 $a$ 不相邻，由 $a_n$ 的定义知，$a$ 不相邻的 $( n -2)-$排列数为 $2 a_{n-1}$ ，根据乘法原则，这类排列数为 $2 a_{n-2}$ 。由加法原则知，$a$ 不相邻的 $n$－排列数为： $a_n=2 a_{n-1}+2 a_{n-2}$ 。并有初始条件：$a_1=3, a_2=8$ ，即这是一个带有初值的递推关系。

下面介绍两种求解递推关系的方法。
求解常系数线性递推关系的特征根方法
定义 7.3 数列 $\left\{a_n\right\}$ 满足递推关系

$$
a_n=h_1 a_{n-1}+h_2 a_{n-2}+\cdots+h_k a_{n-k}
$$

$h_i$ 为常数，$i=1,2, \cdots k, n \geqslant k, h_k \neq 0$
称该递推关系为 $a_n$ 的 $k$ 阶常系数线性齐次递推关系。形如

$$
a_n=h_1 a_{n-1}+h_2 a_{n-2}+\cdots+h_k a_{n-k}+f(n)
$$

$h_i$ 为常数，$i=1,2, \cdots, k, n \geqslant k, h_k \neq 0$
的一类递推关系，称为 $a_n$ 的 $k$ 阶常系数线性非齐次递推关系。
$k$ 阶常系数线性齐次递推关系与微分方程

$$
y^{(k)}=h_1 y^{(k-1)}+h_2 y^{(k-2)}+\cdots+h_k y
$$

$h_i$ 为常数，$i=1,2, \cdots, k$
在结构上类似，而 $k$ 阶常系数线性非齐次递推关系与微分方程

$$
y^{(k)}=h_1 y^{(k-1)}+h_2 y^{(k-2)}+\cdots+h_k y+f(n)
$$

$h_i$ 为常数，$i=1,2, \cdots, k$

在结构上也类似，事实上求解方法也与相应的微分方程类似。下面不加证明地给出求解方法。
定义7．4 方程

$$
x^k-c_1 x^{n-1}-c_2 x^{k-2}-\cdots-a_k=0
$$

称为 $k$ 阶常系数线性齐次递推关系的特征方程，它的 $k$ 个根 $q_1, q_2, \cdots, q_k$ 称为该递推关系的特征根。其中 $q_i(i=1,2, \cdots, k)$ 是复数。

定理 $7.4 a_n=q^n, q \neq 0$ 是常系数线性齐次递推关系的解的充要条件是：$q$ 是该递推关系的特征根。

定理7．5 若 $k$ 阶常系数线性齐次递推关系的特征方程有 $k$ 个互异的特征根：$q_1, q_2, \cdots q_k$ ，则该递推关系的通解为

$$
a_n=c_1 q_1^n+c_2 q_2^n+\cdots+c_k q_k^n
$$

其中 $c_1, c_2, \cdots, c_k$ 为任意常数。
例 7.8 求例 7.7 的带初值递推关系的解。

解：例 7.7 的递推关系的特征方程为

$$
x^2-2 r-2=0
$$

其根是：$q_1=1+\sqrt{3}, ~ q_2=1-\sqrt{3}$ 。由定理 7.5 知，递推关系的通解为

$$
a_n=(1+\sqrt{3})^n c_1+(1-\sqrt{3})^n c_2
$$

要满足初值条件，故有

$$
\left\{\begin{array}{l}
(1+\sqrt{3}) c_1+(1-\sqrt{3}) c_2=3 \\
(1+\sqrt{3})^2 c_1+(1-\sqrt{3})^2 c_2=8
\end{array}\right.
$$

解方程组得

$$
c_1=\frac{5 \sqrt{3}-1}{6 \sqrt{3}}, c_2=\frac{5 \sqrt{3}+1}{6 \sqrt{3}}
$$

所以 $a$ 不相邻的 $n-$ 排列数为

$$
a_n=\frac{5 \sqrt{3}-1}{6 \sqrt{3}}(2+\sqrt{3})^n+\frac{5 \sqrt{3}+1}{6 \sqrt{3}}(2-\sqrt{3})^n
$$

定理 7.5 解决了特征方程的根皆为单根的情况。对于特征根为重根的情况，有下述结论。
定理 7.6 若 $k$ 阶常系数线性齐次递推关系的特征方程有 $t$ 个互异的特征根： $q_1, q_2 \cdots, q_t, m_1, m_2 \cdots m_t$ 为相应根的重数，且 $\sum_{i=1}^t m_i=k$ ，则该递推关系的通解为

$$
u_n=\sum_{i=1}^t \sum_{j=1}^{m_i} c_{i j} n^{j-1} q_i^n
$$

其中 $c_{i j}\left(1 \leqslant j \leqslant m_i, 1 \leqslant i \leqslant t\right)$ 为任意常数。

例 7.9 求解递推关系

$$
\begin{gathered}
a_n+a_{n-1}-3 a_{n-2}-5 a_{n-3}-2 a_{n-4}=0, n \geqslant 4 \\
a_0=1, a_1=a_2=1, a_3=2
\end{gathered}
$$

解：该递推关系的特征方程是

$$
x^4+x^3-3 x^2-5 x-2=0
$$

其特征根是 $-1,-1,-1,2$ 。由定理 7.6 得

$$
a_n=c_{11}(-1)^n+c_{12} n(-1)^n+c_{13} n^2(-1)^n+c_{21} 2^n
$$

代入初值得到以下方程组

$$
\left\{\begin{array}{l}
c_{11}+c_{21}=1 \\
-c_{11}-c_{12}-c_{13}+c_{21}=0 \\
c_{11}+2 c_{12}+4 c_{13}+4 c_{21}=0 \\
-c_{11}-3 c_{12}-9 c_{13}+8 c_{21}=2
\end{array}\right.
$$

解此方程组得

$$
c_1=\frac{7}{8}, c_{12}=-\frac{13}{16}, c_{13}=\frac{1}{16}, c_{21}=\frac{1}{8}
$$

故递推关系的解是

$$
a_n=\frac{7}{8}(-1)^n-\frac{13}{16} n(-1)^n+\frac{1}{16} n^2(-1)^n+\frac{1}{8} 2^n
$$

$k$ 阶常系数线性非齐次递推关系的通解与 $k$ 阶常系数线性非齐次微分方程的通解类似，也是齐次通解与特解之和，即

$$
a_n=a_n^{\prime}+a_n^*
$$

其中 $a_n{ }^{\prime}$ 是 $k$ 阶常系数线性非齐次递推关系所对应的 $k$ 阶常系数线性齐次递推关系

$$
a_n-h_1 a_{n-1}-\cdots-h_k a_{n-k}=0
$$

的通解，而 $a_n^{\prime}$ 是 $k$ 阶常系数线性非齐次递推关系的特解。对于 $a_n^{\prime}$ 由定理 7.6 即得，故关键是 $a_n^*$ 的求解。对于一般的 $f(n)$ 没有普遍的解法，在某些简单的情况下可用待定系数法求出 $a_n^*$ 。

一般地，（1）当 $f(n)$ 是 $n$ 的 $t$ 次多项式时，对应的特解形式为

$$
a_n^*=P_1 n^t+P_2 n^{t-1}+\cdots+P_t n+P_{t+1}
$$

其中 $P_1, P_2, \cdots, P_{t+1}$ 为待定系数。
（2）当 $f(n)$ 是 $\beta^n$ 的形式时，若 $\beta$ 不是对应的齐次递推关系的特征根，则对应的特解是 $P \cdot \beta^n$ ，其中 $P$ 为待定系数；若 $\beta$ 是对应的齐次递推关系的 $m$ 重特征根，则对应的特解是 $P \cdot n^m \cdot \beta^n$ ，其中 $P$ 为待定系数。

例 7.10 求解递推关系

$$
a_n+2 a_{n-1}=n+1, \quad n \geqslant 1, a_0=2
$$

解：该递推关系导出的齐次线性递推关系

$$
a_n+2 a_{n-1}=0
$$

的特征方程是

$$
x+2=0
$$

其特征根是 -2 。由定理 7.5 知其通解为

$$
a_n=c(-2)^n
$$

又因 $f(n)=n+1$ ，故它的特解具有形式

$$
a_n^*=P_1 n+P_2
$$

其中 $P_1, P_2$ 为待定系数。将其代入原递推关系

$$
P_1 n+P_2+2\left(P_1 \cdot(n-1)+P_2\right)=n+1
$$

即

$$
3 P_1 n+3 P_2-2 P_1=n+1
$$

比较上式两端 $n$ 的同次幂的系数，得

$$
P_1=\frac{1}{3}, P_2=\frac{5}{9}
$$

因此

$$
a_n^*=\frac{n}{3}+\frac{5}{9}
$$

是原递推关系的特解。而它的通解是

$$
a_n=c(-2)^n+\frac{n}{3}+\frac{5}{9}
$$

要它满足初值，只须 $c=\frac{13}{9}$ 。所以带初值的递推关系的解为

$$
a_n=\frac{13}{9}(-2)^n+\frac{n}{3}+\frac{5}{9}
$$

求解递推关系的生成函数法
在求解递推关系时，生成函数法也是一个有力的工具。用生成函数法求解递推关系的关键是用 $f(x)$ 表示 $\left\{a_n\right\}$ 的生成函数，即

$$
f(x)=\sum_{n=0}^{\infty} a_n x^n
$$

然后将 $\left\{a_n\right\}$ 的递推关系代入右边，便得到一个关于 $f(x)$ 的方程，解此方程，并将所得的解展开成幂级数，就可得到 $a_n$ 的表达式。

例 7.11 用生成函数法求解递推关系

$$
\begin{aligned}
& a_n=a_{n-1}+9 a_{n-2}-9 a_{n-3}, \quad n \geqslant 3 \\
& a_0=0, \quad a_1=1, \quad a_2=2
\end{aligned}
$$

解：设 $\left\{a_n\right\}$ 的生成函数为

$$
f(x)=a_0+a_1 x+a_2 x^2+\cdots+a_n x^n+\cdots
$$

则

$$
\begin{aligned}
& -x f(x)=-a_0 x-a_1 x^2-a_2 x^3-\cdots-a_{n-1} x^n-\cdots \\
& -9 x^2 f(x)=-9 a_0 x^2-9 a_1 x^3-9 a_2 x^4-\cdots-9 a_{n-2} x^n-\cdots \\
& 9 x^3 f(x)=9 a_0 x^3+9 a_1 x^4+\cdots+9 a_{n-3} x^n+\cdots
\end{aligned}
$$

以上四式相加得

$$
\begin{aligned}
& \left(1-x-9 x^2+9 x^3\right) f(x)=a_0+\left(a_1-a_0\right) x+\left(a_2-a_1-9 a_0\right) x^2 \\
& +\left(a_3-a_2-9 a_1+9 a_0\right) x^3+\cdots+\left(a_n-a_{n-1}-9 a_{n-2}+9 a_{n-3}\right) x^n+\cdots
\end{aligned}
$$

因为 $a_0=0, a_1=1, a_2=2$ ，且当 $n \geqslant 3$ 时，$a_n-a_{n-1}-9 a_{n-2}+9 a_{n-3}=0$ ，所以有

$$
\left(1-x-9 x^2+9 x^3\right) f(x)=x+x^2
$$

即

$$
\begin{aligned}
& f(x)=\frac{x+x^2}{1-x-9 x^2+9 x^3}=\frac{x+x^2}{(1-x)(1+x)(1-3 x)} \\
& =-\frac{1}{4} \cdot \frac{1}{1-x}-\frac{1}{12} \cdot \frac{1}{1+3 x}+\frac{1}{3} \cdot \frac{1}{1-3 x}
\end{aligned}
$$

而
$$
\begin{gathered}
\frac{1}{1-x}=1+x+x^2+\cdots+x^n+\cdots \\
\frac{1}{1+3 x}=1-3 x+3^2 x^2-\cdots+(-1)^n 3^n x^n+\cdots \\
\frac{1}{1-3 x}=1+3 x+3^2 x^2+\cdots+3^n x^n+\cdots \\
a_n=-\frac{1}{4}-\frac{1}{12} \cdot(-1)^n 3^n+\frac{1}{3} 3^n=-\frac{1}{4}-\frac{1}{4}(-1)^n 3^{n-1}+3^{n-1} 。
\end{gathered}
$$

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：指数型生成函数

下一篇：没有了

本文对您是否有用？有用 (0) 无用 (0)