数学大学
母函数与递推关系
组合数学 · 初识母函数
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
母函数与递推关系
组合数学 · 初识母函数
母函数能做什么
母函数把数列装进多项式：系数就是数列项，乘法对应组合运算。
定义
数列 a₀,a₁,… 对应 G(x)=Σaₖxᵏ
威力
递推关系变成代数方程，解出再展开
Hanoi问题（1）
汉诺塔移动次数的递推：先移 n−1 层，移最大盘，再移 n−1 层。
递推建立
aₙ = 2aₙ₋₁ + 1，a₁ = 1
直觉
把上面 n−1 层当整体，三次搬运完成
Hanoi问题（2）
用母函数解汉诺塔递推：aₙ = 2ⁿ − 1，指数爆炸一目了然。
解出通项
递推对应 G(x)=(1+x)/(1−2x) 型
结论
64 层汉诺塔需要 2⁶⁴−1 次移动
偶数个5怎样算
「偶数个 5」类计数：按末位分类建立递推，或直接用母函数系数。
分类递推
按新增数位是否为 5 分两类互推
母函数视角
奇偶两态对应 (1+x) 与 (1−x) 结构
偶数个5怎样算（2）
偶数个 5 的 n 位数通式：(10ⁿ+8ⁿ)/2，母函数一展开就有。
通式
aₙ = (10ⁿ + 8ⁿ) / 2
直观验证
n=1 时无 5 的 9 个数与公式吻合
母函数小结
母函数方法四步：立递推、写母函数、解代数方程、展开读系数。
四步流程
递推→母函数→解方程→系数回读
适用边界
线性递推最顺手，组合计数也好用
本节要点
- ✓母函数：数列装进多项式，系数即项
- ✓Hanoi：aₙ=2aₙ₋₁+1 的解是 2ⁿ−1
- ✓偶数个 5：(10ⁿ+8ⁿ)/2
- ✓四步流程：递推→母函数→解→展开
延伸主题：用母函数重解一个旧递推算一算 64 层汉诺塔的量级
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1母函数为什么能把递推变成代数方程？
参考答案递推关系（如 aₙ=2aₙ₋₁+1）两边乘 xⁿ 求和后，左端是母函数 G(x)，右端的移位求和正好是 2xG(x) 加已知项——递推里的「移位」被 x 的幂次编码，递推方程就成了 G(x) 的代数方程。
264 层汉诺塔 2⁶⁴−1 次移动，这个数大到什么程度？
参考答案约 1.8×10¹⁹。即使每秒移一次，也要五千多亿年——远超宇宙年龄。指数增长的速度让「可行的递推」与「可行的任务」完全是两回事。
3母函数方法中「展开回读系数」为什么可靠？
参考答案母函数的幂级数展开唯一：同一函数只有一种系数排列。解代数方程得到的函数若与正确母函数相等，其展开系数必然逐一等于数列项——等式保证了逐项正确。