汉诺塔
有三根细柱 \(A\)、\(B\)、\(C\)，其中 \(A\) 柱上套着 \(3\) 个圆盘。这些圆盘大小各异，按从大到小的顺序自下而上摆放。现在要把套在 \(A\) 柱上的 \(3\) 个圆盘全部移到 \(C\) 柱上，并且在移动圆盘时须遵守下述规则：
- 每次移动只能将柱子最上端的一个圆盘移到另一根柱子；
- 小圆盘上不能放大圆盘。
那么，将这 \(3\) 个圆盘全部从 \(A\) 柱移到 \(C\) 柱最少需要移动几次呢？
经过尝试，不难发现解法如下图：
现在考虑更一般的问题： \(A\) 柱上套着 \(n\) 个圆盘，将这 \(n\) 个圆盘全部从 \(A\) 柱移到 \(C\) 柱最少需要移动几次？
在处理 \(n=3\) 时，你可能已经注意到，可以将 \(7\) 步拆解成 \(3\) 个大步骤：
- Step 1 ~ Step 3：将 \(1,2\) 号圆盘从 \(A\) 柱按要求移到 \(B\) 柱
- Step 4：将 \(3\) 圆盘移到 \(C\) 柱
- Step 5 ~ Step 7：将 \(1,2\) 号圆盘从 \(B\) 柱按要求移到 \(C\) 柱
这提示我们移动的步骤是以某种“嵌套”的方式进行的，事实上，可以利用数列的递推解决问题。
设 \(n\) 个圆盘对应次数为 \(h_n\)，显然 \(h_1=1\)，对于 \(n\geq 2\)：
- 将 \(1,2,\ldots,n-1\) 号圆盘从 \(A\) 柱按要求移到 \(B\) 柱，共移动 \(h_{n-1}\) 次
- 将 \(n\) 圆盘移到 \(C\) 柱，共移动 \(1\) 次
- 将 \(1,2,\ldots,n-1\) 号圆盘从 \(B\) 柱按要求移到 \(C\) 柱，共移动 \(h_{n-1}\) 次
于是得到 \[h_n = 2h_{n-1} + 1, \quad (n \geq 2)\] 结合 \(h_1=1\)，不难解出 \[h_n = 2^n - 1\]
圆形叠放
\(n\) 个大小不限的圆随意叠放，最多把平面分成多少个区域？
我们知道：
- \(1\) 个圆把平面分成 \(2\) 个区域——里面和外面
- \(2\) 个相交的圆把平面分成 \(4\) 个区域
- \(3\) 个圆最多把平面分成 \(8\) 个区域
更多圆时会怎样呢？解决此类计数问题的一种方法是：研究从 \(n-1\) 个圆 \(\gamma_1, \ldots, \gamma_{n-1}\) 增加到 \(n\) 个圆 \(\gamma_1, \ldots, \gamma_n\) 时，平面区域数量的变化规律。
为了让划分的区域最多，这些圆形的排布应当是一般的，即任意两圆相交于两点，且不存在三个圆共点。
设 \(n\) 个圆最多把平面划分成 \(h_n\) 个区域，显然 \(h_1=2\)。考虑 \(n \geq 2\) 的情况，假设平面上已有 \(n-1\) 个处于一般位置的相互重叠的圆 \(\gamma_1, \ldots, \gamma_{n-1}\)，它们将平面划分为 \(h_{n-1}\) 个区域。此时加入第 \(n\) 个圆 \(\gamma_n\)，使得：
- 前 \(n-1\) 个圆中的每一个都与 \(\gamma_n\) 相交于两点
- 共产生 \(2(n-1)\) 个不同的交点 \(P_1, P_2, \ldots, P_{2(n-1)}\)
这些交点将 \(\gamma_n\) 分割为 \(2(n-1)\) 段弧： \[P_1P_2,\ P_2P_3,\ \ldots,\ P_{2(n-1)-1}P_{2(n-1)},\ P_{2(n-1)}P_1\] 每一段弧会将某个由前 \(n-1\) 个圆构成的区域一分为二，从而净增加 \(2(n-1)\) 个新区域。因此递推关系为： \[h_n = h_{n-1} + 2(n-1), \quad (n \geq 2)\] 结合 \(h_1=2\)，通过累加，可得到 \[h_n = n^2 - n + 2\]
\(h_1=2,\ h_2=4,\ h_3=8,\ h_4=14\)
\(n>3\) 时 \(h_n<2^n\)，所以用圆形代表集合的韦恩图最多只能完整表示 \(3\) 个集合之间的关系。
这篇文章原本的计划是讨论多种可以用数列递推解决的问题，在完成以上内容后剩余部分迟迟没有动笔，于是干脆只写这么多发出来了。
以下是原本为这篇文章搜集的部分题目。
- 欲登上第 \(10\) 级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有多少种？
- 某人计划给 \(8\) 块牌子涂色，每块牌子可选用红、蓝中的一种颜色喷涂。若要求相邻两块牌子不都为红色，试求所有的染色方案数。
- Find a recurrence relation and initial conditions for the sequence \(\{a_n\}\), where \(a_n\) is the number of strings of \(n\) digits (that is, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) that do not contain consecutive even digits (where 0 counts as an even digit).
- 设满足下列条件的 \(n\) 位数有 \(a_n\) 个，写出 \(a_n\) 的表达式。
- 不出现 \(1, 2, 3, 4\) 以外的数字
- \(1\) 出现奇数次
- 由 \(A\) 至 \(G\) 七个字符中部分或全部字符组成 \(n\) 位字符串，希望任意相邻的两个字母不同时为 \(A\)、不同时为 \(B\)、不同时为 \(C\)，请问满足条件的字符串共有多少个?（写出递推式）
思考：
- 什么样的问题能用递推解决？
- 什么时候应该想到用递推解决？
