最后更新: 2025-01-22 09:09 查看: 113 次反馈能力测评会员8.2元/月赞助

递推关系

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

免费注册看余下 70%

非VIP会员每天5篇文章，开通VIP 无限制查看

《高等数学》难点解析

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

高等数学测评 函数与极限一元函数微分学一元函数积分学微分方程空间向量与代数多元微分学多元积分学无穷级数

《线性代数》难点解析

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

线性代数测评 行列式矩阵向量空间

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

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

概率统计测评 事件与概率一维随机变量与事件多维随机变量与事件随机变量的数字特征大数定律与中心极限定理统计量与抽样分布参数估计假设检验

上一篇：指数型生成函数

下一篇：没有了

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