递归问题
河内塔
递归式
[f_n = 2 f_{n - 1} + 1
]
封闭形式
[f_n = 2^n - 1
]
- 证明
(f_1 = 1) 成立，考虑 (f_{n - 1}) 成立 (f_n = 2 (2^{n - 1} - 1) + 1 = 2^n - 1)
平面上的直线
用 (n) 个直线最多划分出多少部分
递归式
考虑新加入一条直线，如果和前面的直线有交点，则会新分一个平面，只需要让新加入的直线不和任何一条已有直线平行即可
[f_n = f_{n - 1} + n
]
封闭形式
考虑从 (f_0) 一直加到 (f_n)
[f_n = f_0 + 1 + 2 + ... + n = 1 + frac {(1 + n) n} 2
]
考虑用数学归纳法证明
[f_n = f_{n - 1} + n = 1 + n + frac{n ^ 2 - n} 2 = 1 + frac{n ^ 2 + n} 2
]
约瑟夫问题
一个 (1) 到 (n) 环，每隔一个数删去一个（删除从第二个数开始删），最后剩下哪个数？
递归式
首先考虑 (2n) 是偶数，发现删除一圈后，所有偶数都被删除了 ((2,4,6,...,2n))
剩下的每个数可以看做一个 (n) 的环，每个数乘 2 减 1
那么我们知道了
[f_{2n} = 2f_n - 1
]
再考虑 (2n + 1) 是奇数，相当于转了一圈后，把 1 也删除了
剩下的每个数可以看做一个 (n) 的环，每个数乘 2 加 1
[f_{2n + 1} = 2f_n + 1
]
封闭形式
找到 (n) 的最高次幂 (2^m)
可以发现所有最高次幂是 (2^m) 的结果都是从最高次幂为 (2^{m - 1}) 的情况下得到的
经过寻找规律可得
[f_n = 2 (n - 2^{m}) + 1
]
这个式子用数学归纳法可以证明
推论
如果一个函数长的和约瑟夫问题很像，或者说有另外的递推式，我们应该怎样寻找它的封闭形式呢？
对于一个函数，我们可以加入独立参数来描绘它，比如，(f_1 = a, f_{2n} = 2f_n + b_0, f_{2n + 1} = 2f_n + b1)
对于一些特殊情景（如 (f_2 = 2f_1 + b_0)）我们可以直接解出它的特殊参数
总结
通过上面的例子可以发现，在求解一个封闭形式时，一般要先讨论边界和小数情况，进行合理推理和猜想，最后证明式子
对于一般的递归式，可以设置独立参数来辅助求解