概念

递推关系

把复杂计数问题转化为数列满足的递推式，用特征方程或母函数求解，斐波那契数列与卡塔兰数都是经典例子。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

递推关系组合数学

01定义

递推关系把计数问题转化为数列满足的方程：斐波那契数列由「前两项之和」生成，卡塔兰数由卷积型递推刻画。特征方程解线性递推，生成函数解一切递推——离散世界的「微分方程」。

斐波那契数列：递推生成，比值收敛于黄金比例

按「最后一步的选择」分类：楼梯走法 $a_n=a_{n-1}+a_{n-2}$ 、二叉树计数 $C_n=\sum C_iC_{n-1-i}$ ——结构分解直接写出方程。

线性递推 $a_n=c_1a_{n-1}+c_2a_{n-2}$ 的解是特征根幂次的线性组合；斐波那契通项含 $\varphi^n$ ，指数增长率由主根决定。

递推两边乘 $x^n$ 求和即得生成函数方程，解出封闭形式再读系数——比特征根法更通用，能处理非线性与卷积型递推。

F_n=\frac{\varphi^n-\psi^n}{\sqrt{5}},\ \ \varphi=\frac{1+\sqrt{5}}{2}

C_n=\frac{1}{n+1}\binom{2n}{n}\ (\text{卡塔兰数})

斐波那契《算盘书》（1202）以兔子问题引入该数列；棣莫弗 1730 年发明特征根法；生成函数路线由欧拉与拉普拉斯在 18 世纪发展成熟。

算法复杂度分析（动态规划状态数）、金融的复利与年金模型、种群动态的离散模型——递推是离散系统演化的通用语言。

汉诺塔：H(n) = 2·H(n−1) + 1 = 2ⁿ − 1每加一片圆盘，移动步数翻倍再加一

n 圆盘数5