Recurrence Relations and Sequences | 递推关系与数列

📚 Recurrence Relations and Sequences | 递推关系与数列

A recurrence relation is an equation that defines a sequence by expressing each term as a function of one or more of its preceding terms. Together with a set of initial conditions, a recurrence relation provides a complete and compact description of a sequence that may otherwise be difficult to write out term by term.

递推关系是一种通过将数列的某一项表示为前一项或前几项的函数来定义数列的方程。结合一组初始条件，递推关系能够完整而简洁地描述一个数列，而如果逐项写出，这种数列可能会非常冗长。

---

1. What Is a Recurrence Relation? | 什么是递推关系？

A recurrence relation for a sequence (a_n) is an equation that relates (a_n) to earlier terms, such as (a_{n-1}), (a_{n-2}), etc. For example, the Fibonacci sequence is defined by (a_n = a_{n-1} + a_{n-2}) with (a_0 = 0), (a_1 = 1).

数列 (a_n) 的递推关系是将 (a_n) 与前面的项（如 (a_{n-1})、(a_{n-2}) 等）联系起来的方程。例如，斐波那契数列由 (a_n = a_{n-1} + a_{n-2}) 定义，且 (a_0 = 0)，(a_1 = 1)。

The order of a recurrence relation is the number of previous terms required to compute the next term. A first-order relation involves only (a_{n-1}), while a second-order relation involves both (a_{n-1}) and (a_{n-2}).

递推关系的阶数是指计算下一项所需的前项数量。一阶递推关系只涉及 (a_{n-1})，而二阶递推关系同时涉及 (a_{n-1}) 和 (a_{n-2})。

---

2. First-Order Recurrence Relations | 一阶递推关系

A first-order recurrence relation has the general form (a_n = f(a_{n-1})), where (f) is some function. The simplest cases are arithmetic and geometric sequences.

一阶递推关系的一般形式为 (a_n = f(a_{n-1}))，其中 (f) 是某个函数。最简单的例子是算术数列和几何数列。

Arithmetic sequence: (a_n = a_{n-1} + d), with initial term (a_1 = a). The explicit formula is (a_n = a + (n-1)d).

算术数列：(a_n = a_{n-1} + d)，首项为 (a_1 = a)。其通项公式为 (a_n = a + (n-1)d)。

Geometric sequence: (a_n = r a_{n-1}), with initial term (a_1 = a). The explicit formula is (a_n = a r^{n-1}).

几何数列：(a_n = r a_{n-1})，首项为 (a_1 = a)。其通项公式为 (a_n = a r^{n-1})。

Arithmetic: (a_n = a + (n-1)d)  |  Geometric: (a_n = a r^{n-1})

算术：(a_n = a + (n-1)d)  |  几何：(a_n = a r^{n-1})

---

3. Finding a General Term from a First-Order Relation | 由一阶递推关系求通项

For a recurrence of the form (a_n = p a_{n-1} + q), where (p) and (q) are constants, we can find the explicit formula by identifying a fixed point. Let the fixed point be (L) such that (L = pL + q). Solving gives (L = frac{q}{1-p}) (provided (p neq 1)).

对于形如 (a_n = p a_{n-1} + q)（其中 (p)、(q) 为常数）的递推关系，我们可以通过寻找不动点来求通项公式。设不动点为 (L)，满足 (L = pL + q)。解得 (L = frac{q}{1-p})（前提是 (p neq 1)）。

Then define (b_n = a_n – L). Since (b_n = p b_{n-1}), the sequence (b_n) is geometric, and we obtain:

然后定义 (b_n = a_n – L)。由于 (b_n = p b_{n-1})，数列 (b_n) 是几何数列，于是得到：

(a_n = L + p^{n-1}(a_1 – L))

Example: Given (a_n = 2a_{n-1} + 3), (a_1 = 1). The fixed point is (L = 3/(1-2) = -3). Thus (a_n = -3 + 2^{n-1}(1 – (-3)) = -3 + 4 cdot 2^{n-1}).

示例：已知 (a_n = 2a_{n-1} + 3)，(a_1 = 1)。不动点为 (L = 3/(1-2) = -3)。因此 (a_n = -3 + 2^{n-1}(1 – (-3)) = -3 + 4 cdot 2^{n-1})。

---

4. Second-Order Linear Recurrences | 二阶线性递推关系

A second-order linear recurrence with constant coefficients has the form (a_n = p a_{n-1} + q a_{n-2}), where (p) and (q) are constants and (q neq 0). This type of recurrence appears frequently in advanced mathematics and in examination problems.

常系数二阶线性递推关系形如 (a_n = p a_{n-1} + q a_{n-2})，其中 (p)、(q) 为常数且 (q neq 0)。这类递推在高等数学和考试题目中十分常见。

To solve it, we assume a solution of the form (a_n = r^n). Substituting into the recurrence gives the characteristic equation:

为了求解，我们假设解的形式为 (a_n = r^n)。将其代入递推关系，得到特征方程：

(r^2 – p r – q = 0)

The roots of this quadratic equation determine the general form of the solution, as described in the next section.

该二次方程的根决定了通解的形式，具体内容将在下一节介绍。

---

5. Distinct Real Roots | 两个不等实根

If the characteristic equation has two distinct real roots (r_1) and (r_2), then the general solution is:

若特征方程有两个不相等的实根 (r_1) 和 (r_2)，则通解为：

(a_n = A r_1^n + B r_2^n)

where (A) and (B) are constants determined by the initial conditions (a_0) and (a_1) (or (a_1) and (a_2), depending on how the sequence is indexed).

其中 (A) 和 (B) 是由初始条件 (a_0) 和 (a_1)（或 (a_1) 和 (a_2)，取决于数列的编号方式）确定的常数。

Example: Solve (a_n = a_{n-1} + 2a_{n-2}) with (a_0 = 2), (a_1 = 3). The characteristic equation is (r^2 – r – 2 = 0), so (r = 2) or (r = -1). Thus (a_n = A cdot 2^n + B cdot (-1)^n). Using (a_0 = 2) gives (A + B = 2). Using (a_1 = 3) gives (2A – B = 3). Solving yields (A = 5/3), (B = 1/3). Therefore (a_n = frac{5}{3} cdot 2^n + frac{1}{3} cdot (-1)^n).

示例：求解 (a_n = a_{n-1} + 2a_{n-2})，其中 (a_0 = 2)，(a_1 = 3)。特征方程为 (r^2 – r – 2 = 0)，所以 (r = 2) 或 (r = -1)。因此 (a_n = A cdot 2^n + B cdot (-1)^n)。由 (a_0 = 2) 得 (A + B = 2)；由 (a_1 = 3) 得 (2A – B = 3)。联立解得 (A = 5/3)，(B = 1/3)。因此 (a_n = frac{5}{3} cdot 2^n + frac{1}{3} cdot (-1)^n)。

---

6. Repeated Root | 重根情形

If the characteristic equation has a repeated root (r), then the general solution takes a different form:

若特征方程有重根 (r)，则通解的形式有所不同：

(a_n = (A + Bn) r^n)

Here the factor (n) appears because a single basis function (r^n) is not sufficient to span all possible sequences satisfying the recurrence.

这里出现了因子 (n)，因为仅靠一个基函数 (r^n) 不足以表示所有满足该递推关系的数列。

Example: Solve (a_n = 4a_{n-1} – 4a_{n-2}) with (a_0 = 1), (a_1 = 4). The characteristic equation is (r^2 – 4r + 4 = 0), giving (r = 2) as a repeated root. Thus (a_n = (A + Bn)2^n). From (a_0 = 1), we get (A = 1). From (a_1 = 4), we get ((A + B) cdot 2 = 4), so (B = 1). Therefore (a_n = (1 + n)2^n).

示例：求解 (a_n = 4a_{n-1} – 4a_{n-2})，其中 (a_0 = 1)，(a_1 = 4)。特征方程为 (r^2 – 4r + 4 = 0)，得到重根 (r = 2)。因此 (a_n = (A + Bn)2^n)。由 (a_0 = 1) 得 (A = 1)；由 (a_1 = 4) 得 ((A + B) cdot 2 = 4)，所以 (B = 1)。因此 (a_n = (1 + n)2^n)。

---

7. Complex Roots | 复数根情形

If the characteristic equation has complex conjugate roots (r = alpha pm ibeta), the general solution can be written in the form (a_n = R^n(A cos ntheta + B sin ntheta)), where (R = sqrt{alpha^2 + beta^2}) and (theta = tan^{-1}(beta/alpha)).

若特征方程有一对共轭复数根 (r = alpha pm ibeta)，通解可以写成 (a_n = R^n(A cos ntheta + B sin ntheta)) 的形式，其中 (R = sqrt{alpha^2 + beta^2})，(theta = tan^{-1}(beta/alpha))。

This polar form is often more convenient than using powers of complex numbers directly, especially when evaluating the first several terms or when the sequence is expected to oscillate.

这种极坐标形式通常比直接使用复数的幂更方便，尤其是在计算前几项或预计数列会振荡时。

Example: The recurrence (a_n = 2a_{n-1} – 2a_{n-2}) with (a_0 = 1), (a_1 = 2) has characteristic equation (r^2 – 2r + 2 = 0), whose roots are (1 pm i). Here (R = sqrt{2}), (theta = pi/4). The general solution is (a_n = (sqrt{2})^n (A cos(npi/4) + B sin(npi/4))). Applying the initial conditions gives (A = 1), (B = 1). Thus (a_n = (sqrt{2})^n (cos(npi/4) + sin(npi/4))).

示例：递推关系 (a_n = 2a_{n-1} – 2a_{n-2})，其中 (a_0 = 1)，(a_1 = 2)，其特征方程为 (r^2 – 2r + 2 = 0)，根为 (1 pm i)。此时 (R = sqrt{2})，(theta = pi/4)。通解为 (a_n = (sqrt{2})^n (A cos(npi/4) + B sin(npi/4)))。代入初始条件得 (A = 1)，(B = 1)。因此 (a_n = (sqrt{2})^n (cos(npi/4) + sin(npi/4)))。

---

8. Summation of Sequences | 数列求和

Once the explicit formula for (a_n) is known, the sum of the first (n) terms can often be found using standard formulas.

一旦知道了 (a_n) 的通项公式，前 (n) 项的和通常可以用标准公式求得。

For an arithmetic sequence, the sum is:

对于算术数列，其和为：

(S_n = frac{n}{2}(2a_1 + (n-1)d))

For a geometric sequence, the sum is:

对于几何数列，其和为：

(S_n = frac{a_1(1 – r^n)}{1 – r})  ((r neq 1))

For sequences expressed as combinations of powers, such as (a_n = A r_1^n + B r_2^n), the sum can be computed by summing the two geometric parts separately.

对于由幂函数组合表达的数列，如 (a_n = A r_1^n + B r_2^n)，求和时可以分别对两个几何部分求和。

---

9. Recurrence Relations in Context | 递推关系在实际问题中的应用

Recurrence relations are widely used to model real-world phenomena. Population growth, compound interest, and the number of ways to climb a staircase (with steps of size 1 or 2) are all examples where recurrence relations provide a natural mathematical model.

递推关系被广泛用于模拟现实世界中的现象。人口增长、复利计算、以及爬楼梯的方式数（每次跨一级或两级）都是递推关系作为自然数学模型的例子。

In finance, the value of an investment after (n) periods often satisfies (V_n = (1 + r)V_{n-1} + P), where (r) is the interest rate and (P) is a periodic deposit. Solving this type of recurrence gives a closed-form formula for the future value.

在金融领域，经过 (n) 个周期后的投资价值通常满足 (V_n = (1 + r)V_{n-1} + P)，其中 (r) 是利率，(P) 是每期存款。求解这类递推关系可以得到终值的闭式公式。

In combinatorics, the Fibonacci recurrence (F_n = F_{n-1} + F_{n-2}) counts many different structures, from tilings of a (2 times n) board to paths in a graph.

在组合数学中，斐波那契递推 (F_n = F_{n-1} + F_{n-2}) 可以计数许多不同的结构，从 (2 times n) 棋盘的铺砖方式到图中的路径数。

---

10. Common Examination Techniques | 常见考试技巧

Examination questions on recurrence relations typically require one or more of the following skills: finding the first few terms, proving a given formula by induction, solving a linear recurrence, or using a recurrence to model a word problem.

关于递推关系的考试题目通常要求以下一项或多项技能：求数列的前几项、用数学归纳法证明给定公式、求解线性递推关系、或利用递推关系建模应用题。

• Always write down the initial conditions clearly; they determine the unique solution.

  务必清楚地写出初始条件；它们决定了唯一的解。

• When solving a second-order recurrence, always set up the characteristic equation explicitly before writing the general solution.

  在求解二阶递推关系时，务必先明确写出特征方程，再写出通解。

• Check your answer by computing the first two or three terms from both the recurrence and your explicit formula.

  通过分别用递推关系和显式公式计算前两三项来检验答案。

• For word problems, define the sequence clearly in terms of the quantity being counted or modelled.

  对于应用题，明确用所计数或建模的量来定义数列。

---

11. Worked Examination-Style Problem | 典型考试例题

Problem: A sequence is defined by (a_n = 5a_{n-1} – 6a_{n-2}) for (n geq 2), with (a_0 = 3) and (a_1 = 7). Find an explicit formula for (a_n).

题目：数列由 (a_n = 5a_{n-1} – 6a_{n-2})（(n geq 2)）定义，其中 (a_0 = 3)，(a_1 = 7)。求 (a_n) 的显式公式。

Solution: The characteristic equation is (r^2 – 5r + 6 = 0), which factors as ((r-2)(r-3) = 0). The roots are (r = 2) and (r = 3), so (a_n = A cdot 2^n + B cdot 3^n).

解答：特征方程为 (r^2 – 5r + 6 = 0)，因式分解为 ((r-2)(r-3) = 0)。根为 (r = 2) 和 (r = 3)，所以 (a_n = A cdot 2^n + B cdot 3^n)。

Using (a_0 = 3): (A + B = 3). Using (a_1 = 7): (2A + 3B = 7). Solving gives (A = 2), (B = 1). Therefore (a_n = 2 cdot 2^n + 3^n).

由 (a_0 = 3)：(A + B = 3)。由 (a_1 = 7)：(2A + 3B = 7)。联立解得 (A = 2)，(B = 1)。因此 (a_n = 2 cdot 2^n + 3^n)。

n	0	1	2	3
aₙ (recurrence)	3	7	17	43
aₙ (formula)	2+1=3	4+3=7	8+9=17	16+27=43

The two methods agree, confirming the formula is correct.

两种方法得到的结果一致，验证了公式的正确性。

---

12. Summary and Final Tips | 总结与要点

Recurrence relations offer a powerful way to define and analyse sequences. The key steps are: identify the order of the recurrence, write down the characteristic equation, determine the form of the general solution, and use the initial conditions to find the constants.

递推关系为定义和分析数列提供了一种强大的工具。关键步骤是：确定递推的阶数、写出特征方程、确定通解的形式、利用初始条件求常数。

Remember that the form of the general solution depends on the nature of the roots of the characteristic equation: distinct real roots, repeated roots, or complex roots. Practising each case will build confidence and speed in examinations.

请记住，通解的形式取决于特征方程根的性质：两个不等实根、重根、还是复数根。针对每种情况进行练习，将有助于在考试中建立信心并提高速度。

Published by TutorHao | Mathematics Revision Series | aleveler.com

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