奥数专题 · 专题五：递推与数列

递

专题五：递推与数列

Recurrence & Sequences · 一个管着一个

爬楼梯不用真爬上去数——问一句"最后一步怎么上来的"，答案自己就冒出来了。递推的美，就是把"一大堆"变成"再走一步"。

卡必背公式 / 记忆口诀

等差/等比基础

特征方程法解线性递推

不动点法解非线性递推

口诀：递推核心——找规律、建关系

这一节在六专题里的位置：上节不等式靠放缩，这节靠"一步步长出来"。递推就是动态规划的祖宗，递归算法、斐波那契、分治全从这里发芽。

这节要学：找递推式 → 初始值 → 特征方程 → 通项/递推估计

递是什么：先抓相邻两项的关系

数列就是一队排好的数，递推是找到"队长怎么管住队员"的规矩。斐波那契：1,1,2,3,5,8… 从第三项起每项 = 前两项之和，别背数字，背规矩 Fₙ = Fₙ₋₁ + Fₙ₋₂。竞赛常考：特征方程法、构造等比、错位相减、裂项求和、数学归纳法。

路考点心法：看到「专题五：递推与数列」先想什么

• 题型识别：先看是数论/组合/几何/不等式/函数方程哪类——不同类型有不同套路

• 方法选择：抽屉原理/染色法/反证法/构造法/不变量——奥数就这几把刷子

• 别忘验证：竞赛题有陷阱——算出答案要检查边界条件

想怎么想到的：永远先问"最后一步"

问"爬 n 阶多少种方法"，别从第一阶往上想——问：最后一步怎么走？要么从第 n−1 阶跨一步，要么从第 n−2 阶跨两步。递推式就这么"问"出来的。递推式一立，剩下就是体力活：齐次的上特征方程，带常数的凑等比。

核心方法三招

找方法一：从"最后一步"倒推

把 f(n) 用 f(n−1)、f(n−2) 表示出来——这是立递推式的唯一动作。大问题拆成小问题，递归到底。

征方法二：特征方程法

线性递推 aₙ = p·aₙ₋₁ + q·aₙ₋₂，把 aₙ 换成 rⁿ，解 r² = pr + q。两不同根 r₁、r₂ 时通项 = $A\cdot r_1^n + B\cdot r_2^n$，再用前两项定 A、B。递推问题降级成解二次方程。

构方法三：构造等比数列

aₙ₊₁ = 2aₙ + 1 这种"带常数"的，两边加 c 凑成 aₙ₊₁ + c = 2(aₙ + c)，比系数解出 c，新数列直接套等比公式。

经典例题

先审题憋三分钟，再点开看完整过程。

例1. 爬楼梯每次 1 阶或 2 阶，爬上第 n 阶有多少种方法？（爬 10 阶呢？）

审题：最后一步只可能跨 1 阶或 2 阶。

思路：两类情况相加立递推式。

逐步解法：设 f(n) 为方法数，则 f(n) = f(n−1) + f(n−2)。初始 f(1)=1，f(2)=2。递推：f(3)=3, f(4)=5, f(5)=8, f(6)=13, f(7)=21, f(8)=34, f(9)=55, f(10)=89。

答案：f(n) = f(n−1)+f(n−2)；10 阶共 89 种

【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到本页"是什么"和例题区，把卡住的那步再推一遍。

例2. 斐波那契 F₁=F₂=1，Fₙ=Fₙ₋₁+Fₙ₋₂，用特征方程法求通项。（比内公式）

审题：标准二阶线性递推。

思路：设 Fₙ = rⁿ，解特征方程。

逐步解法：代入得 r² = r + 1，即 r² − r − 1 = 0。两根 φ = (1+√5)/2，ψ = (1−√5)/2。通解 Fₙ = Aφⁿ + Bψⁿ，用 F₁=F₂=1 定出 A = 1/√5、B = −1/√5，得 $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$。

答案：比内公式 Fₙ = [((1+√5)/2)ⁿ − ((1−√5)/2)ⁿ] / √5

【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到本页"是什么"和例题区，把卡住的那步再推一遍。

例3. 已知 a₁ = 1，aₙ₊₁ = 2aₙ + 1，求通项 aₙ。（构造等比数列）

审题：递推带常数 +1，直接求不行。

思路：两边加 c 凑等比。

逐步解法：设 aₙ₊₁ + c = 2(aₙ + c)，展开对比原式得 2c = 1 + c ⇒ c = 1。故 bₙ = aₙ + 1 是公比 2 的等比数列，b₁ = a₁+1 = 2，bₙ = 2·2ⁿ⁻¹ = 2ⁿ，还回去得 $a_n = 2^n - 1$。验算：a₂=3、a₃=7，全部吻合。

答案：aₙ = 2ⁿ − 1

【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到本页"是什么"和例题区，把卡住的那步再推一遍。

用用途与案例

现实里：银行复利就是递推 aₙ₊₁ = (1+r)aₙ；种群数量预测、传染病模型都是它。编程里：动态规划的本质就是"填表解递推式"——你刷的每道 DP 题，骨子里都是斐波那契的徒子徒孙。

延延展：往楼上走一步

递推往上是生成函数（把整串数列装进一个多项式），再往上和常微分方程遥遥相对——微分方程是"连续版的递推"。斐波那契数列还和黄金分割、向日葵花盘的螺旋数、钢琴 12 平均律都有瓜葛。

防坑警示

坑一：初始值搞错。f(1)=1、f(2)=2 还是 f(0)=1、f(1)=1？差一位整条链全错。怎么改：递推式立完，先把前 3 项手算出来核对。

坑二：特征方程重根乱用公式。r₁ = r₂ 时通项不是 A·rⁿ + B·rⁿ（合并就完了），而是 (A + Bn)·rⁿ。为什么错：重根少了一个自由度，要乘个 n 补回来。

奥数思维点拨 · 递推

突破口：找到相邻项之间的关系，然后解这个关系。递推题第一步永远不是写公式，是问"最后一步怎么来的"。递推式一立，剩下就是解方程的体力活。

费曼学习法：讲给别人听

① 用自己的话讲：递推就是"别想整个过程，只想最后一步"：爬楼梯 n 级 = 先 n-1 级再跨一步 + 先 n-2 级跨两步。

② 举个反例（什么条件下不成立）：不是所有递推都有闭式——特征方程只对线性常系数好用；初始值给错就全盘皆错。

③ 哪里还说不清：特征根重根时为什么要乘 n？

记

本专题小结

① 问"最后一步"立递推式。② 齐次上特征方程，带常数凑等比。③ 初始值手算核对。

费曼学习法

合上书，给一个完全不懂的人讲清楚「专题五：递推与数列」——说不清楚的地方就是你没真懂的。

证专题五：递推与数列的关键定理与公式

核心性质：① 二阶线性递推的特征方程法：若 $a_{n+2} = p\,a_{n+1} + q\,a_n$，则解的特征方程为 $x^2 - px - q = 0$；两根 $x_1 \ne x_2$ 时 $a_n = A x_1^{\,n} + B x_2^{\,n}$，重根 $x_0$ 时 $a_n = (A+Bn)x_0^{\,n}$。
② 单调有界准则：单调且有界的实数列必收敛。
③ 错位相减法：形如 $\sum (an+b)r^n$ 的"等差 $\times$ 等比"求和，两边同乘公比再相减。
④ 裂项相消：$\frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}$，求和时中间项全部抵消，只剩首尾。

推导（不跳步）：以斐波那契 $F_{n+2} = F_{n+1} + F_n$（$F_0=0,F_1=1$）求通项为例——① 猜解形如 $F_n = x^n$，代入递推得 $x^{n+2} = x^{n+1} + x^n$。② 约去 $x^n$（$x \ne 0$）得 $x^2 = x + 1$，即特征方程 $x^2 - x - 1 = 0$。③ 解得两根 $x_1 = \frac{1+\sqrt{5}}{2}$、$x_2 = \frac{1-\sqrt{5}}{2}$。④ 两根不同，故通解为 $F_n = A x_1^{\,n} + B x_2^{\,n}$；代入初值 $F_0=0$ 得 $A+B=0$，代入 $F_1=1$ 得 $Ax_1+Bx_2=1$。⑤ 解得 $A = \frac{1}{\sqrt{5}}$、$B = -\frac{1}{\sqrt{5}}$，于是 $F_n = \frac{1}{\sqrt{5}}\Big[\big(\frac{1+\sqrt{5}}{2}\big)^{n} - \big(\frac{1-\sqrt{5}}{2}\big)^{n}\Big]$——这就是斐波那契的显式公式（比内公式）。

直觉把握：特征方程法的核心是"猜一个会自己复制自己的形状"——指数函数 $x^n$ 乘一次就多一个 $x$，正好对上递推的"往前挪一格"。两个根给两种基本形状，通解就是它们的加权组合，权重由开头两项决定。凡是"下一项由前几项决定"，先写特征方程。

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

【审题】一阶线性递推带常数项——标准动作是"凑成一个等比数列"。

逐步：① 设 $a_{n+1} + c = 2(a_n + c)$，展开对比原式 $a_{n+1} = 2a_n + c$，需 $c = 1$。② 于是 $\{a_n + 1\}$ 是公比为 $2$ 的等比数列。③ 首项 $a_1 + 1 = 2$，故 $a_n + 1 = 2\cdot 2^{n-1} = 2^{n}$。④ 答案：$a_n = 2^{n} - 1$。验证：$n=1$ 时 $1$；$a_{n+1} = 2^{n+1}-1 = 2(2^{n}-1)+1$，成立。
现代应用：把常数 $1$ 换成 $n$，就得到归并排序的复杂度递推 $T(n) = 2T(\frac{n}{2}) + n$，解出来是 $O(n\log n)$。算法复杂度的主定理，就是这套递推解法的工业版。

例题：求 $S_n = \sum_{k=1}^{n} \frac{1}{k(k+1)}$，并求 $\lim_{n\to\infty} S_n$

【审题】每一项都是两个相邻整数相乘的倒数——裂项相消的标准形状。

逐步：① 先裂项：$\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$（通分验证：$\frac{k+1-k}{k(k+1)} = \frac{1}{k(k+1)}$）。② 展开求和：$S_n = (1-\frac{1}{2}) + (\frac{1}{2}-\frac{1}{3}) + \cdots + (\frac{1}{n}-\frac{1}{n+1})$。③ 中间项一减一加全消掉，只剩首尾：$S_n = 1 - \frac{1}{n+1} = \frac{n}{n+1}$。④ 令 $n\to\infty$，$\frac{1}{n+1}\to 0$，得极限为 $1$。⑤ 答案：$S_n = \frac{n}{n+1}$，极限为 $1$。
现代应用：裂项相消就是前缀和与差分数组的思想原型——把逐项相加变成只算端点，是算法里把 $O(n)$ 查询压到 $O(1)$ 的经典手法；信号处理里的积分器与微分器互为逆运算，也是同一件事。

例题：设 $a_1 = 1$，$a_{n+1} = \sqrt{2 + a_n}$，证明 $\{a_n\}$ 收敛并求其极限

【审题】递推式给的是"后一项由前一项算出来"，要证收敛——单调有界准则出场。

逐步：① 先猜极限：若收敛到 $L$，则 $L = \sqrt{2+L}$，即 $L^2 - L - 2 = 0$，解得 $L=2$（舍去负根 $-1$，因为各项为正）。② 证有界：用归纳法，$a_1=1<2$；若 $a_n < 2$，则 $a_{n+1} = \sqrt{2+a_n} < \sqrt{4} = 2$，故全部 $<2$。③ 证单调递增：$a_{n+1} - a_n = \sqrt{2+a_n} - a_n$，因 $a_n<2$ 时 $2+a_n > a_n^2$（即 $(a_n-2)(a_n+1)<0$ 成立），故 $\sqrt{2+a_n} > a_n$，数列递增。④ 单调递增且有上界 $2$，由单调有界准则必收敛，极限只能是 $2$。⑤ 答案：收敛于 $2$。
现代应用："单调有界 ⇒ 收敛"正是迭代算法收敛性证明的模板——梯度下降要证损失单调下降且有下界，EM 算法要证似然单调上升且有上界，思路完全一样。

④ 用途与案例

工程：专题五：递推与数列

在工程、物理、计算机、金融等领域，专题五：递推与数列是基础工具——理解"使用场景"比死记公式重要。

日常：你见过但没注意的专题五：递推与数列

生活中处处有专题五：递推与数列——价格波动、几何造型、统计图表、游戏设计——只不过没人告诉你这就是数学。