递推关系简介 (Introduction to Recurrence Relations)

欢迎来到决策数学 2 (Decision Mathematics 2) 中最实用且优雅的课题之一！在日常生活中，许多事物都是随着离散的时间间隔逐步变化的。试想象一下你的储蓄账户每年赚取利息、自然保护区内的动物数量在每个繁殖季节后的增长，或是算法进行重复运算的过程。递推关系（recurrence relation，常称为差分方程 difference equation）其实就是一个利用数列中前面的一项或多项，来表示后续各项的方程。

虽然项与项之间的关系法则（term-to-term rule）能告诉你如何由一步推展到下一步，但如果你想求取 \(100\) 年后的数值，却要先算出中间每一年，那确实会相当繁琐。在这一章中，你将学会如何“解”这些递推关系，从而找出闭合形式（closed form，即以 \(n\) 表示第 \(n\) 项 \(u_n\) 的通项公式）。刚开始接触时千万不要被它吓倒；我们会把整个方法拆解成清晰易懂、逐步推进的步骤！

1. 理解递推关系 (Understanding Recurrence Relations)

什么是阶线性递推关系？

在决策数学 2 的课程范围内，重点集中在一阶线性递推关系（first-order linear recurrence relations）：

• 一阶（First-order）： 每一项 \(u_{n+1}\) 仅取决于紧接在前的一项 \(u_n\)。
• 线性（Linear）： 项 \(u_{n+1}\) 和 \(u_n\) 的次数仅为 \(1\) 次；它们不会互相相乘、平方，亦不会出现在 \(\sin\) 或 \(\sqrt{\phantom{x}}\) 等函数之内。

常系数一阶线性递推关系的一般形式为：

\(u_{n+1} - a u_n = g(n)\)    （或写成 \(u_{n+1} = a u_n + g(n)\)）

其中 \(a\) 为常数，而 \(g(n)\) 则是给定的 \(n\) 函数（可以是常数、包含 \(n\) 的多项式或指数项）。

齐次与非齐次 (Homogeneous vs Non-Homogeneous)

我们主要将这类关系分为两大类：

1. 齐次（Homogeneous）： 当 \(g(n) = 0\) 时。方程可简化为：
\(u_{n+1} - a u_n = 0\)   \(\implies\)   \(u_{n+1} = a u_n\)
比喻： 可以将其视为纯粹的复利增长，期间没有任何额外的资金注入或提取。

2. 非齐次（Non-Homogeneous）： 当 \(g(n) \neq 0\) 时。方程包含额外的“输入项”或“外力项”：
\(u_{n+1} - a u_n = g(n)\)
比喻： 可以视为一项每年赚取利息的投资，但同时你每年还会定期存入一笔固定金额。

重点提示： 一阶的意思是仅往回看一步。若等号右方为零，则为齐次；若右方包含额外的 \(n\) 函数，则为非齐次。

2. 解一阶线性齐次递推关系 (Solving First-Order Linear Homogeneous Recurrence Relations)

补函数与特征方程 (The Complementary Function and Auxiliary Equation)

我们先探讨齐次方程：

\(u_{n+1} - a u_n = 0\)

若 \(u_{n+1} = a u_n\)，代表每一项都是前一项乘以 \(a\)。这本质上就是一个等比数列（geometric sequence）！其解称为补函数（complementary function，记作 \(u_c\)）。

为了按照考评局要求的规范方法求解，我们会写出特征方程（auxiliary equation）。我们尝试代入形式为 \(u_n = m^n\) 的试探解：

\(m^{n+1} - a m^n = 0\)

两边同时除以 \(m^n\)，便得出特征方程：

\(m - a = 0 \implies m = a\)

因此，通解（即补函数）为：

\(u_n = A(a)^n\)

其中 \(A\) 为任意常数，需由初始条件（例如起始值 \(u_0\) 或 \(u_1\)）决定。

逐步示范：齐次关系

题目： 给定 \(u_0 = 5\)，解递推关系 \(u_{n+1} - 3u_n = 0\)。

第一步：写出特征方程。
将 \(u_{n+1}\) 换成 \(m\)，将 \(u_n\) 换成 \(1\)：
\(m - 3 = 0 \implies m = 3\)

第二步：写出通解。
\(u_n = A(3)^n\)

第三步：应用初始条件求 \(A\)。
当 \(n = 0\) 时，\(u_0 = 5\)：
\(5 = A(3)^0 \implies A = 5\)

最终答案：
\(u_n = 5(3)^n\)

重点提示： 对于任何形式为 \(u_{n+1} - a u_n = 0\) 的关系，特征方程均为 \(m - a = 0\)，可直接得出 \(u_n = A(a)^n\)。

3. 解非齐次递推关系 (Solving Non-Homogeneous Recurrence Relations)

完整解的结构

求解非齐次递推关系 \(u_{n+1} - a u_n = g(n)\) 时，完整的通解（general solution）必然由两部分相加而成：

\(u_n = \text{补函数 (CF)} + \text{特解 (PS)}\)

\(u_n = u_c + u_p\)

• 补函数（\(u_c\)）： 对应齐次方程 \(u_{n+1} - a u_n = 0\) 的解。这部分必定包含任意常数 \(A\)。
• 特解（\(u_p\)）： 满足完整方程 \(u_{n+1} - a u_n = g(n)\) 的任何一个特定数列。它不含任何任意常数。

求特解（\(u_p\)）

为了找出特解，我们会根据 \(g(n)\) 的数学形式作出合理的“猜测”（即试探解 trial solution），将其代入递推关系中，然后比较系数求出未知的常数。

以下是必须熟记的常见试探解对照表：

• 若 \(g(n) = k\)（常数）：
尝试设 \(u_p = C\)（常数）。
特殊情况： 若 \(a = 1\)（此时齐次解本身已是常数 \(A(1)^n = A\)），设常数将无法求出解。此时须乘以 \(n\)，尝试设 \(u_p = C n\)。

• 若 \(g(n) = p n + q\)（\(n\) 的一次多项式）：
尝试设 \(u_p = C n + D\)。
特殊情况： 若 \(a = 1\)，尝试设 \(u_p = n(C n + D) = C n^2 + D n\)。

• 若 \(g(n) = k \lambda^n\)（指数形式）：
尝试设 \(u_p = C \lambda^n\)。
特殊情况： 若 \(\lambda = a\)（底数与特征方程的根相同），尝试设 \(u_p = C n \lambda^n\)。

至关重要的原则：何时计算任意常数

考试重要警告： 切勿在加上特解之前就利用初始条件去求常数 \(A\)！你必须先建立完整的通解 \(u_n = u_c + u_p\)，然后才可以代入 \(n = 0\)（或 \(n = 1\)）来计算 \(A\)。

范例一：右方为常数

题目： 求递推关系 \(u_{n+1} - 2u_n = 6\) 的通解，并求出当 \(u_0 = 10\) 时的特解。

第一步：求补函数（\(u_c\)）。
将右方设为零：\(u_{n+1} - 2u_n = 0\)。
特征方程：\(m - 2 = 0 \implies m = 2\)。
因此，\(u_c = A(2)^n\)。

第二步：求特解（\(u_p\)）。
右方为常数 \(6\)。我们尝试设常数解：\(u_n = C\)。
若 \(u_n = C\)，则 \(u_{n+1} = C\)。
代入递推关系中：
\(C - 2C = 6\)
\(-C = 6 \implies C = -6\)
因此，\(u_p = -6\)。

第三步：写出通解。
\(u_n = u_c + u_p\)
\(u_n = A(2)^n - 6\)

第四步：利用初始条件求 \(A\)。
已知 \(u_0 = 10\)：
\(10 = A(2)^0 - 6\)
\(10 = A(1) - 6 \implies A = 16\)

最终答案：
\(u_n = 16(2)^n - 6\)

快速验算： 当 \(n = 0\) 时，\(u_0 = 16(1) - 6 = 10\)。由原递推关系可得 \(u_1 = 2(10) + 6 = 26\)。代入求得的公式：\(u_1 = 16(2)^1 - 6 = 32 - 6 = 26\)。结果完全吻合！

范例二：右方为一次式

题目： 给定 \(u_0 = 2\)，解递推关系 \(u_{n+1} - 3u_n = 4n\)。

第一步：求补函数（\(u_c\)）。
特征方程：\(m - 3 = 0 \implies m = 3\)。
\(u_c = A(3)^n\)。

第二步：求特解（\(u_p\)）。
由于 \(g(n) = 4n\) 为一次式，我们尝试设 \(u_n = C n + D\)。
则下一项为 \(u_{n+1} = C(n+1) + D = C n + C + D\)。
将两者代入 \(u_{n+1} - 3u_n = 4n\)：
\((C n + C + D) - 3(C n + D) = 4n\)
展开并整理同类项：
\(-2C n + (C - 2D) = 4n\)

比较 \(n\) 的系数与常数项：
• 比较 \(n\) 的系数：\(-2C = 4 \implies C = -2\)
• 比较常数项：\(C - 2D = 0 \implies -2 - 2D = 0 \implies 2D = -2 \implies D = -1\)
因此，\(u_p = -2n - 1\)。

第三步：写出通解。
\(u_n = A(3)^n - 2n - 1\)

第四步：求常数 \(A\)。
代入 \(n = 0\) 及 \(u_0 = 2\)：
\(2 = A(3)^0 - 2(0) - 1\)
\(2 = A - 1 \implies A = 3\)

最终答案：
\(u_n = 3(3)^n - 2n - 1\)  （亦可化简为 \(u_n = 3^{n+1} - 2n - 1\)）。

重点提示： 非齐次方程的解题步骤清晰分为两部分：先利用特征方程求出 \(u_c\)，再透过比较系数求出 \(u_p\)。记住必须先结合成 \(u_n = u_c + u_p\)，才可以代入条件求 \(A\)。

4. 递推关系的应用建模 (Modelling with Recurrence Relations)

将实际情境转化为递推关系

决策数学 2 的核心考核能力之一，就是将文字叙述的情境转化为递推关系、求解方程，并在实际情境中合理解读其意义。

阅读题目时，请特别留意以下常见字眼：

• 百分比增长／减少： 若某数量每年增加 \(r\%\)，则每个新数值等于前一年的数值乘以 \((1 + \frac{r}{100})\)。例如，增长 \(4\%\) 代表乘以 \(1.04\)。
• 固定增加或扣除： 像“固定费用 \(50\)”、“捕捞 \(300\) 条鱼”或“每年补充放养 \(120\) 只动物”等字眼，代表 \(g(n)\) 中的常数部分。若使总量增加则相加，若减少则相减。
• 初始状态： 起始数量代表 \(u_0\)（在时间 \(0\)）或有时代表 \(u_1\)（在第 \(1\) 年结束后）。请务必仔细阅读题目对时间 \(n\) 的定义。

综合建模范例：种群增长

情境： 一个野生动物信托基金负责管理森林内的鹿群。设 \(x_n\) 为第 \(n\) 年年初的鹿群数量。
在第 \(0\) 年年初，共有 \(800\) 只鹿。
在每一年内，由于自然繁殖，鹿群数量会增加 \(10\%\)。此外，在每年年底，护林员会将固定的 \(50\) 只鹿迁往其他公园，以防止过度繁衍。

(a) 建立以 \(x_n\) 表示 \(x_{n+1}\) 的递推关系。
(b) 解此递推关系，求以 \(n\) 表示 \(x_n\) 的表达式。
(c) 计算第 \(5\) 年年初的鹿群数量。
(d) 描述鹿群数量在长远而言的变化趋势。

解答：

(a) 部分：建立关系式
自然增长 \(10\%\) 对应的倍数为 \(1 + 0.10 = 1.1\)。
每年年底迁走鹿只会使数量减少 \(50\)。
因此：
\(x_{n+1} = 1.1 x_n - 50\)，初始条件为 \(x_0 = 800\)。
整理成标准形式：
\(x_{n+1} - 1.1 x_n = -50\)

(b) 部分：求解递推关系
补函数（\(x_c\)）：
特征方程：\(m - 1.1 = 0 \implies m = 1.1\)。
\(x_c = A(1.1)^n\)

特解（\(x_p\)）：
等号右方为常数（\(-50\)），故设 \(x_n = C\)：
\(C - 1.1 C = -50\)
\(-0.1 C = -50 \implies C = \frac{-50}{-0.1} = 500\)
因此，\(x_p = 500\)。

通解：
\(x_n = A(1.1)^n + 500\)

应用初始条件（\(x_0 = 800\)）：
\(800 = A(1.1)^0 + 500\)
\(800 = A + 500 \implies A = 300\)

因此，闭合形式的解为：
\(x_n = 300(1.1)^n + 500\)

(c) 部分：计算第 \(5\) 年的数量
代入 \(n = 5\)：
\(x_5 = 300(1.1)^5 + 500\)
\(x_5 = 300(1.61051) + 500 = 483.153 + 500 = 983.153\)
由于动物数量必须为整数，取最接近的整数得：\(983\) 只鹿。

(d) 部分：长远趋势
随着 \(n\) 增加，\(1.1^n\) 会无限增长（因为 \(1.1 > 1\)）。因此，项 \(300(1.1)^n\) 会趋向无限大。
长远而言，鹿群数量将会无止境地持续增长。

重点提示： 建模题目通常遵循三个标准步骤：(1) 将文字叙述转化为 \(u_{n+1} - a u_n = g(n)\)，(2) 透过“补函数 + 特解”配合边界条件求解，(3) 代入数值或分析 \(n \to \infty\) 时的极限，从而在现实背景下得出结论。

5. 常见错误与避忌 (Common Mistakes and How to Avoid Them)

1. 过早计算 \(A\)：
这是考生在试卷中最常犯的错误！不少同学写出 \(u_c = A(a)^n\) 后，就立刻代入 \(u_0\) 来求 \(A\)，最后才把特解加进去。这样做必然会得出错误答案。请切记：务必先写出完整通解 \(u_n = u_c + u_p\)，然后才代入初始值。

2. 下标混淆（\(n\) 与 \(n+1\)）：
当把一次式的试探解 \(u_n = C n + D\) 代入方程时，谨记 \(u_{n+1} = C(n+1) + D = C n + C + D\)。如果忘了把 \(C\) 分配乘进 \(+1\) 的项中，常数项的计算便会全盘出错。

3. “底数重叠”陷阱：
若你要解 \(u_{n+1} - 2u_n = 3(2)^n\)，尝试设 \(u_p = C(2)^n\) 会导致 \(C(2)^{n+1} - 2C(2)^n = 2C(2)^n - 2C(2)^n = 0\)，使 \(C\) 被完全消去！因为 \(2^n\) 本身已经是补函数的一部分，遇到这种情况，你必须尝试设 \(u_p = C n (2)^n\)。

4. 没有验算答案：
考试时你可以使用计算器。你随时可以用原有的递推关系逐步手算推出 \(n = 1\) 和 \(n = 2\) 的值，然后再代入你找出的通项公式验算。如果两者相符，你就可以对自己的答案有 \(100\%\) 的信心！

温习清单 (Summary Checklist)

• 标准形式： 将关系式整理成 \(u_{n+1} - a u_n = g(n)\)。
• 补函数： 解特征方程 \(m - a = 0 \implies m = a\)，得出 \(u_c = A(a)^n\)。
• 特解： 根据 \(g(n)\) 选择适当的试探形式，代入方程并比较系数以求出未知参数。
• 通解： 组合出 \(u_n = u_c + u_p\)。
• 求常数： 将给定的边界条件（如 \(u_0\)）代入完整的通解中求出 \(A\)。
• 合理解读： 在应用情境题目中，计算具体数值或探讨随 \(n\) 增加时的长远变化趋势。