Recursive Formulas and Their Applications | 递归公式及其应用

📚 Recursive Formulas and Their Applications | 递归公式及其应用

A recursive formula defines each term of a sequence using one or more previous terms. It is a fundamental concept in mathematics, computer science, and real-world modelling. In this article, we will explore recursive formulas, how to solve them, and how they appear in A-level style problems.

递归公式通过一个或多个前面的项来定义数列中的每一项。它是数学、计算机科学和现实建模中的基本概念。本文将探讨递归公式、求解方法以及它们在 A-level 风格题目中的应用。

1. What Is a Recursive Formula? | 什么是递归公式？

A recursive formula consists of two parts: a starting value (or values) and a rule that connects each term to the previous one. For example, the sequence \(a_1 = 3\), \(a_{n+1} = a_n + 4\) defines the arithmetic sequence 3, 7, 11, 15, … The rule tells us how to move from one term to the next.

递归公式由两部分组成：初始值（一个或多个）和将每一项与前一项联系起来的规则。例如，数列 \(a_1 = 3\)，\(a_{n+1} = a_n + 4\) 定义了等差数列 3, 7, 11, 15, …。规则告诉我们如何从一项推出下一项。

Initial condition: the first term \(a_1\) is given.
Recurrence relation: the rule relating \(a_{n+1}\) to \(a_n\).

初始条件：给出首项 \(a_1\)。
递推关系：连接 \(a_{n+1}\) 与 \(a_n\) 的规则。

2. First-Order Recursive Formulas | 一阶递归公式

A first-order recurrence uses only the immediately previous term. The general form is \(a_{n+1} = f(a_n)\). A common type is the linear recurrence \(a_{n+1} = ra_n + d\), where \(r\) and \(d\) are constants. For example, \(a_1 = 2\), \(a_{n+1} = 3a_n – 1\) gives 2, 5, 14, 41, …

一阶递推只使用紧邻的前一项。一般形式为 \(a_{n+1} = f(a_n)\)。常见类型是线性递推 \(a_{n+1} = ra_n + d\)，其中 \(r\) 和 \(d\) 是常数。例如，\(a_1 = 2\)，\(a_{n+1} = 3a_n – 1\) 得到 2, 5, 14, 41, …。

To solve a first-order linear recurrence, we first find the fixed point \(L\) such that \(L = rL + d\). Then we set \(b_n = a_n – L\). This transforms the recurrence into \(b_{n+1} = r b_n\), which is geometric.

要求解一阶线性递推，我们先找到不动点 \(L\)，满足 \(L = rL + d\)。然后设 \(b_n = a_n – L\)，将递推转化为等比形式 \(b_{n+1} = r b_n\)。

\(a_{n+1} = r a_n + d \quad\Rightarrow\quad a_n – L = r^{n-1}(a_1 – L)\)

3. Second-Order Recursive Formulas | 二阶递归公式

Second-order recurrences depend on two previous terms. A classic example is the Fibonacci sequence: \(F_1 = 1\), \(F_2 = 1\), and \(F_{n+2} = F_{n+1} + F_n\). To find a closed form, we use the characteristic equation.

二阶递推依赖于前两项。经典例子是斐波那契数列：\(F_1 = 1\)，\(F_2 = 1\)，且 \(F_{n+2} = F_{n+1} + F_n\)。要求出通项公式，我们使用特征方程。

\(x^2 = x + 1\)

Solving gives \(x = \frac{1 \pm \sqrt{5}}{2}\). The general solution is \(F_n = A\alpha^{n-1} + B\beta^{n-1}\), where \(\alpha\) and \(\beta\) are the roots. Using the initial conditions determines \(A\) and \(B\).

解得 \(x = \frac{1 \pm \sqrt{5}}{2}\)。通解为 \(F_n = A\alpha^{n-1} + B\beta^{n-1}\)，其中 \(\alpha\) 和 \(\beta\) 是两根。利用初始条件确定 \(A\) 和 \(B\)。

4. The Characteristic Equation Method | 特征方程法

For a linear recurrence with constant coefficients, such as \(a_{n+2} + p a_{n+1} + q a_n = 0\), we assume a solution of the form \(a_n = \lambda^n\). Substituting gives the characteristic equation \(\lambda^2 + p\lambda + q = 0\).

对于常系数线性递推，如 \(a_{n+2} + p a_{n+1} + q a_n = 0\)，我们假设解的形式为 \(a_n = \lambda^n\)。代入后得到特征方程 \(\lambda^2 + p\lambda + q = 0\)。

Roots of characteristic equation	General solution
Distinct real roots \(\lambda_1, \lambda_2\)	\(a_n = A\lambda_1^{\,n} + B\lambda_2^{\,n}\)
Repeated real root \(\lambda\)	\(a_n = (A + Bn)\lambda^{\,n}\)
Complex roots \(r e^{\pm i\theta}\)	\(a_n = r^{\,n}(A\cos n\theta + B\sin n\theta)\)

5. Converting Recursive to Explicit Formulas | 从递推公式到通项公式

Explicit formulas allow us to compute any term directly without iterating. For the recurrence \(a_{n+1} = a_n + d\), we have \(a_n = a_1 + (n-1)d\). For a geometric recurrence \(a_{n+1} = r a_n\), we have \(a_n = a_1 r^{n-1}\).

通项公式允许直接计算任意一项，无需逐项迭代。对于递推 \(a_{n+1} = a_n + d\)，有 \(a_n = a_1 + (n-1)d\)。对于等比递推 \(a_{n+1} = r a_n\)，有 \(a_n = a_1 r^{n-1}\)。

For more complicated recurrences, we can use iterative substitution or generating functions. Iterative substitution means expanding the recurrence step by step until a pattern emerges.

对于更复杂的递推，我们可以使用迭代代入或母函数。迭代代入是指逐步展开递推，直到浮现出规律。

Example: \(a_1 = 2\), \(a_{n+1} = 2a_n + 3\)

Iterating: \(a_2 = 2(2)+3 = 7\), \(a_3 = 2(7)+3 = 17\). After solving, \(a_n = 5 \cdot 2^{n-1} – 3\).

迭代：\(a_2 = 2(2)+3 = 7\)，\(a_3 = 2(7)+3 = 17\)。求解后得 \(a_n = 5 \cdot 2^{n-1} – 3\)。

6. Applications in Compound Interest and Population Growth | 复利与人口增长中的应用

Recursive formulas model repeated processes. For compound interest, if the annual return rate is \(r\) and the initial amount is \(P\), then after \(n\) years the amount is \(A_n = P(1 + r)^n\). More generally, \(A_{n+1} = A_n + r A_n = (1+r)A_n\).

递归公式模拟重复过程。对于复利，若年回报率为 \(r\)，初始金额为 \(P\)，则 \(n\) 年后的金额为 \(A_n = P(1 + r)^n\)。更一般地，\(A_{n+1} = A_n + r A_n = (1+r)A_n\)。

In population dynamics, the discrete logistic model is \(N_{n+1} = N_n + k N_n (1 – N_n / K)\), where \(K\) is the carrying capacity. Such models show how recursion can generate rich behaviour, including stable states or chaos.

在种群动力学中，离散逻辑斯蒂模型为 \(N_{n+1} = N_n + k N_n (1 – N_n / K)\)，其中 \(K\) 是环境容量。这类模型展示了递归如何产生丰富的行为，包括稳定状态或混沌。

7. Recursion in Divide-and-Conquer Algorithms | 分治算法中的递归

In computer science, recursive formulas describe the time complexity of algorithms. For example, merge sort splits a problem of size \(n\) into two halves and then merges them. Its recurrence is \(T(n) = 2T(n/2) + n\).

在计算机科学中，递归公式描述算法的时间复杂度。例如，归并排序将规模为 \(n\) 的问题分成两半，然后合并。其递推为 \(T(n) = 2T(n/2) + n\)。

Solving this with the master theorem or iteration gives \(T(n) = O(n \log n)\). Other common recurrences include \(T(n) = T(n-1) + O(1)\) for linear scan and \(T(n) = 2T(n-1) + 1\) for the Tower of Hanoi.

使用主定理或迭代求解得到 \(T(n) = O(n \log n)\)。其他常见递推包括线性扫描的 \(T(n) = T(n-1) + O(1)\) 和汉诺塔的 \(T(n) = 2T(n-1) + 1\)。

8. Limits and Convergence of Recursive Sequences | 递归数列的极限与收敛

A recursive sequence may approach a finite limit. For \(a_{n+1} = f(a_n)\), if the sequence converges to \(L\), then \(L\) must satisfy \(L = f(L)\). This fixed-point condition is necessary for convergence.

递归数列可能趋向有限极限。对于 \(a_{n+1} = f(a_n)\)，若数列收敛于 \(L\)，则 \(L\) 必须满足 \(L = f(L)\)。这个不动点条件是收敛的必要条件。

For example, define \(a_{n+1} = \frac{1}{2}(a_n + 2/a_n)\) with \(a_1 = 1\). This is Newton’s method for \(\sqrt{2}\). The limit is the positive root of \(L = \frac{1}{2}(L + 2/L)\), which gives \(L = \sqrt{2}\).

例如，定义 \(a_{n+1} = \frac{1}{2}(a_n + 2/a_n)\)，其中 \(a_1 = 1\)。这是求 \(\sqrt{2}\) 的牛顿法。极限是 \(L = \frac{1}{2}(L + 2/L)\) 的正根，即 \(L = \sqrt{2}\)。

\(a_{n+1} = \frac{1}{2}\left(a_n + \frac{2}{a_n}\right) \;\longrightarrow\; \sqrt{2}\)

9. Common Mistakes and Exam Tips | 常见错误与考试技巧

Students often confuse the index in recursive formulas. For \(a_{n+1} = 3a_n – 1\), the second term is obtained by substituting \(n=1\), not \(n=0\). Always check whether the first term is \(a_0\) or \(a_1\).

学生在递归公式中经常混淆下标。对于 \(a_{n+1} = 3a_n – 1\)，第二项应代入 \(n=1\) 而不是 \(n=0\)。始终检查首项是 \(a_0\) 还是 \(a_1\)。

When using the characteristic equation, rewrite the recurrence so that all terms are on one side.
For non-homogeneous recurrences like \(a_{n+2} – 5a_{n+1} + 6a_n = 4\), find a particular solution first.

使用特征方程时，将递推改写为所有项在一边。
对于非齐次递推，如 \(a_{n+2} – 5a_{n+1} + 6a_n = 4\)，先求特解。

Exam questions often give a recurrence and ask for the limit. If the recurrence is monotone and bounded, the limit exists. Then solve the fixed-point equation.

考题常给递推并求极限。若递推单调且有界，则极限存在。然后解不动点方程即可。

10. Worked Example: Solving a Non-Homogeneous Recurrence | 例题：求解非齐次递推

Consider \(a_1 = 1\), \(a_{n+1} = 2a_n + 3\). Find \(a_n\) in terms of \(n\).

已知 \(a_1 = 1\)，\(a_{n+1} = 2a_n + 3\)，求用 \(n\) 表示 \(a_n\)。

Step 1: Fixed point: \(L = 2L + 3 \Rightarrow L = -3\).
Step 2: Let \(b_n = a_n + 3\). Then \(b_{n+1} = a_{n+1} + 3 = (2a_n + 3) + 3 = 2(a_n + 3) = 2b_n\).
Step 3: \(b_n = b_1 \cdot 2^{n-1} = (1+3)2^{n-1} = 4 \cdot 2^{n-1} = 2^{n+1}\).
Step 4: \(a_n = b_n – 3 = 2^{n+1} – 3\).

第一步：不动点：\(L = 2L + 3 \Rightarrow L = -3\)。
第二步：令 \(b_n = a_n + 3\)，则 \(b_{n+1} = a_{n+1} + 3 = (2a_n + 3) + 3 = 2(a_n + 3) = 2b_n\)。
第三步：\(b_n = b_1 \cdot 2^{n-1} = (1+3)2^{n-1} = 4 \cdot 2^{n-1} = 2^{n+1}\)。
第四步：\(a_n = b_n – 3 = 2^{n+1} – 3\)。

11. Recursive Formulas in Sequences and Series Exams | 数列与级数考试中的递归公式

In A-level mathematics, recursive formulas are used to define arithmetic and geometric progressions, as well as more complex sequences. Questions may ask you to generate terms, find a general formula, or determine convergence.

在 A-level 数学中，递归公式用于定义等差、等比数列以及更复杂的数列。题目可能要求生成项、求通项或判断收敛性。

Make sure you know how to use the recurrence relation in both directions: given \(a_n\), find \(a_{n+1}\), or given \(a_{n+1}\), solve for \(a_n\). This is particularly useful for inverse problems.

确保你掌握递推关系的双向使用：已知 \(a_n\) 求 \(a_{n+1}\)，或已知 \(a_{n+1}\) 解出 \(a_n\)。这在逆问题中尤其有用。

12. Summary | 总结

Recursive formulas provide a compact way to define sequences and model iterative processes. Key techniques include finding fixed points, using characteristic equations, and recognizing linear recurrences. With practice, you can quickly convert between recursive and explicit forms.

递归公式为定义数列和模拟迭代过程提供了一种简洁的方法。关键技巧包括寻找不动点、使用特征方程以及识别线性递推。通过练习，你可以快速在递归形式与通项形式之间转换。

Remember: always write down the initial condition, apply the recurrence carefully, and check your results with the first few terms.

记住：始终写出初始条件，谨慎应用递推关系，并用前几项检验结果。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Recursive Formulas and Their Applications | 递归公式及其应用