最后更新: 2025-01-22 09:09 ● 参与者查看: 24 次纠错分享参与项目词条搜索

递推关系

递推关系是离散变量之间变化规律中常见的一种方式，与生成函数一样是解决计数问题的有力工具。一般地，对数列 $\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}
$$

上一篇：指数型生成函数

下一篇：没有了

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