数列与递推方法

一阶线性递推

最基础的递推形式是：

$$a_{n+1} = pa_n + q$$

其中 $p, q$为常数。当$p=1$时退化为等差数列；当$q=0$ 时退化为等比数列。

特征根法

对于 $p \neq 1$的情况，先求不动点$x$（满足 $x=px+q$），即 $x=\frac{q}{1-p}$。然后令 $b_n = a_n - x$，则：

$$b_{n+1} = a_{n+1}-x = (pa_n+q)-(px+q) = p(a_n-x) = pb_n$$

因此 $\lbrace b_n\rbrace $是公比为$p$的等比数列，通项为$b_n = b_1 \cdot p^{n-1}$，进而：

$$a_n = x + (a_1 - x)p^{n-1} = \frac{q}{1-p} + \left(a_1 - \frac{q}{1-p}\right)p^{n-1}$$

记忆口诀

一阶线性递推 → 求不动点 → 减去不动点得等比 → 等比通项加不动点。

含 $n$ 的变系数一阶线性递推

形如 $a_{n+1} = p(n)a_n + q(n)$ 的递推，方法为：

1. 先解对应的齐次形式 $a_{n+1}=p(n)a_n$，即 $a_n = a_1\prod_{k=1}^{n-1}p(k)$
2. 再用常数变易法求特解

一阶线性非齐次递推的常数变易法

对于 $a_{n+1} = pa_n + f(n)$（$p$ 为常数，$f(n)$为已知函数），先解齐次部分$a_{n+1}^{(h)} = p a_n^{(h)}$，得 $a_n^{(h)} = C \cdot p^{\thinspace{}n-1}$。然后设特解 $a_n^{(p)} = C_n \cdot p^{\thinspace{}n-1}$，代入原递推确定 $C_n$。

代入得 $C_{n+1} \cdot p^{\thinspace{}n} = p \cdot C_n \cdot p^{\thinspace{}n-1} + f(n) = C_n \cdot p^{\thinspace{}n} + f(n)$，于是：

$$C_{n+1} - C_n = \frac{f(n)}{p^{\thinspace{}n}}$$

累加得 $C_n = C_1 + \sum_{k=1}^{n-1}\frac{f(k)}{p^{\thinspace{}k}}$。通解为 $a_n = C_n \cdot p^{\thinspace{}n-1}$。

常数变易法步骤

1. 写出齐次通解 $a_n^{(h)} = C \cdot p^{\thinspace{}n-1}$
2. 将常数 $C$变为函数$C_n$，代入原递推
3. 得到 $C_n$ 的递推关系，累加求解
4. 利用初值 $a_1$确定$C_1$

例题：$a_1 = 1$，$a_{n+1} = 2a_n + 3^n$，求通项。

齐次通解 $a_n^{(h)} = C \cdot 2^{n-1}$。设 $a_n = C_n \cdot 2^{n-1}$，代入：

$$C_{n+1} \cdot 2^n = 2 \cdot C_n \cdot 2^{n-1} + 3^n = C_n \cdot 2^n + 3^n$$

$$C_{n+1} - C_n = \left(\frac{3}{2}\right)^n$$

$$C_n = C_1 + \sum_{k=1}^{n-1}\left(\frac{3}{2}\right)^k = C_1 + \frac{\frac{3}{2}\left[\left(\frac{3}{2}\right)^{n-1}-1\right]}{\frac{3}{2}-1} = C_1 + 3\left[\left(\frac{3}{2}\right)^{n-1}-1\right]$$

由 $a_1 = 1 = C_1 \cdot 2^0 = C_1$，得 $C_1 = 1$。

$$C_n = 1 + 3\left(\frac{3}{2}\right)^{n-1} - 3 = 3\left(\frac{3}{2}\right)^{n-1} - 2$$

$$a_n = C_n \cdot 2^{n-1} = 3 \cdot 3^{n-1} - 2 \cdot 2^{n-1} = 3^n - 2^n$$

常数变易法 vs 待定系数法

当 $f(n) = q^n$且$q \neq p$时，也可直接设特解$a_n^{(p)} = A \cdot q^n$用待定系数法。但当$q = p$（共振情况）时，需设 $a_n^{(p)} = A \cdot n \cdot p^n$。常数变易法是更通用的方法。

一阶递推的求和法

对于任意递推 $a_{n+1} = f(a_n, n)$，最朴素也最万能的思路是写出相邻两项之差：

$$a_n = a_1 + \sum_{k=1}^{n-1}(a_{k+1} - a_k)$$

核心思想

将递推关系转化为 $a_{k+1} - a_k$ 的表达式，然后通过累加得到通项。这是处理一阶递推的基本思路，也是理解「累加法」的出发点。

累加法与累乘法

累加法：当递推可化为 $a_{n+1} - a_n = f(n)$ 时，直接累加：

$$a_n = a_1 + \sum_{k=1}^{n-1} f(k)$$

常见 $f(n)$ 的求和公式

• $f(n) = n$：$\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}$
• $f(n) = n^2$：$\sum_{k=1}^{n-1} k^2 = \frac{(n-1)n(2n-1)}{6}$
• $f(n) = q^n$（$q \neq 1$）：$\sum_{k=1}^{n-1} q^k = \frac{q(q^{n-1}-1)}{q-1}$
• $f(n) = \frac{1}{n(n+1)}$：$\sum_{k=1}^{n-1} \frac{1}{k(k+1)} = 1 - \frac{1}{n}$

累乘法：当递推可化为 $a_{n+1} = f(n) \cdot a_n$ 时，累乘：

$$a_n = a_1 \prod_{k=1}^{n-1} f(k)$$

常见 $f(n)$ 的累乘公式

• $f(n) = \frac{n}{n+1}$：$a_n = \frac{a_1}{n}$
• $f(n) = \frac{n+1}{n}$：$a_n = a_1 \cdot n$
• $f(n) = q$：$a_n = a_1 \cdot q^{n-1}$（等比数列）
• $f(n) = \frac{n+2}{n}$：$a_n = \frac{a_1 \cdot n(n+1)}{2}$

例题：$a_1 = 1$，$a_{n+1} = a_n + 2n + 1$，求通项。

化为 $a_{n+1} - a_n = 2n + 1$，累加：

$$a_n = 1 + \sum_{k=1}^{n-1}(2k+1) = 1 + 2 \cdot \frac{(n-1)n}{2} + (n-1) = 1 + n(n-1) + n - 1 = n^2$$

例题：$a_1 = 1$，$a_{n+1} = \frac{n}{n+2} \cdot a_n$，求通项。

累乘：$a_n = 1 \cdot \prod_{k=1}^{n-1}\frac{k}{k+2} = \frac{1 \cdot 2 \cdot 3 \cdots (n-1)}{3 \cdot 4 \cdot 5 \cdots (n+1)} = \frac{2}{(n+1)n} = \frac{2}{n(n+1)}$

二阶线性齐次递推

$$a_{n+2} = pa_{n+1} + qa_n$$

特征方程法

设 $a_n = \lambda^n$ 代入，得到特征方程：

$$\lambda^2 - p\lambda - q = 0$$

根据判别式 $\Delta = p^2+4q$ 分三种情况：

三种情况

1. $\Delta > 0$（两相异实根 $\lambda_1 \neq \lambda_2$）： $$a_n = C_1\lambda_1^n + C_2\lambda_2^n$$ 其中 $C_1, C_2$由初值$a_1, a_2$ 确定。

2. $\Delta = 0$（重根 $\lambda_1 = \lambda_2 = \lambda$）： $$a_n = (C_1 + C_2 n)\lambda^n$$

3. $\Delta < 0$（共轭复根 $\lambda = re^{\pm i\theta}$）： $$a_n = r^n(C_1\cos n\theta + C_2\sin n\theta)$$

斐波那契数列（竞赛视角）

斐波那契数列由 $F_1=F_2=1$，$F_{n+2}=F_{n+1}+F_n$ 定义。

特征方程 $\lambda^2-\lambda-1=0$，根为 $\lambda_{1,2}=\frac{1\pm\sqrt{5}}{2}$（黄金比例 $\phi$和$-\phi^{-1}$）。

通项公式（比内公式）： $$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$

竞赛中的斐波那契性质

• $F_1+F_2+\cdots+F_n = F_{n+2}-1$
• $F_1^2+F_2^2+\cdots+F_n^2 = F_nF_{n+1}$
• $\gcd(F_m, F_n) = F_{\gcd(m,n)}$
• $F_{n-1}F_{n+1}-F_n^2 = (-1)^n$（卡西尼恒等式）

二阶线性非齐次递推

形如 $a_{n+2} = p a_{n+1} + q a_n + f(n)$ 的递推，通解 = 齐次通解 + 非齐次特解。

待定系数法

根据 $f(n)$ 的形式设特解：

特解形式对照表

$f(n)$的形式	特解$a_n^{(p)}$ 的形式	条件
多项式 $P_m(n)$（$m$次）	$Q_m(n)$（$m$ 次多项式）	1 不是特征根
多项式 $P_m(n)$	$n \cdot Q_m(n)$	1 是单特征根
多项式 $P_m(n)$	$n^2 \cdot Q_m(n)$	1 是重特征根
$A \cdot r^n$	$B \cdot r^n$	$r$ 不是特征根
$A \cdot r^n$	$B \cdot n \cdot r^n$	$r$ 是单特征根
$A \cdot r^n$	$B \cdot n^2 \cdot r^n$	$r$ 是重特征根
$P_m(n) \cdot r^n$	$Q_m(n) \cdot r^n$	$r$ 不是特征根

其中 $P_m(n)$表示$m$ 次多项式，$Q_m(n)$表示待定系数的$m$ 次多项式。

例题：$a_1 = 0, a_2 = 1$，$a_{n+2} = 5a_{n+1} - 6a_n + 2^n$，求通项。

特征方程 $\lambda^2 - 5\lambda + 6 = 0$，$\lambda_1 = 2, \lambda_2 = 3$。

$f(n) = 2^n$，而 $2$是特征根（单根），故设特解$a_n^{(p)} = A \cdot n \cdot 2^n$。

代入递推： $$A(n+2)2^{n+2} = 5A(n+1)2^{n+1} - 6A n 2^n + 2^n$$

两边除以 $2^n$： $$4A(n+2) = 10A(n+1) - 6An + 1$$ $$4An + 8A = 10An + 10A - 6An + 1$$ $$4An + 8A = 4An + 10A + 1$$ $$8A = 10A + 1 \thickspace\Rightarrow\thickspace -2A = 1 \thickspace\Rightarrow\thickspace A = -\frac{1}{2}$$

特解 $a_n^{(p)} = -\frac{1}{2} n \cdot 2^n = -n \cdot 2^{n-1}$。

齐次通解 $a_n^{(h)} = C_1 \cdot 2^n + C_2 \cdot 3^n$。

通解 $a_n = C_1 \cdot 2^n + C_2 \cdot 3^n - n \cdot 2^{n-1}$。

代入初值： $$\begin{cases} 2C_1 + 3C_2 - 2 = 0 \newline 4C_1 + 9C_2 - 4 = 1 \end{cases}$$

解得 $C_1 = \frac{1}{2}, C_2 = \frac{1}{3}$。

故 $a_n = \frac{1}{2} \cdot 2^n + \frac{1}{3} \cdot 3^n - n \cdot 2^{n-1} = 2^{n-1} + 3^{n-1} - n \cdot 2^{n-1}$。

叠加原理

若 $f(n) = f_1(n) + f_2(n)$，可分别求 $a_{n+2} = p a_{n+1} + q a_n + f_1(n)$和$a_{n+2} = p a_{n+1} + q a_n + f_2(n)$的特解$a_n^{(p1)}$和$a_n^{(p2)}$，则 $a_n^{(p)} = a_n^{(p1)} + a_n^{(p2)}$ 是原方程的特解。

叠加原理

线性递推中，非齐次项可以分解为若干项的和，各子项的特解相加即为原方程的特解。这大大简化了 $f(n)$ 为混合型（如多项式 + 指数）时的求解。

例题：$a_{n+2} = 5a_{n+1} - 6a_n + 4n + 3^n$，求特解形式。

$f(n) = 4n + 3^n$，分解为 $f_1(n) = 4n$和$f_2(n) = 3^n$。

特征根为 $2, 3$。对于 $f_1(n) = 4n$（1 不是特征根），设 $a_n^{(p1)} = An + B$。 对于 $f_2(n) = 3^n$（3 是特征根），设 $a_n^{(p2)} = C \cdot n \cdot 3^n$。

总特解形式：$a_n^{(p)} = An + B + C \cdot n \cdot 3^n$。

高阶线性递推

三阶及以上线性递推的特征方程法

对于 $k$ 阶线性齐次递推：

$$a_{n+k} = c_1 a_{n+k-1} + c_2 a_{n+k-2} + \cdots + c_k a_n$$

特征方程为：

$$\lambda^k - c_1\lambda^{k-1} - c_2\lambda^{k-2} - \cdots - c_k = 0$$

$k$ 阶线性齐次递推的通解结构

设特征方程的 $k$个根为$\lambda_1, \lambda_2, \ldots, \lambda_k$（计重数）：

• 每个单实根 $\lambda$对应通解中的一项$C \cdot \lambda^n$
• 每个 $m$重实根$\lambda$对应通解中的项$(C_1 + C_2 n + \cdots + C_m n^{m-1})\lambda^n$
• 每对共轭复根 $re^{\pm i\theta}$对应$r^n(C_1 \cos n\theta + C_2 \sin n\theta)$
• 通解为以上各项的线性组合，共含 $k$ 个待定常数

例题（Tribonacci 数列）：$T_1 = T_2 = 1, T_3 = 2$，$T_{n+3} = T_{n+2} + T_{n+1} + T_n$，求特征方程。

特征方程 $\lambda^3 - \lambda^2 - \lambda - 1 = 0$。

这是一个三次方程，有一个实根和两个共轭复根。通解形式为：

$$T_n = C_1 \lambda_1^n + C_2 \lambda_2^n + C_3 \lambda_3^n$$

其中 $\lambda_1, \lambda_2, \lambda_3$ 为特征根，$C_1, C_2, C_3$ 由初值确定。

Tribonacci 数列的近似值

特征方程 $\lambda^3 - \lambda^2 - \lambda - 1 = 0$的最大实根约为$\lambda_1 \approx 1.8393$，称为 Tribonacci 常数。$\frac{T_{n+1}}{T_n} \to \lambda_1$。

线性递推的母函数方法

母函数（生成函数）的定义

对于数列 $\lbrace a_n\rbrace _{n=0}^{\infty}$，其普通型母函数（生成函数）定义为形式幂级数：

$$G(x) = \sum_{n=0}^{\infty} a_n x^n$$

母函数的核心思想

将数列的递推关系转化为关于 $G(x)$的函数方程，解出$G(x)$ 的解析表达式，再将其展开为幂级数，$x^n$的系数即为$a_n$。

用母函数求斐波那契数列通项

设 $F_0 = 0, F_1 = 1$，$F_{n+2} = F_{n+1} + F_n$（$n \geq 0$）。母函数 $G(x) = \sum_{n=0}^{\infty} F_n x^n$。

$$\begin{aligned} G(x) &= F_0 + F_1 x + \sum_{n=2}^{\infty} F_n x^n \newline &= x + \sum_{n=0}^{\infty} F_{n+2} x^{n+2} \newline &= x + \sum_{n=0}^{\infty} (F_{n+1} + F_n) x^{n+2} \newline &= x + x\sum_{n=0}^{\infty} F_{n+1} x^{n+1} + x^2\sum_{n=0}^{\infty} F_n x^n \newline &= x + x(G(x) - F_0) + x^2 G(x) \newline &= x + x G(x) + x^2 G(x) \end{aligned}$$

解得 $G(x) = \dfrac{x}{1 - x - x^2}$。

将分母分解：$1 - x - x^2 = (1 - \phi x)(1 - \hat{\phi}x)$，其中 $\phi = \frac{1+\sqrt{5}}{2}$，$\hat{\phi} = \frac{1-\sqrt{5}}{2}$。

部分分式展开：

$$G(x) = \frac{1}{\sqrt{5}}\left(\frac{1}{1-\phi x} - \frac{1}{1-\hat{\phi}x}\right) = \frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}(\phi^n - \hat{\phi}^n)x^n$$

故 $F_n = \frac{1}{\sqrt{5}}(\phi^n - \hat{\phi}^n)$，即比内公式。

用母函数求卡特兰数通项

卡特兰数 $C_n$满足$C_0 = 1$，$C_{n+1} = \sum_{k=0}^{n} C_k C_{n-k}$（$n \geq 0$）。

设母函数 $G(x) = \sum_{n=0}^{\infty} C_n x^n$。

$$G(x)^2 = \sum_{n=0}^{\infty}\left(\sum_{k=0}^{n} C_k C_{n-k}\right)x^n = \sum_{n=0}^{\infty} C_{n+1} x^n = \frac{G(x) - 1}{x}$$

于是 $x G(x)^2 - G(x) + 1 = 0$，解得 $G(x) = \dfrac{1 - \sqrt{1-4x}}{2x}$（取负号以保证 $G(0) = C_0 = 1$）。

利用广义二项式定理展开 $\sqrt{1-4x}$：

$$G(x) = \frac{1}{2x}\left[1 - \sum_{n=0}^{\infty}\binom{1/2}{n}(-4x)^n\right]$$

化简得 $C_n = \frac{1}{n+1}\binom{2n}{n}$。

母函数求递推的一般步骤

1. 设母函数 $G(x) = \sum_{n=0}^{\infty} a_n x^n$
2. 将递推关系两边乘以 $x^n$并对$n$ 求和
3. 利用 $G(x)$ 及其导数/积分表达各项和式
4. 得到关于 $G(x)$的方程，解出$G(x)$
5. 将 $G(x)$展开为幂级数，读出系数$a_n$

例题：$a_0 = 1$，$a_{n+1} = 2a_n + 1$（$n \geq 0$），用母函数求 $a_n$。

设 $G(x) = \sum_{n=0}^{\infty} a_n x^n$。

$$\sum_{n=0}^{\infty} a_{n+1} x^n = 2\sum_{n=0}^{\infty} a_n x^n + \sum_{n=0}^{\infty} x^n$$

左边 $= \frac{G(x) - a_0}{x} = \frac{G(x) - 1}{x}$，右边 $= 2G(x) + \frac{1}{1-x}$。

$$\frac{G(x) - 1}{x} = 2G(x) + \frac{1}{1-x}$$

解得 $G(x) = \frac{1}{(1-x)(1-2x)} = \frac{2}{1-2x} - \frac{1}{1-x}$。

展开：$G(x) = 2\sum_{n=0}^{\infty} 2^n x^n - \sum_{n=0}^{\infty} x^n = \sum_{n=0}^{\infty}(2^{n+1} - 1)x^n$。

故 $a_n = 2^{n+1} - 1$。

分式线性递推：不动点法

对于形如 $a_{n+1} = \dfrac{pa_n+q}{ra_n+s}$ 的递推，考虑不动点方程：

$$x = \frac{px+q}{rx+s}, \quad 即 \quad rx^2 + (s-p)x - q = 0$$

不动点法分类

• 两相异不动点 $\alpha \neq \beta$：令 $b_n = \frac{a_n-\alpha}{a_n-\beta}$，则 $\lbrace b_n\rbrace $ 为等比数列。
• 重不动点 $\alpha = \beta$：令 $b_n = \frac{1}{a_n-\alpha}$，则 $\lbrace b_n\rbrace $ 为等差数列。
• 无实不动点：数列表现为周期数列。

分式线性递推的矩阵表示

将分式线性递推 $a_{n+1} = \dfrac{pa_n + q}{ra_n + s}$与矩阵$M = \begin{pmatrix}p & q \newline r & s\end{pmatrix}$ 对应。

定义作用：若 $a = \dfrac{p x + q}{r x + s}$，则记 $a = M \circ x$。那么：

$$a_n = M^n \circ a_1$$

其中 $M^n$是矩阵的$n$ 次幂。迭代分式线性递推等价于计算矩阵的幂。

矩阵表示的优势

• 矩阵乘法对应于分式线性变换的复合
• 不动点方程 $x = \frac{px+q}{rx+s}$等价于求矩阵$M$ 的特征向量
• 通过矩阵对角化可求 $M^n$，进而得到 $a_n$ 的通项

例题：$a_1 = 2$，$a_{n+1} = \dfrac{3a_n - 2}{a_n}$，用矩阵法求通项。

对应矩阵 $M = \begin{pmatrix}3 & -2 \newline 1 & 0\end{pmatrix}$。

特征方程 $\det(M - \lambda I) = \lambda^2 - 3\lambda + 2 = 0$，$\lambda_1 = 1, \lambda_2 = 2$。

对角化 $M = PDP^{-1}$，其中 $D = \begin{pmatrix}1 & 0 \newline 0 & 2\end{pmatrix}$。

则 $M^n = PD^nP^{-1}$，进而 $a_n = M^n \circ a_1$。

具体计算可得 $a_n = \dfrac{2^{n+1} - 1}{2^n - 1}$。

矩阵法 vs 不动点法

矩阵法本质上将分式线性递推的迭代问题转化为矩阵乘幂问题，与不动点法殊途同归。当不动点较复杂时，矩阵法可能更系统化。

非线性递推的处理

取对数法

当递推形式为 $a_{n+1} = c \cdot a_n^k$ 时，两边取对数： $$\ln a_{n+1} = \ln c + k\ln a_n$$

令 $b_n = \ln a_n$，则 $b_{n+1}=kb_n+\ln c$，化为一阶线性递推。

取倒数法

当递推形式为 $a_{n+1} = \dfrac{a_n}{pa_n+q}$ 时，取倒数： $$\frac{1}{a_{n+1}} = p + \frac{q}{a_n}$$

令 $b_n = \frac{1}{a_n}$，则 $b_{n+1}=qb_n+p$，化为一阶线性递推。

三角换元法

当递推中出现 $a_{n+1} = 2a_n^2-1$型时，联想到$\cos 2\theta = 2\cos^2\theta-1$，令 $a_n = \cos\theta_n$ 可化简。

同理，$a_{n+1} = \frac{2a_n}{1-a_n^2}$联想到$\tan 2\theta = \frac{2\tan\theta}{1-\tan^2\theta}$。

平方型递推

形如 $a_{n+1} = a_n^2 + c$或$a_{n+1} = a_n^2 + b a_n + c$ 的递推。

处理策略

1. 配方：若 $a_{n+1} = a_n^2 + b a_n + c$，尝试配方为 $a_{n+1} + d = (a_n + d)^2$ 的形式
2. 取对数：若可化为 $b_{n+1} = b_n^2$型，则$b_n = b_1^{2^{n-1}}$
3. 三角换元：若出现 $a_{n+1} = 2a_n^2 - 1$型，用$\cos$ 换元

例题：$a_1 = 3$，$a_{n+1} = a_n^2 - 2a_n + 2$，求通项。

配方：$a_{n+1} = (a_n - 1)^2 + 1$，即 $a_{n+1} - 1 = (a_n - 1)^2$。

令 $b_n = a_n - 1$，则 $b_{n+1} = b_n^2$，$b_1 = 2$。

$b_n = 2^{2^{n-1}}$，故 $a_n = 2^{2^{n-1}} + 1$。

有理递推的一般处理策略

对于更复杂的非线性递推 $a_{n+1} = f(a_n)$，一般策略：

处理流程

1. 尝试换元：寻找合适的 $b_n = g(a_n)$ 使递推线性化
2. 尝试取倒数：若 $f$ 是分式形式，取倒数可能简化
3. 尝试取对数：若 $f$ 是乘积/幂形式，取对数
4. 尝试三角换元：若 $f$ 与三角函数恒等式相似
5. 不动点分析：求不动点，通过减去不动点来简化
6. 桥函数法：寻找共轭函数

递推的周期性问题

若递推 $a_{n+1} = f(a_n)$中的函数$f$满足$f^{(T)}(x) = x$（$f$的$T$次迭代为恒等映射），则对任意初值数列为周期为$T$ 的周期数列。

常见的周期递推

• $a_{n+1} = -\dfrac{1}{a_n}$：周期为 2（$a_{n+2} = a_n$）
• $a_{n+1} = \dfrac{1}{1-a_n}$：周期为 3
• $a_{n+1} = \dfrac{a_n-1}{a_n+1}$：周期为 4
• $a_{n+1} = \dfrac{1+a_n}{1-a_n}$：周期为 4

判断周期性的方法

计算 $a_2, a_3, a_4, \ldots$，看是否出现 $a_{n+T} = a_n$。一旦发现周期，即可直接写出所有项。

例题：$a_1 = 2$，$a_{n+1} = \dfrac{1}{1-a_n}$，求 $a_{2024}$。

计算：$a_1 = 2$，$a_2 = \frac{1}{1-2} = -1$，$a_3 = \frac{1}{1-(-1)} = \frac{1}{2}$，$a_4 = \frac{1}{1-\frac{1}{2}} = 2 = a_1$。

周期为 3。$2024 \equiv 2 \pmod{3}$，故 $a_{2024} = a_2 = -1$。

桥函数法

桥函数法（函数迭代法）

如果递推 $a_{n+1} = f(a_n)$中的函数$f$可以通过一个可逆函数$g$与一个简单函数$h$共轭，即$f = g^{-1} \circ h \circ g$，那么： $$a_n = g^{-1}(h^{n-1}(g(a_1)))$$ 其中 $h^{n-1}$表示$h$的$n-1$ 次迭代。

例如：$a_{n+1} = \frac{a_n}{1+a_n}$，取 $g(x)=\frac{1}{x}$，则 $h(x)=x+1$，故 $a_n = \frac{a_1}{1+(n-1)a_1}$。

数列的差分方法

差分算子

定义前向差分算子 $\Delta$：

$$\Delta a_n = a_{n+1} - a_n$$

差分的基本性质

• $\Delta(C) = 0$（常数的差分为零）
• $\Delta(a_n + b_n) = \Delta a_n + \Delta b_n$（线性性）
• $\Delta(a_n b_n) = a_{n+1}\Delta b_n + b_n \Delta a_n$（乘法法则）
• $\Delta\left(\frac{a_n}{b_n}\right) = \frac{b_n \Delta a_n - a_n \Delta b_n}{b_n b_{n+1}}$（除法法则）

高阶差分

递归定义 $k$ 阶差分：

$$\Delta^{k} a_n = \Delta(\Delta^{k-1} a_n) = \sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}a_{n+j}$$

高阶差分的意义

• 若 $\lbrace a_n\rbrace $是$m$次多项式数列，则$\Delta^{m+1} a_n = 0$（对所有 $n$）
• 反之，若 $\Delta^{m+1} a_n = 0$且$\Delta^{m} a_n \neq 0$，则 $a_n$是$m$ 次多项式

差分与递推的关系

递推 $a_{n+1} = f(a_n, n)$ 本质上是用差分方程描述数列。一阶递推可以写成：

$$\Delta a_n = f(a_n, n) - a_n$$

高阶递推可以写成 $\Delta^k a_n = \cdots$ 的形式。

用差分求多项式数列的通项

对于多项式数列，可以利用牛顿前向差分公式：

$$a_n = \sum_{k=0}^{m} \binom{n-1}{k} \Delta^k a_1$$

其中 $\binom{n-1}{k} = \frac{(n-1)(n-2)\cdots(n-k)}{k!}$（$k \geq 1$），$\binom{n-1}{0} = 1$。

例题：已知 $a_1 = 2, a_2 = 7, a_3 = 16, a_4 = 29$，且 $a_n$是$n$ 的二次多项式，求通项。

计算差分： $\Delta a_1 = 5, \Delta a_2 = 9, \Delta a_3 = 13$ $\Delta^2 a_1 = 4, \Delta^2 a_2 = 4$（常数，确认为二次）

$$\begin{aligned} a_n &= a_1 + \binom{n-1}{1}\Delta a_1 + \binom{n-1}{2}\Delta^2 a_1 \newline &= 2 + (n-1) \cdot 5 + \frac{(n-1)(n-2)}{2} \cdot 4 \newline &= 2 + 5n - 5 + 2(n^2 - 3n + 2) \newline &= 2n^2 - n + 1 \end{aligned}$$

数列求和进阶

裂项相消法

将通项 $a_n$写成$a_n = b_{n+1} - b_n$ 的形式，则：

$$\sum_{k=1}^{n} a_k = b_{n+1} - b_1$$

常见裂项公式

• $\frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}$
• $\frac{1}{n(n+1)(n+2)} = \frac{1}{2}\left[\frac{1}{n(n+1)} - \frac{1}{(n+1)(n+2)}\right]$
• $\frac{1}{n(n+k)} = \frac{1}{k}\left(\frac{1}{n} - \frac{1}{n+k}\right)$
• $\frac{1}{\sqrt{n+1}+\sqrt{n}} = \sqrt{n+1} - \sqrt{n}$（分母有理化）
• $n \cdot n! = (n+1)! - n!$

例题：求 $S_n = \sum_{k=1}^{n} \frac{1}{k(k+1)(k+2)}$。

$$\begin{aligned} S_n &= \frac{1}{2}\sum_{k=1}^{n}\left[\frac{1}{k(k+1)} - \frac{1}{(k+1)(k+2)}\right] \newline &= \frac{1}{2}\left[\frac{1}{1 \cdot 2} - \frac{1}{(n+1)(n+2)}\right] \newline &= \frac{1}{4} - \frac{1}{2(n+1)(n+2)} \end{aligned}$$

分组求和

将数列拆分为若干个子数列分别求和，再合并结果。适用于：

• 奇偶项规律不同的数列
• 可拆分为等差 + 等比的形式

例题：求 $S_n = \sum_{k=1}^{n} (2k-1) \cdot 3^{k-1}$。

这是「等差 × 等比」混合型求和。用错位相减法：

$$\begin{aligned} S_n &= 1 \cdot 3^0 + 3 \cdot 3^1 + 5 \cdot 3^2 + \cdots + (2n-1) \cdot 3^{n-1} \newline 3S_n &= \quad\quad\thickspace 1 \cdot 3^1 + 3 \cdot 3^2 + \cdots + (2n-3) \cdot 3^{n-1} + (2n-1) \cdot 3^n \end{aligned}$$

相减：$-2S_n = 1 + 2(3^1 + 3^2 + \cdots + 3^{n-1}) - (2n-1) \cdot 3^n$

$-2S_n = 1 + 2 \cdot \frac{3(3^{n-1}-1)}{2} - (2n-1) \cdot 3^n = 1 + 3^n - 3 - (2n-1) \cdot 3^n$

$S_n = (n-1) \cdot 3^n + 1$。

阿贝尔求和公式（分部求和）

阿贝尔求和公式

设 $A_n = \sum_{k=1}^{n} a_k$，则： $$\sum_{k=1}^{n} a_k b_k = A_n b_n + \sum_{k=1}^{n-1} A_k(b_k - b_{k+1})$$ 这是离散版本的分部积分公式，对应 $\int u dv = uv - \int v du$。

数列不等式

递推数列的不等式证明

对于递推数列，常用以下方法证明不等式：

1. 数学归纳法：直接归纳证明 $a_n \leq M$或$a_n \geq m$
2. 单调性分析：通过 $a_{n+1} - a_n$ 的符号判断单调性
3. 辅助函数法：令 $f(x) = a_{n+1}$的表达式，研究$f(x)$ 的性质

常用技巧：放缩

若 $a_{n+1} = f(a_n)$且$f$单调递增，则给定$a_1$的范围后，可利用$f$ 的单调性逐项放缩。

放缩法证明数列不等式

例题：证明 $\sum_{k=1}^{n} \frac{1}{k^2} < 2$（$n \geq 1$）。

利用 $\frac{1}{k^2} < \frac{1}{k(k-1)} = \frac{1}{k-1} - \frac{1}{k}$（$k \geq 2$）：

$$\sum_{k=1}^{n} \frac{1}{k^2} < 1 + \sum_{k=2}^{n}\left(\frac{1}{k-1} - \frac{1}{k}\right) = 1 + 1 - \frac{1}{n} = 2 - \frac{1}{n} < 2$$

数列的单调性与有界性综合应用

这是判断递推数列收敛的核心方法。结合单调有界定理，常用于求极限。

例题：$a_1 = 1$，$a_{n+1} = \sqrt{3a_n + 4}$，证明数列收敛并求极限。

先证单调递增：$a_2 = \sqrt{7} > 1 = a_1$。若 $a_n > a_{n-1}$，则 $a_{n+1} = \sqrt{3a_n + 4} > \sqrt{3a_{n-1} + 4} = a_n$。归纳得 $\lbrace a_n\rbrace $ 单调递增。

再证有上界：$a_1 = 1 < 4$。若 $a_n < 4$，则 $a_{n+1} = \sqrt{3a_n + 4} < \sqrt{3 \cdot 4 + 4} = 4$。归纳得 $a_n < 4$。

由单调有界定理，数列收敛。设极限 $L$，则 $L = \sqrt{3L + 4}$，$L^2 - 3L - 4 = 0$，$L = 4$（$L = -1$舍去）。故$a_n \to 4$。

数列中的数论问题

递推数列的整除性

对于整数递推数列，常研究其整除性质。

例题：$a_1 = 1, a_2 = 1$，$a_{n+2} = a_{n+1} + 2a_n$，证明对所有 $n$，$a_n$ 为奇数。

归纳法：$a_1 = 1$（奇），$a_2 = 1$（奇）。假设 $a_n$和$a_{n+1}$均为奇数，则$a_{n+2} = a_{n+1} + 2a_n = \text{奇} + \text{偶} = \text{奇}$。故所有 $a_n$ 为奇数。

递推数列的模周期（皮萨诺周期）

皮萨诺周期

斐波那契数列模 $m$的余数序列$\lbrace F_n \bmod m\rbrace $必定是周期数列。其周期长度$\pi(m)$ 称为皮萨诺周期。

• $\pi(2) = 3$：$1,1,0,1,1,0,\ldots$
• $\pi(3) = 8$：$1,1,2,0,2,2,1,0,\ldots$
• $\pi(5) = 20$

一般结论

任何满足常系数线性递推的整数数列，模 $m$后必定最终周期。这是因为模$m$ 的状态空间有限，由鸽巢原理，状态必重复。

例题：求 $F_{2024} \bmod 4$。

斐波那契数列模 4：$1,1,2,3,1,0,1,1,2,3,1,0,\ldots$，周期为 6。

$2024 \equiv 2 \pmod{6}$，故 $F_{2024} \bmod 4 = F_2 \bmod 4 = 1$。

数列与数学归纳法

竞赛中，数学归纳法常用于：

1. 证明递推数列的显式通项公式
2. 证明数列的单调有界性
3. 证明数列不等式的成立

第二数学归纳法

假设命题 $P(1), P(2), \ldots, P(k)$成立，推出$P(k+1)$ 成立。这在处理二阶及以上递推时尤为有用。

数列极限与收敛性

对于递推定义的数列 $a_{n+1}=f(a_n)$，若数列收敛且 $f$连续，则极限$L$满足$L=f(L)$，即 $L$是$f$ 的不动点。

单调有界定理是判断收敛的最常用工具：

• 若数列单调递增且有上界，则收敛
• 若数列单调递减且有下界，则收敛

精选例题

例题 1

题目：求 $a_1=1$，$a_{n+1}=2a_n+3$ 的通项。

解析： 不动点方程 $x=2x+3$，得 $x=-3$。

令 $b_n=a_n+3$，则 $b_{n+1}=a_{n+1}+3=2a_n+6=2(a_n+3)=2b_n$。

故 $b_n=b_1\cdot 2^{n-1}=4\cdot 2^{n-1}=2^{n+1}$。

$a_n=2^{n+1}-3$。

例题 2

题目：求 $a_1=1, a_2=2$，$a_{n+2}=5a_{n+1}-6a_n$ 的通项。

解析： 特征方程 $\lambda^2-5\lambda+6=0$，根为 $\lambda_1=2, \lambda_2=3$。

通项形式：$a_n = C_1 \cdot 2^n + C_2 \cdot 3^n$。

代入初值： $$\begin{cases} 2C_1+3C_2=1 \newline 4C_1+9C_2=2 \end{cases}$$

解得 $C_1=\frac{1}{2}, C_2=0$。

故 $a_n = \frac{1}{2} \cdot 2^n = 2^{n-1}$。

例题 3

题目（斐波那契通项推导）：$F_1=F_2=1$，$F_{n+2}=F_{n+1}+F_n$，求通项公式。

解析： 特征方程 $\lambda^2-\lambda-1=0$，$\lambda_{1,2}=\frac{1\pm\sqrt{5}}{2}$。

通项 $F_n=C_1\lambda_1^n + C_2\lambda_2^n$，代入 $n=1,2$：

$$\begin{cases} C_1\lambda_1 + C_2\lambda_2 = 1 \newline C_1\lambda_1^2 + C_2\lambda_2^2 = 1 \end{cases}$$

利用 $\lambda_i^2=\lambda_i+1$（由特征方程），两式相减： $C_1(\lambda_1^2-\lambda_1)+C_2(\lambda_2^2-\lambda_2)=0$，即 $C_1 \cdot 1 + C_2 \cdot 1 = 0$，$C_1=-C_2$。

代入第一式：$C_1(\lambda_1-\lambda_2)=1$，$\lambda_1-\lambda_2=\sqrt{5}$，故 $C_1=\frac{1}{\sqrt{5}}, C_2=-\frac{1}{\sqrt{5}}$。

$$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$

例题 4

题目：$a_1=2$，$a_{n+1}=\dfrac{a_n+2}{2a_n+1}$，求通项。

解析： 不动点方程 $x=\frac{x+2}{2x+1}$，即 $2x^2+x=x+2$，$x^2=1$，$x=\pm 1$。

两相异不动点，令 $b_n = \frac{a_n-1}{a_n+1}$。

$$b_{n+1} = \frac{\frac{a_n+2}{2a_n+1}-1}{\frac{a_n+2}{2a_n+1}+1} = \frac{(a_n+2)-(2a_n+1)}{(a_n+2)+(2a_n+1)} = \frac{1-a_n}{3a_n+3} = -\frac{1}{3}\cdot\frac{a_n-1}{a_n+1} = -\frac{1}{3}b_n$$

故 $\lbrace b_n\rbrace $是公比$-\frac{1}{3}$ 的等比数列。

$b_1 = \frac{2-1}{2+1} = \frac{1}{3}$，$b_n = \frac{1}{3}(-\frac{1}{3})^{n-1}$。

由 $b_n = \frac{a_n-1}{a_n+1}$解出$a_n = \frac{1+b_n}{1-b_n}$。

例题 5

题目：$a_1=1$，$a_{n+1} = a_n^2 + 2a_n$，求 $a_n$。

解析： 观察 $a_{n+1}+1 = a_n^2+2a_n+1 = (a_n+1)^2$。

令 $b_n = a_n+1$，则 $b_{n+1}=b_n^2$，$b_1=2$。

故 $b_n = b_1^{2^{n-1}} = 2^{2^{n-1}}$。

$a_n = 2^{2^{n-1}}-1$。

遇到 $a_{n+1} = a_n^2 + 2a_n$型，联想到$(a_n+1)^2$ 展开。

例题 6

题目：$a_1=\sqrt{2}$，$a_{n+1}=\sqrt{2+a_n}$，判断数列收敛性并求极限。

解析： 先证单调性。$a_2 = \sqrt{2+\sqrt{2}} > \sqrt{2} = a_1$。假设 $a_n > a_{n-1}$，则 $a_{n+1}=\sqrt{2+a_n} > \sqrt{2+a_{n-1}}=a_n$。由归纳法，$\lbrace a_n\rbrace $ 单调递增。

再证有界性。$a_1=\sqrt{2}<2$。若 $a_n<2$，则 $a_{n+1}=\sqrt{2+a_n}<\sqrt{2+2}=2$。由归纳法，$a_n<2$对所有$n$ 成立。

由单调有界定理，数列收敛。设极限为 $L$，则 $L=\sqrt{2+L}$，$L^2-L-2=0$，$L=2$或$L=-1$（舍去负值）。故 $a_n \to 2$。

例题 7

题目：$a_1 = 1$，$a_{n+1} = 3a_n + 2n - 1$，求通项。

解析： 齐次通解 $a_n^{(h)} = C \cdot 3^{n-1}$。$f(n) = 2n-1$是一次多项式，1 不是特征根（特征根为 3），设特解$a_n^{(p)} = An + B$。

代入：$A(n+1) + B = 3(An + B) + 2n - 1$

$An + A + B = 3An + 3B + 2n - 1$

比较系数：$A = 3A + 2 \Rightarrow A = -1$；$A + B = 3B - 1 \Rightarrow -1 + B = 3B - 1 \Rightarrow B = 0$。

特解 $a_n^{(p)} = -n$。齐次通解 $a_n^{(h)} = C \cdot 3^{n-1}$。

通解 $a_n = C \cdot 3^{n-1} - n$。代入 $a_1 = 1$：$C \cdot 3^0 - 1 = 1 \Rightarrow C = 2$。

故 $a_n = 2 \cdot 3^{n-1} - n$。

例题 8

题目：$a_1 = 2$，$a_{n+1} = \dfrac{2a_n + 3}{a_n}$，求通项。

解析： 不动点方程 $x = \frac{2x+3}{x}$，即 $x^2 = 2x + 3$，$x^2 - 2x - 3 = 0$，$x = 3$或$x = -1$。

两相异不动点，令 $b_n = \dfrac{a_n - 3}{a_n + 1}$。

$$b_{n+1} = \frac{\frac{2a_n+3}{a_n} - 3}{\frac{2a_n+3}{a_n} + 1} = \frac{2a_n+3 - 3a_n}{2a_n+3 + a_n} = \frac{3 - a_n}{3a_n + 3} = -\frac{1}{3} \cdot \frac{a_n - 3}{a_n + 1} = -\frac{1}{3}b_n$$

$b_1 = \frac{2-3}{2+1} = -\frac{1}{3}$，$b_n = -\frac{1}{3} \cdot \left(-\frac{1}{3}\right)^{n-1} = \left(-\frac{1}{3}\right)^n$。

由 $b_n = \frac{a_n - 3}{a_n + 1}$解出$a_n = \dfrac{3 + b_n}{1 - b_n} = \dfrac{3 + (-\frac{1}{3})^n}{1 - (-\frac{1}{3})^n}$。

例题 9

题目：$a_1 = 1$，$a_{n+1} = a_n + \dfrac{1}{a_n}$，证明 $a_n \to \infty$并估计$a_n$ 的增长速度。

解析： 首先，$a_{n+1}^2 = a_n^2 + 2 + \dfrac{1}{a_n^2} > a_n^2 + 2$。

累加：$a_n^2 > a_1^2 + 2(n-1) = 2n - 1$，故 $a_n > \sqrt{2n-1}$。

另一方面，$a_{n+1}^2 = a_n^2 + 2 + \dfrac{1}{a_n^2} < a_n^2 + 2 + \dfrac{1}{2n-1}$（当 $n$ 较大时）。

$a_n^2 < 1 + 2(n-1) + \sum_{k=1}^{n-1}\frac{1}{2k-1} \approx 2n + \frac{1}{2}\ln n$。

故 $a_n \sim \sqrt{2n}$（$n \to \infty$），且 $a_n \to \infty$。

此类递推的估计技巧

将递推两边平方，将 $a_{n+1} - a_n$转化为$a_{n+1}^2 - a_n^2$ 的形式，再用累加和放缩。

例题 10

题目：$a_1 = 0, a_2 = 1$，$a_{n+2} = a_{n+1} + a_n + n$，求通项。

解析： 齐次特征方程 $\lambda^2 - \lambda - 1 = 0$，特征根 $\lambda_{1,2} = \frac{1 \pm \sqrt{5}}{2}$。

齐次通解 $a_n^{(h)} = C_1 \lambda_1^n + C_2 \lambda_2^n$。

$f(n) = n$（一次多项式），1 不是特征根，设特解 $a_n^{(p)} = An + B$。

代入：$A(n+2) + B = A(n+1) + B + An + B + n$

$An + 2A + B = An + A + B + An + B + n = 2An + A + 2B + n$

比较系数：$A = 2A + 1 \Rightarrow A = -1$；$2A + B = A + 2B \Rightarrow -2 + B = -1 + 2B \Rightarrow B = -1$。

特解 $a_n^{(p)} = -n - 1$。

通解 $a_n = C_1 \lambda_1^n + C_2 \lambda_2^n - n - 1$。

代入初值： $$\begin{cases} C_1\lambda_1 + C_2\lambda_2 - 2 = 0 \newline C_1\lambda_1^2 + C_2\lambda_2^2 - 3 = 1 \end{cases}$$

利用 $\lambda_i^2 = \lambda_i + 1$，第二式化为 $C_1(\lambda_1+1) + C_2(\lambda_2+1) - 3 = 1$，即 $(C_1\lambda_1 + C_2\lambda_2) + (C_1 + C_2) = 4$。

由第一式 $C_1\lambda_1 + C_2\lambda_2 = 2$，故 $C_1 + C_2 = 2$。

又 $\lambda_1 - \lambda_2 = \sqrt{5}$，解方程组得 $C_1 = \frac{1+\sqrt{5}}{2}, C_2 = \frac{1-\sqrt{5}}{2}$。

注意到 $\lambda_1 = \frac{1+\sqrt{5}}{2}$，$\lambda_2 = \frac{1-\sqrt{5}}{2}$，故 $a_n = \lambda_1^{n+1} + \lambda_2^{n+1} - n - 1$。

用斐波那契数表示：$a_n = F_{n+2} + F_n - n - 1$。

例题 11

题目：$a_1 = 1$，$a_{n+1} = \dfrac{3a_n - 1}{a_n + 1}$，求通项。

解析： 不动点方程 $x = \frac{3x-1}{x+1}$，$x^2 + x = 3x - 1$，$x^2 - 2x + 1 = 0$，$(x-1)^2 = 0$，重不动点 $x = 1$。

注意

$a_1 = 1$恰为不动点，此时$a_n = 1$对所有$n$ 成立。当初值恰为不动点时，数列为常数列，不动点法中的换元无效，需单独处理。

例题 12

题目：$a_1 = \sqrt{3}$，$a_{n+1} = \sqrt{a_n^2 + a_n + 1}$，求 $\lim\limits_{n \to \infty} \dfrac{a_n}{n}$。

解析： 先分析 $a_n$ 的增长。$a_{n+1}^2 = a_n^2 + a_n + 1$。

$a_{n+1}^2 - a_n^2 = a_n + 1$。

累加：$a_n^2 = a_1^2 + \sum_{k=1}^{n-1}(a_k + 1) = 3 + (n-1) + \sum_{k=1}^{n-1} a_k$。

由于 $a_n$单调递增且趋于无穷，当$n$ 很大时，$a_n^2 \sim n + \sum_{k=1}^{n-1} a_k$。

由 Stolz 定理：$\lim\limits_{n \to \infty} \frac{a_n}{n} = \lim\limits_{n \to \infty} (a_{n+1} - a_n)$。

而 $a_{n+1} - a_n = \sqrt{a_n^2 + a_n + 1} - a_n = \frac{a_n + 1}{\sqrt{a_n^2 + a_n + 1} + a_n} \to \frac{1}{2}$。

故 $\lim\limits_{n \to \infty} \frac{a_n}{n} = \frac{1}{2}$。

例题 13

题目：$a_1 = 2$，$a_{n+1} = \dfrac{a_n^2 + 2}{2a_n}$，求 $\lim\limits_{n \to \infty} a_n$。

解析： 观察递推形式：$a_{n+1} = \frac{1}{2}\left(a_n + \frac{2}{a_n}\right)$，这是求 $\sqrt{2}$ 的牛顿迭代公式。

首先证明 $a_n > \sqrt{2}$（$n \geq 2$）：由均值不等式，$a_{n+1} = \frac{1}{2}(a_n + \frac{2}{a_n}) \geq \sqrt{a_n \cdot \frac{2}{a_n}} = \sqrt{2}$。等号成立当且仅当 $a_n = \sqrt{2}$。

$a_2 = \frac{4+2}{4} = \frac{3}{2} > \sqrt{2}$。

再证单调递减：$a_{n+1} - a_n = \frac{1}{2}(\frac{2}{a_n} - a_n) = \frac{2 - a_n^2}{2a_n} < 0$（当 $a_n > \sqrt{2}$）。

故数列单调递减有下界，收敛。设极限 $L$，则 $L = \frac{1}{2}(L + \frac{2}{L})$，$L^2 = 2$，$L = \sqrt{2}$。

牛顿迭代

形如 $a_{n+1} = \frac{1}{2}(a_n + \frac{c}{a_n})$的递推是求$\sqrt{c}$ 的牛顿迭代，收敛速度极快（二次收敛）。

例题 14

题目：$a_1 = 1$，$a_{n+1} = a_n + \dfrac{1}{n(n+1)}a_n$，求 $\lim\limits_{n \to \infty} a_n$。

解析： 递推可写为 $a_{n+1} = \left(1 + \frac{1}{n(n+1)}\right)a_n = \frac{n(n+1)+1}{n(n+1)}a_n = \frac{n^2+n+1}{n(n+1)}a_n$。

累乘：$a_n = a_1 \prod_{k=1}^{n-1} \frac{k^2+k+1}{k(k+1)} = \prod_{k=1}^{n-1} \frac{k^2+k+1}{k(k+1)}$。

$\frac{a_{n+1}}{a_n} = 1 + \frac{1}{n(n+1)} > 1$，故 $a_n$ 单调递增。

$\ln a_n = \sum_{k=1}^{n-1} \ln\left(1 + \frac{1}{k(k+1)}\right) \leq \sum_{k=1}^{n-1} \frac{1}{k(k+1)} = 1 - \frac{1}{n} < 1$。

故 $a_n < e$，单调递增有上界，收敛。极限存在，设为 $L$。

利用 $\frac{k^2+k+1}{k(k+1)} = \frac{(k^3-1)/(k-1)}{k(k+1)} = \frac{k^3-1}{(k-1)k(k+1)}$（$k \neq 1$），可计算部分积。计算可得 $L = 2$。

公式速查表

递推类型	标准形式	核心方法
一阶线性	$a_{n+1}=pa_n+q$	不动点 + 等比化
二阶线性齐次	$a_{n+2}=pa_{n+1}+qa_n$	特征方程
分式线性	$a_{n+1}=\frac{pa_n+q}{ra_n+s}$	不动点法
乘积型非线性	$a_{n+1}=c\cdot a_n^k$	取对数
倒数型非线性	$a_{n+1}=\frac{a_n}{pa_n+q}$	取倒数
共轭型	$a_{n+1}=f(a_n)$	桥函数法

相关链接

• 数列与微分方程核心方法
• 迭代与函数方程
• 数学归纳法
• 求和式的计算方式
• 求积式的计算方式
• 斐波那契数列的通项公式推导
• 矩阵与线性代数初步 — 线性递推 $\vec{v}_{n+1}=A\vec{v}_n$ 的矩阵对角化求解
• 对称多项式与牛顿恒等式深化 — Newton 恒等式将递推数列的幂和与对称多项式联系起来
• 特殊数列的数论性质 — Fibonacci、Lucas 数列的整除性与 Pisano 周期
• 连分数与丢番图逼近 — 二阶递推与连分数渐近分数的紧密联系