递推关系求解器

递推关系求解器

递推关系求解器通过求解其特征方程，在复平面上绘制根，并生成序列的前 N 项，来计算任何常系数线性齐次递推关系的闭式解。您可以将递推式作为有序系数列表输入，也可以作为自然数学表达式（如 a(n) = 3·a(n−1) − 2·a(n−2)）输入，工具会自动处理相异实根、重根和复共轭对。

什么是线性递推关系？

k 阶常系数线性齐次递推关系具有如下形式：

其中 c₁, c₂, …, c_k 是固定的实数，k 是阶数。结合 k 个初始值 a(0), a(1), …, a(k−1)，递推关系可以唯一地定义后续的每一项。经典的例子包括：

• 斐波那契 (Fibonacci)： a(n) = a(n−1) + a(n−2)，初始值 0, 1 → 0, 1, 1, 2, 3, 5, 8, 13, …
• 卢卡斯 (Lucas)： a(n) = a(n−1) + a(n−2)，初始值 2, 1 → 2, 1, 3, 4, 7, 11, 18, 29, …
• 佩尔数 (Pell numbers)： a(n) = 2·a(n−1) + a(n−2)，初始值 0, 1 → 0, 1, 2, 5, 12, 29, 70, …
• Tribonacci： a(n) = a(n−1) + a(n−2) + a(n−3)，初始值 0, 0, 1 → 0, 0, 1, 1, 2, 4, 7, 13, 24, …

特征方程法

为了找到 a(n) 的闭式公式，我们寻找形如 a(n) = rⁿ 的解。代入递推式并除以 r^n−k 可得：

这就是特征方程 —— 一个关于 r 的 k 次多项式方程。根据代数基本定理，它恰好有 k 个复根（计入重数）。递推关系的通解取决于这些根的结构：

情况 1：相异实根 r₁, …, r_k

常数 A₁, …, A_k 通过代入 n = 0, 1, …, k−1 并根据初始值求解线性方程组来确定。

情况 2：具有重数 m 的根 r

每个重根贡献 m 个线性无关的基序列 rⁿ, n·rⁿ, n²·rⁿ, …, n^m−1·rⁿ。

情况 3：复共轭根 r = ρ·e^iθ, r̄ = ρ·e^−iθ

当递推关系具有实系数时，复根总是成对以共轭形式出现。每一对根组合成一个具有几何包络线 ρⁿ 和频率 θ 的实数振荡项。

基于主根的增长分类

令 ρ = max|r_i| 为最大根模（即谱半径）。a(n) 的长期行为由以下因素决定：

斐波那契 —— 计算示例

考虑斐波那契递推式 a(n) = a(n−1) + a(n−2)，其中 a(0) = 0 且 a(1) = 1。

1. 特征方程： r² − r − 1 = 0
2. 求根（求根公式）： r = (1 ± √5) / 2，因此 φ ≈ 1.6180 且 ψ ≈ −0.6180
3. 通解形式： a(n) = A·φⁿ + B·ψⁿ
4. 代入初始条件： A + B = 0 且 A·φ + B·ψ = 1，解得 A = 1/√5, B = −1/√5
5. 比内 (Binet) 公式： a(n) = (φⁿ − ψⁿ) / √5

因为 |ψ| < 1，当 n → ∞ 时第二项会趋于消失，所以 a(n) 近似等于 φⁿ / √5 —— 这就是为什么斐波那契数每一步大约增长 φ 倍的原因。

如何使用本求解器

1. 选择输入模式：“引导模式”让您选择阶数并输入以逗号分隔的系数；“自由格式表达式”接受完整的递推式，如 a(n) = a(n-1) + 6*a(n-2) - 8*a(n-3)。
2. 输入系数或表达式。 支持小数 (0.5) 和分数 (1/2)。
3. 提供初始值。 必须提供恰好 k 个与递推阶数匹配的值：a(0), a(1), …, a(k−1)。
4. 选择要显示的项数（最高 60 项）。
5. 点击“求解”。结果页面将显示特征方程、复平面上的根位置、闭式公式以及序列的动画柱状图。

支持的情况与局限性

• 阶数： 1 到 6 阶（3 阶及以上的特征多项式通过 Durand–Kerner 迭代进行数值求解）。
• 实常系数： 不支持复系数；系数 c_i 必须为实数。
• 仅限齐次： 该工具求解齐次递推关系（不带强制项，如 + n 或 + 2ⁿ）。对于非齐次递推关系，可在此求解齐次部分，并另外添加特解。
• 数值精度： 结果以 IEEE-754 双精度计算；对于病态递推关系（根的模长跨度极大），验证横幅会标出闭式解与迭代值之间的任何偏差。

应用领域

• 算法分析： 分治算法的运行时间通常满足线性递推关系（主定理）。
• 组合数学： 计数序列 —— 卡特兰数 (Catalan numbers)、错排、铺砖问题 —— 经常通过递推式给出。
• 信号处理： 带有反馈的离散时间 LTI 系统是线性递推关系；其稳定性由根的位置决定（在单位圆内 ⇔ 稳定）。
• 人口动力学与金融： 复利计算、年龄结构人口模型、自回归 AR(p) 时间序列。
• 物理学： 一维晶格模型、紧束缚哈密顿量和转移矩阵法。

常见问题解答

什么是常系数线性递推关系？

常系数线性递推关系是形如 a(n) = c₁·a(n−1) + c₂·a(n−2) + … + c_k·a(n−k) 的方程，其中 c₁, c₂, …, c_k 是固定的实数，k 是阶数。序列中的每一项都是前 k 项的线性组合。常见的例子包括斐波那契递推 a(n) = a(n−1) + a(n−2) 和具有不同初始值的卢卡斯递推。

什么是递推式的特征方程？

给定递推式 a(n) = c₁·a(n−1) + c₂·a(n−2) + … + c_k·a(n−k)，其特征方程为 r^k − c₁·r^k−1 − c₂·r^k−2 − … − c_k = 0。该多项式方程恰好有 k 个复根（计入重数），递推式的每一个解都是形如 n^j·rⁿ 序列的线性组合，其中 r 是根，j 的取值范围最高到重数减 1。

如何获得 a(n) 的闭式公式？

求解特征方程以找到其根 r₁, r₂, …, r_k。如果所有根都是相异的，则闭式解为 a(n) = A₁·r₁ⁿ + A₂·r₂ⁿ + … + A_k·r_kⁿ，常数 A_i 通过代入初始值并求解线性方程组确定。如果根 r 的重数为 m，它将贡献 m 个基项：rⁿ, n·rⁿ, n²·rⁿ, …, n^m−1·rⁿ。本计算器会自动执行整个过程。

复根对序列意味着什么？

当递推关系具有实系数时，复根总是以共轭对 r = ρ·e^iθ 和 r̄ = ρ·e^−iθ 出现。这样的一对根会产生振荡行为：闭式解包含项 2·ρⁿ·[α·cos(nθ) − β·sin(nθ)]。如果 ρ 等于 1，序列以恒定幅度振荡；如果 ρ 小于 1，振荡衰减；如果 ρ 大于 1，幅度呈几何级数增长。

为什么主根能告诉我序列如何增长？

随着 n 变大，具有最大绝对值 |r| 的项会主导其他所有项，因为它的量值增长最快。因此，如果 ρ = max|r_i|，那么 |a(n)| 渐近地与 ρⁿ 成正比，如果主根是重根，则会带有一个额外的多项式因子。本求解器根据这一原理对序列进行分类：当 ρ < 1 时趋于零，当 ρ = 1 时有界，当 ρ > 1 时呈几何级数增长。

这个工具能求解斐波那契序列吗？

可以。输入递推式 a(n) = a(n−1) + a(n−2)，初始值为 0, 1。计算器推导出特征方程 r² − r − 1 = 0，根为 φ = (1 + √5)/2 和 ψ = (1 − √5)/2，并返回比内公式 a(n) = (φⁿ − ψⁿ) / √5。点击输入框上方的斐波那契快速示例可查看完整的求解过程。

该工具是否处理非齐次递推关系，如 a(n) = a(n−1) + n？

不处理 —— 该工具仅求解齐次递推关系（无强制项）。对于非齐次递推关系，可将通解分解为齐次部分（可在此求解）加上一个与强制项匹配的特解。常见的特解设法（待定系数法）包括：对于多项式强制项设同阶多项式，对于指数强制项设 C·rⁿ，或者对于三角函数强制项设 A·cos(nθ) + B·sin(nθ)。

延伸阅读

• 递推关系 — 维基百科
• 常系数线性递推 — 维基百科
• 特征方程 — 维基百科
• 斐波那契序列 — 维基百科
• Durand–Kerner 方法 — 维基百科

其他相关工具:

数列工具:

• 等差数列计算器 高精度
• 立方列表
• 前n个质数
• 几何序列计算器
• 斐波纳契数列表
• 质数列表
• 平方数列表
• 考拉兹猜想计算器
• 快乐数计算器
• 幻方生成器 精选
• 卡特兰数生成器
• 西格玛求和计算器 新
• 乘积符号计算器 (Pi记号) 新
• 帕斯卡三角形生成器 新
• 孪生素数查找器 新
• 分拆函数计算器 新
• 递推关系求解器 新