7.2 线性递推关系

第 7.1 节用递归规则构造字符串和表达式。现在我们把同样的思想用于数列：按照整数下标排列的一列数。

数列通常写成

a_0,a_1,a_2,a_3,\ldots

符号 $a_n$ 表示“下标为 $n$ 的那一项”。下标是位置标记，并非乘法；例如 $a_3$ 表示第 $3$ 号位置的项。

递推关系把当前项连接到前面的项

递推关系是一条用一个或多个较早项来定义 $a_n$ 的等式。例如，

a_n=a_{n-1}+3 \qquad(n\ge1)

表示每一项都比前一项大 $3$ 。

只有递推式还不够，我们还需要一个初始条件，例如

a_0=2.

这样，每一项才会被唯一确定：

\begin{aligned} a_1&=a_0+3=2+3=5,\\ a_2&=a_1+3=5+3=8,\\ a_3&=a_2+3=8+3=11. \end{aligned}

所以数列开头是

2,5,8,11,\ldots

如果只把初始值改成 $a_0=10$ ，同一个递推式就会生成另一条数列。可以把递推式看成机器的运行规则，而初始条件决定机器从哪里启动。

阶数说明需要多少历史信息

递推关系的阶数是它向前回看的最远距离。

递推式

a_n=2a_{n-1}+1

只使用紧邻的前一项，因此是一阶递推。

递推式

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

会向前回看两个位置，因此是二阶递推。它通常需要两个初始值，例如 $a_0$ 和 $a_1$ 。

例如，给定

a_0=1,qquad a_1=1,qquad a_n=a_{n-1}+a_{n-2}\quad(n\ge2),

可得到

1,1,2,3,5,8,\ldots

计算 $n=2$ 时， $a_1$ 和 $a_0$ 都已经知道。如果只提供 $a_0$ ，那么 $a_1$ 仍然未知，递推机器便无法启动。

逐项生成还不是通项公式

递推关系给出的是局部规则。要计算 $a_{100}$ ，可能需要先算出前面所有项。通项公式则直接用 $n$ 表示 $a_n$ ，不再引用数列的早期项。

对递推关系

a_0=2,qquad a_n=a_{n-1}+3,

反复代入可得

\begin{aligned} a_n &=a_{n-1}+3\\ &=(a_{n-2}+3)+3\\ &=a_{n-2}+2\cdot3\\ &=\cdots\\ &=a_0+n\cdot3\\ &=2+3n. \end{aligned}

省略号表示重复执行同一种代入，直到下标降到 $0$ 。我们可以分别检查基础值与递推式来验证公式：

a_0=2+3(0)=2,

并且

(2+3n)-[2+3(n-1)]=3.

乘法增长展开为乘积

考虑

b_0=5,qquad b_n=2b_{n-1}.

逐层展开：

b_n=2b_{n-1}=2^2b_{n-2}=\cdots=2^n b_0=5\cdot2^n.

这是一个等比数列。更一般地，

b_0=c,qquad b_n=r b_{n-1}

的通项公式是

b_n=cr^n.

这里 $r$ 是固定的倍数。指数 $n$ 记录递推回到基础值之前，一共乘了多少次 $r$ 。

正在加载交互实验...

启动递推时间机器：配置一阶或二阶依赖，逐项揭示数值，并沿支撑某个选中结果的实际代入链向后检查。若移除必要的种子值，依赖轨道会在第一个未定义项处断开，而不会凭空猜出一个数。

正在加载概念检查...

正在加载本节练习...

计数问题会自然产生递推关系

第 6 章通过加法原理统计互斥情况。如果规模为 $n$ 的对象能够分成互斥类别，而每个类别删去最后一步后对应一个更小规模的对象，那么它们的数量就会满足递推关系。

例子：铺满长条板

设 $t_n$ 表示用以下瓷砖铺满长度为 $n$ 的长条板的方法数：

长度为 $1$ 的方砖；
长度为 $2$ 的多米诺骨牌。

瓷砖不能重叠，并且必须恰好覆盖整块长条板。

先给出两个初始计数：

t_0=1,qquad t_1=1.

为什么 $t_0=1$ 而不是 $0$ ？空长条恰好有一种铺法：什么砖都不放。这个“空构造”能让递推式在边界处正确工作。

对 $n\ge2$ ，按照最后一块砖分类所有铺法。

如果最后是方砖，移除它以后，会留下任意一个长度为 $n-1$ 的铺法，因此这一类有 $t_{n-1}$ 种。
如果最后是多米诺骨牌，移除它以后，会留下任意一个长度为 $n-2$ 的铺法，因此这一类有 $t_{n-2}$ 种。

两类互不相交，因为一种铺法不可能同时以两种砖结尾；两类也覆盖全部铺法，因为每个非空铺法都有最后一块砖。因此加法原理给出

t_n=t_{n-1}+t_{n-2}.

现在逐项计算：

\begin{aligned} t_2&=t_1+t_0=1+1=2,\\ t_3&=t_2+t_1=2+1=3,\\ t_4&=t_3+t_2=3+2=5,\\ t_5&=t_4+t_3=5+3=8. \end{aligned}

请注意这里的逻辑链条：

\text{按照最后一个构造步骤分类} \longrightarrow \text{与更小对象建立双射} \longrightarrow \text{相加各类数量} \longrightarrow \text{递推关系}.

这个递推式不是根据几项数字猜出来的模式，而是结构化计数论证的记录。

“线性”是什么意思

如果较早的数列项都只出现一次方，并且彼此不相乘，这个递推关系就是线性的。

例如，

a_n=5a_{n-1}-6a_{n-2}

是线性递推。相反，

a_n=a_{n-1}a_{n-2}

把两个早期项相乘，因此是非线性的。

如果等式中没有只依赖于 $n$ 的额外项，线性递推就是齐次的。所以

a_n=5a_{n-1}-6a_{n-2}

是齐次的，而

a_n=5a_{n-1}-6a_{n-2}+n

因为多出一个 $n$ ，所以是非齐次的。

若早期项前面的系数（例如 $5$ 和 $-6$ ）不随 $n$ 改变，就称递推关系具有常系数。

求解二阶齐次递推关系

考虑

a_n=5a_{n-1}-6a_{n-2} \qquad(n\ge2).

先寻找形如 $a_n=r^n$ 的等比解。代入递推式：

r^n=5r^{n-1}-6r^{n-2}.

当 $r\ne0$ 时，两边除以 $r^{n-2}$ ：

r^2=5r-6.

把所有项移到一边：

r^2-5r+6=0.

这就是特征方程。因式分解得到

(r-2)(r-3)=0,

所以两个不同的根是 $r=2$ 和 $r=3$ 。

每个根都给出一个等比解，它们的任意线性组合仍然是解：

a_n=A2^n+B3^n.

两个常数 $A$ 和 $B$ 由两个初始条件决定。假设

a_0=2,qquad a_1=5.

令 $n=0$ ：

A+B=2.

令 $n=1$ ：

2A+3B=5.

用第二个方程减去第一个方程的两倍，得到 $B=1$ ，进而 $A=1$ 。因此

\boxed{a_n=2^n+3^n}.

还可以直接验证：

5a_{n-1}-6a_{n-2} =5(2^{n-1}+3^{n-1})-6(2^{n-2}+3^{n-2}) =2^n+3^n.

重复特征根

如果特征方程中的同一个根 $r$ 出现两次，两个独立的构造块是

r^n \qquad\text{和}\qquad nr^n.

因此通解形式为

a_n=(A+Bn)r^n.

例如，递推关系

a_n=6a_{n-1}-9a_{n-2}

的特征方程是

r^2-6r+9=(r-3)^2=0,

所以解具有形式

a_n=(A+Bn)3^n.

常数 $A$ 和 $B$ 仍然由初始条件确定。

正在加载交互实验...

把方砖和多米诺骨牌拖入长条板，再把完整铺法图库折叠成“最后是方砖”和“最后是多米诺骨牌”两族。移除最后一块砖，就能看到它们与规模 $n-1$ 、 $n-2$ 的可逆对应；递推账本会根据实际构造同步更新。

正在加载概念检查...

正在加载本节练习...

注意

初始条件负责启动递推，阶数说明需要多少个早期值，而计数递推必须来自互斥且完备的分类，不能只因为前几项数字看起来吻合就下结论。

本节衔接

本节递推关系依赖固定数量的紧邻早期项。递归算法会产生另一种重要结构：一个规模为 $n$ 的问题被拆成若干规模为 $n/b$ 的子问题。第 7.3 节将把这种执行过程写成分治递推，并用递归树进行分析。

7.2 线性递推关系

第 7.1 节用递归规则构造字符串和表达式。现在我们把同样的思想用于数列：按照整数下标排列的一列数。

数列通常写成

a_0,a_1,a_2,a_3,\ldots

符号 $a_n$ 表示“下标为 $n$ 的那一项”。下标是位置标记，并非乘法；例如 $a_3$ 表示第 $3$ 号位置的项。

递推关系把当前项连接到前面的项

递推关系是一条用一个或多个较早项来定义 $a_n$ 的等式。例如，

a_n=a_{n-1}+3 \qquad(n\ge1)

表示每一项都比前一项大 $3$ 。

只有递推式还不够，我们还需要一个初始条件，例如

a_0=2.

这样，每一项才会被唯一确定：

\begin{aligned} a_1&=a_0+3=2+3=5,\\ a_2&=a_1+3=5+3=8,\\ a_3&=a_2+3=8+3=11. \end{aligned}

所以数列开头是

2,5,8,11,\ldots

如果只把初始值改成 $a_0=10$ ，同一个递推式就会生成另一条数列。可以把递推式看成机器的运行规则，而初始条件决定机器从哪里启动。

阶数说明需要多少历史信息

递推关系的阶数是它向前回看的最远距离。

递推式

a_n=2a_{n-1}+1

只使用紧邻的前一项，因此是一阶递推。

递推式

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

会向前回看两个位置，因此是二阶递推。它通常需要两个初始值，例如 $a_0$ 和 $a_1$ 。

例如，给定

a_0=1,qquad a_1=1,qquad a_n=a_{n-1}+a_{n-2}\quad(n\ge2),

可得到

1,1,2,3,5,8,\ldots

计算 $n=2$ 时， $a_1$ 和 $a_0$ 都已经知道。如果只提供 $a_0$ ，那么 $a_1$ 仍然未知，递推机器便无法启动。

逐项生成还不是通项公式

递推关系给出的是局部规则。要计算 $a_{100}$ ，可能需要先算出前面所有项。通项公式则直接用 $n$ 表示 $a_n$ ，不再引用数列的早期项。

对递推关系

a_0=2,qquad a_n=a_{n-1}+3,

反复代入可得

\begin{aligned} a_n &=a_{n-1}+3\\ &=(a_{n-2}+3)+3\\ &=a_{n-2}+2\cdot3\\ &=\cdots\\ &=a_0+n\cdot3\\ &=2+3n. \end{aligned}

省略号表示重复执行同一种代入，直到下标降到 $0$ 。我们可以分别检查基础值与递推式来验证公式：

a_0=2+3(0)=2,

并且

(2+3n)-[2+3(n-1)]=3.

乘法增长展开为乘积

考虑

b_0=5,qquad b_n=2b_{n-1}.

逐层展开：

b_n=2b_{n-1}=2^2b_{n-2}=\cdots=2^n b_0=5\cdot2^n.

这是一个等比数列。更一般地，

b_0=c,qquad b_n=r b_{n-1}

的通项公式是

b_n=cr^n.

这里 $r$ 是固定的倍数。指数 $n$ 记录递推回到基础值之前，一共乘了多少次 $r$ 。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

计数问题会自然产生递推关系

例子：铺满长条板

设 $t_n$ 表示用以下瓷砖铺满长度为 $n$ 的长条板的方法数：

长度为 $1$ 的方砖；
长度为 $2$ 的多米诺骨牌。

瓷砖不能重叠，并且必须恰好覆盖整块长条板。

先给出两个初始计数：

t_0=1,qquad t_1=1.

为什么 $t_0=1$ 而不是 $0$ ？空长条恰好有一种铺法：什么砖都不放。这个“空构造”能让递推式在边界处正确工作。

对 $n\ge2$ ，按照最后一块砖分类所有铺法。

如果最后是方砖，移除它以后，会留下任意一个长度为 $n-1$ 的铺法，因此这一类有 $t_{n-1}$ 种。
如果最后是多米诺骨牌，移除它以后，会留下任意一个长度为 $n-2$ 的铺法，因此这一类有 $t_{n-2}$ 种。

两类互不相交，因为一种铺法不可能同时以两种砖结尾；两类也覆盖全部铺法，因为每个非空铺法都有最后一块砖。因此加法原理给出

t_n=t_{n-1}+t_{n-2}.

现在逐项计算：

\begin{aligned} t_2&=t_1+t_0=1+1=2,\\ t_3&=t_2+t_1=2+1=3,\\ t_4&=t_3+t_2=3+2=5,\\ t_5&=t_4+t_3=5+3=8. \end{aligned}

请注意这里的逻辑链条：

\text{按照最后一个构造步骤分类} \longrightarrow \text{与更小对象建立双射} \longrightarrow \text{相加各类数量} \longrightarrow \text{递推关系}.

这个递推式不是根据几项数字猜出来的模式，而是结构化计数论证的记录。

“线性”是什么意思

如果较早的数列项都只出现一次方，并且彼此不相乘，这个递推关系就是线性的。

例如，

a_n=5a_{n-1}-6a_{n-2}

是线性递推。相反，

a_n=a_{n-1}a_{n-2}

把两个早期项相乘，因此是非线性的。

如果等式中没有只依赖于 $n$ 的额外项，线性递推就是齐次的。所以

a_n=5a_{n-1}-6a_{n-2}

是齐次的，而

a_n=5a_{n-1}-6a_{n-2}+n

因为多出一个 $n$ ，所以是非齐次的。

若早期项前面的系数（例如 $5$ 和 $-6$ ）不随 $n$ 改变，就称递推关系具有常系数。

求解二阶齐次递推关系

考虑

a_n=5a_{n-1}-6a_{n-2} \qquad(n\ge2).

先寻找形如 $a_n=r^n$ 的等比解。代入递推式：

r^n=5r^{n-1}-6r^{n-2}.

当 $r\ne0$ 时，两边除以 $r^{n-2}$ ：

r^2=5r-6.

把所有项移到一边：

r^2-5r+6=0.

这就是特征方程。因式分解得到

(r-2)(r-3)=0,

所以两个不同的根是 $r=2$ 和 $r=3$ 。

每个根都给出一个等比解，它们的任意线性组合仍然是解：

a_n=A2^n+B3^n.

两个常数 $A$ 和 $B$ 由两个初始条件决定。假设

a_0=2,qquad a_1=5.

令 $n=0$ ：

A+B=2.

令 $n=1$ ：

2A+3B=5.

用第二个方程减去第一个方程的两倍，得到 $B=1$ ，进而 $A=1$ 。因此

\boxed{a_n=2^n+3^n}.

还可以直接验证：

5a_{n-1}-6a_{n-2} =5(2^{n-1}+3^{n-1})-6(2^{n-2}+3^{n-2}) =2^n+3^n.

重复特征根

如果特征方程中的同一个根 $r$ 出现两次，两个独立的构造块是

r^n \qquad\text{和}\qquad nr^n.

因此通解形式为

a_n=(A+Bn)r^n.

例如，递推关系

a_n=6a_{n-1}-9a_{n-2}

的特征方程是

r^2-6r+9=(r-3)^2=0,

所以解具有形式

a_n=(A+Bn)3^n.

常数 $A$ 和 $B$ 仍然由初始条件确定。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

注意

初始条件负责启动递推，阶数说明需要多少个早期值，而计数递推必须来自互斥且完备的分类，不能只因为前几项数字看起来吻合就下结论。