如何求解形如 aₙ = k·aₙ₋₁ + b 的一阶线性递推数列通项？

Question

如何求解形如 $ a_n = k a_{n-1} + b $（其中 $ k \neq 1 $）的一阶线性非齐次递推数列的通项公式？当已知初始值 $ a_1 $ 时，常用的方法包括迭代法、待定系数法或构造等比数列。例如，通过引入辅助变量 $ b_n = a_n - c $，能否找到合适的常数 $ c $ 使得新序列 $ b_n $ 构成等比数列？若 $ k = 1 $，数列退化为等差数列，通项易得；但当 $ k \neq 1 $ 时，如何系统地推导出通项表达式？特别是当 $ b $ 为常数时，齐次解与特解的叠加方法是否适用？这类问题在算法分析与动态规划中频繁出现，掌握其通解结构具有重要意义。

Answer 1

一、递推数列通项求解：从基础到系统方法

1. 问题背景与基本形式

在算法分析、动态规划及离散数学中，形如：

\[ a_n = k a_{n-1} + b \quad (k \neq 1) \]

的一阶线性非齐次递推关系频繁出现。当 \( k = 1 \) 时，该式退化为等差数列，通项为 \( a_n = a_1 + (n-1)b \)，求解简单。但当 \( k \neq 1 \) 且 \( b \) 为常数时，需采用更系统的数学工具进行求解。

2. 迭代法：直观展开递推关系

从初始值 \( a_1 \) 出发，逐层展开递推式：

• \( a_2 = k a_1 + b \)
• \( a_3 = k a_2 + b = k(k a_1 + b) + b = k^2 a_1 + k b + b \)
• \( a_4 = k a_3 + b = k^3 a_1 + k^2 b + k b + b \)

观察可得一般形式：

\[ a_n = k^{n-1} a_1 + b \sum_{i=0}^{n-2} k^i \]

利用等比数列求和公式（\( k \neq 1 \)）：

\[ \sum_{i=0}^{n-2} k^i = \frac{1 - k^{n-1}}{1 - k} \]

因此通项为：

\[ a_n = k^{n-1} a_1 + b \cdot \frac{1 - k^{n-1}}{1 - k} \]

3. 构造法：引入辅助变量构造等比数列

设新序列 \( b_n = a_n - c \)，目标是使 \( b_n \) 成为等比数列。代入原式：

\[ b_n + c = k(b_{n-1} + c) + b \Rightarrow b_n = k b_{n-1} + (k c + b - c) \]

令非齐次项为零：

\[ k c + b - c = 0 \Rightarrow c(1 - k) = b \Rightarrow c = \frac{b}{1 - k} \]

于是：

\[ b_n = k b_{n-1} \Rightarrow b_n = b_1 \cdot k^{n-1} \]

而 \( b_1 = a_1 - c = a_1 - \frac{b}{1 - k} \)，故：

\[ a_n = b_n + c = \left(a_1 - \frac{b}{1 - k}\right) k^{n-1} + \frac{b}{1 - k} \]

这与迭代法结果一致，验证了构造的有效性。

4. 齐次解 + 特解法：标准微分方程思想迁移

将递推式分解为两部分：

1. 齐次方程： \( a_n^{(h)} = k a_{n-1}^{(h)} \Rightarrow a_n^{(h)} = A k^{n-1} \)
2. 特解： 因右侧为常数，设特解为常数 \( a_n^{(p)} = C \)，代入得：
3. \[ C = k C + b \Rightarrow C(1 - k) = b \Rightarrow C = \frac{b}{1 - k} \]

通解为：

\[ a_n = a_n^{(h)} + a_n^{(p)} = A k^{n-1} + \frac{b}{1 - k} \]

由初值 \( a_1 \) 确定常数 \( A \)：

\[ a_1 = A + \frac{b}{1 - k} \Rightarrow A = a_1 - \frac{b}{1 - k} \]

最终结果与前述方法完全一致。

5. 方法对比与适用场景分析

方法	适用条件	计算复杂度	可扩展性	典型应用场景
迭代法	小规模 n 或教学演示	O(n)	低	教学、手算验证
构造法	k ≠ 1, b 常数	O(1)	中	算法设计中的模式识别
齐次+特解	线性非齐次结构	O(1)	高	动态规划状态转移分析
生成函数法	复杂递推或理论研究	O(n log n)	极高	组合数学、复杂度证明

6. 在算法分析中的实际应用案例

考虑如下伪代码：

function f(n):
    if n == 1:
        return a1
    else:
        return k * f(n-1) + b

其时间复杂度满足递推关系 \( T(n) = T(n-1) + O(1) \)，但若涉及数值增长，则值域行为由上述通项决定。例如在动态规划中，状态转移：

\[ dp[i] = k \cdot dp[i-1] + b \]

常见于金融复利模型、资源衰减/增益系统、计数器衰减逻辑等。

7. Mermaid 流程图：通项求解决策路径

graph TD
    A[输入递推式 an = k*an-1 + b] --> B{k == 1?}
    B -- 是 --> C[等差数列: an = a1 + (n-1)*b]
    B -- 否 --> D[使用构造法或齐次+特解法]
    D --> E[设 cn = an - b/(1-k)]
    E --> F[cn 是等比数列: cn = c1 * k^{n-1}]
    F --> G[还原 an = cn + b/(1-k)]
    G --> H[输出通项公式]

8. 推广思考：当 b 不再是常数？

若 \( b = b_n \) 为关于 \( n \) 的函数（如多项式、指数），则需使用：

• 待定系数法设定特解形式
• 生成函数法（Z变换思想）
• 累加法处理变系数情形

例如当 \( b_n = r^n \)，可设特解为 \( A r^n \)（若 \( r \neq k \)），否则设为 \( A n r^n \)。

9. 数值稳定性与编程实现注意事项

在实际编码中（如Python或C++），直接递归会导致栈溢出或重复计算。推荐迭代实现：

def solve_recurrence(a1, k, b, n):
    if k == 1:
        return a1 + (n - 1) * b
    else:
        c = b / (1 - k)
        return (a1 - c) * (k ** (n - 1)) + c

注意浮点精度误差、大指数幂的溢出问题，必要时使用对数域或模运算（如在竞赛编程中）。

10. 总结与延伸方向

本系列方法构成了求解一阶线性非齐次递推的基础框架。对于高阶递推（如斐波那契型），可推广至特征方程法；对于非线性递推，则需借助不动点、渐近分析等高级工具。掌握这些技术不仅有助于理解算法行为，也为构建高效状态转移模型提供数学支撑。