一切的开始。
典例选讲
hanoi塔
问题不加赘述。
想要解决问题，书中便借此问题引出一些解决问题的通法：
- 先研究小的情形
- 命名并求解
经过这两步与一些基础的构造，不难把hanoi塔问题变为一组递推式：
\[\begin{array}{ll} &T_0 = 0;\\ &T_n \leq 2T_{n-1}+1, n>0. \end{array} \] 接下来尝试得出这组递推式的解，即将递推式转换为等价的，且关于 \(T_n\) 的式子中不含 \(T\) 。我们将这种形式的式子称为封闭形式，这会使我们求解 \(T\) 所需的计算大大的减省。
为了求解递推式，我们需要若干成体系的方法。数学归纳法便是众多方法中的一种，并且于这道题而言是一个非常不错的方法。
数学归纳法并不是一个求解的方法，而是一个证明的方法。因此我们在使用数学归纳法之前需要有一个猜想，而 \(T\) 的值十分有规律，不难猜出 \(t_n = 2^n-1, n \geq 0\) 。
在有了猜想之后，我们就可以开始使用数学归纳法进行证明。数学归纳法的步骤分为两步，首先是在 \(n\) 取最小值 \(n_0\) 时证明命题，这一步被称为基础（basis）。然后，对于所有 \(n>n_0\) ，假设 \(n^0\) 与 \(n-1\) 之间所有值已被证明，证明命题对 \(n\) 成立，这一步被称为归纳（induction）。这种方法可以让我们只使用两步就证明对于所有的 \(n\) 命题成立，不失为一种好的证明方法。
hanoi塔的问题解决过程完美涵盖了解决一般问题的三个阶段：
(1)研究小的情形。这有助于我们洞察问题，且对(2)(3)有所帮助。
(2)对有意义的量求出数学表达式并给出证明数学表达式能完全涵盖原问题。一般而言我们能通过阶段获取有意义的递归式。
(3)对数学表达式求出封闭形式并予以证明。
（《具体数学》主要探讨的是第三阶段，而这也正是我想要提升的部分，毕竟于我而言OI的难点就在于此。）
当然解决hanoi塔递归式的方式不止是循规蹈矩的数学归纳法，一些灵光一闪也能帮助我们解递归式，例如令 \(U_i = T_i+1\) ，套进原递归式将会化这样子：
这种形态的递归式想必不需特别的技巧即可得知 \(U_i = 2^i\) ，这样解递归式十分有效，因此在解题时请务必不要吝啬合理的想法。
平面上的 \(V\)
用 \(n\) 条直线最多能将一个平面分割成几个块，这个问题较为简单，不多讲，设这个数量为 \(L_n\) ，则递归式为 \(L_0 = 1, L_n = L_{n-1}+n\) ，通过高斯 \(L_n = \frac{n(n+1)}2 + 1, n \geq 0\) 。
接下来我们看一个相关问题：用 \(n\) 个 \(V\) 型最多能将一个平面分割成几个块。（ \(V\) 型是指在平面上同一个点出发的两条射线组成的图形）
乍一看这个问题没什么头绪，但我们可以通过适当的转化，来讲问题变换为我们熟悉的递归式。将射线变成直线，我们得到了下面这张图：
这样就是 \(2n\) 条直线的答案，但是还要减去 \(2n\) ，因为 \(V\) 型相比于 \(2\) 条直线每个都少划分了 \(2\) 个区域，因此区域数 \(Z_n = L_{2n}-2n = 2n^2-n+1\) 。
约瑟夫问题
一个经典的问题，而在本书中该问题的描述是：从围成标有记号 \(1\) 到 \(n\) 的圆圈的第 \(n\) 个人开始，每个一个人删去一个人，知道只有一个人存活。
将有 \(n\) 个人圆圈的幸存者命名为 \(J(n)\) 。首先尝试模拟求出部分的值：
然而 \(J(n)\) 看上去不如 \(T_n\) 一般有规律，能迅速找出递归式。这时我们可以分类讨论来帮助我们找出递归式：
(1)对于 \(n\) 为偶数的情形，经过一轮后剩下的人号码都会翻倍并减一，即：
(2)对于 \(n\) 为奇数的情形，我们一并把编号 \(1\) 的人删掉，那么就相当于经过一轮后剩下的人号码都会翻倍并加一，即：
\[J(2n+1) = 2J(n)+1, n \geq 1 \](3)组合上递归式的原始解 \(J(1) = 1\) ，总的递归式就长这样：
\[\begin{array}{ll} &J(1) = 1;\\ &J(2n) = 2J(n)-1, n\geq1;\\ &J(2n+1) = 2J(n)+1, n\geq1. \end{array} \]这个递归式并不如前两个一样好解，尝试从表格中找规律：
通过查表不难发现递归式的解为 \(J(2^m+l) = 2l+1, m \geq 0, 0 \leq l < 2^m\) ，然后用上我们刚学过的数学归纳法即可证明。
另外， \(J(n)\) 含有一个十分有趣的性质：先将 \(n\) 按二进制展开，即 \(n = (b_mb_{m-1}...b_1b_0)_2\) ，然后因为 \(J(n = 2m+l) = 2l+1\) 所以有 \(J((b_mb_{m-1}...b_1b_1)_2) = (b_{m-1}..b_1b_0b_n)\) ，即将 \(n\) 去掉了最高位的 \(1\) ，然后整体乘 \(2\) 再加上一个 \(1\) ，这样是等价于将 \(n\) 向左循环移动一位。不过因为要去掉前导零，所以除非 \(n = 2^x-1\) ，否则不能循环地转一圈。
（重点）成套方法求解递归式
前面我们都是用的
方法总结
数学归纳法
类型：证明
步骤：
(1)基础（basis）：在 \(n\) 取最小值 \(n_0\) 时证明命题。
(2)归纳（induction）：对于所有 \(n>n_0\) ，假设 \(n^0\) 与 \(n-1\) 之间所有值已被证明，证明命题对 \(n\) 成立。
转化
类型：思想
核心：将问题部分或全部转化为形式相近但已知的内容
分类讨论
类型：推导
步骤：
(1)提炼题目中每一个不同情形
(2)对每个不同情形分别求解
暴力列表
类型：求解
步骤：略（恼，这我也没法写啊）