介绍如题的内容。
汉诺塔
汉诺塔是颇为出名的游戏，有三根柱子，一开始一根柱子上有 $n$个圆盘，从上到下越来越大。每次移动一个圆盘，必须先移动最上面的圆盘，圆盘必须移动到比自己小的圆盘上方。经过多少步才能把所有圆盘移动到另一个柱子上？假设是$T_n$ 步。
经典的做法是递归。要移动 $n$个圆盘，可以先移动前$n-1$个圆盘到另一根柱子上，把最底下的圆盘移动到剩下的柱子，再把$n-1$ 个圆盘移动到目标柱子上。这样每个过程都等价成更小数值圆盘的移动。也就有：
$$ T_n\leq 2 T_{n-1}+1 $$
实际上这也就是我们能做到的最好的办法了。我们总要移动最后一个圆盘，在这时，其他圆盘一定在剩下的柱子上，也就是说此时的步数 $\ge T_{n-1}$。那么移动也至少一步，最后也一样，至少是$T_{n-1}$，因此$T_n\ge 2T_{n-1}+1$ ，那么：
$$ T_n=2T_{n-1}+1 $$
如何求解呢，高中我们学过待定系数，刷题的功劳就是，由于过分的熟悉，我们会机械地两边加一构造等比数列。但一般地呢，如果我们没见过呢？
猜测与验证是非常常见的数学方法。猜到答案之后，利用归纳法证明，是一个很不错的路径。我们算出前几项，不难发现是 $1,3,7$，自然会猜测通项是$2^n-1$ ，那么就可以利用归纳法证明。
如果这时候还注意不出来，可以直接一层一层地套递推式，容易观察到这样的结构：
$$ T_n=1+2+4+...+2^{n-2}+2^{n-1}T_1 $$
其中 $T_1$也就是$1$ ，那么利用等比数列求和我们同样能得到结果。
归并排序(merge sort)
给 $n>1$个数$x_1,…x_n$排序，方便起见令$n=2^t$ 。分成两步：
- 给 $x_1,…,x_{n/2}$和$x_{n/2+1},…,x_n$ 排序
- 合并两边，比较两边最小值即可
设 $T(n)$ 是最差情况下归并排序需要的比较次数。
合并中，最差情况下我们比较 $n-1$次。分别排序则是$2T(\frac{n}{2})$ 。那么：
$$ T(n)=2T(\frac{n}{2})+n-1 $$
这个式子就没法一眼顶针了。通常我们算出几项观察。前几项会是 $T(1)=0,T(2)=1,T(4)=5,T(8)=17,T(16)=49$
看起来不好猜，那么我们尝试代入递推式。
$$ T(n)=n-1+2T(\frac{n}{2})=n-1+2(\frac{n}{2}-1+2T(\frac{n}{4})) $$
再次代入就得到
$$ T(n)=n-1+n-2+n-4+8T(\frac{n}{8}) $$
如果忍住化简前面的式子，这样总能猜到了（
$$ T(n)=n-1+n-2+\dots+n-2^{i-1}+2^iT(\frac{n}{2^i}) $$
最后，在我们美丽的假设下，令 $i=log_2n=t$，此时最后那个就是$T(1)=0$ ，就得到
$$ T(n)=\sum_{i=0}^t(n-2^i)=nlog_2n-n+1 $$
几乎是线性的，比挨个比较快上不少。
比较发现：
$$ T(n)=2T(n-1)+1\implies T(n)\sim2^n $$
$$ T(n)=2T(\frac{n}{2})+n-1\implies T(n)\sim nlog_2n $$
二者形式相似但差别巨大，就在于 $T()$ 里边的不同。
一般地不是 $2$的幂次的情形，并稍微改改递推，我们变成$S(1)=0,S(n) = S(\lfloor \frac{n}{2} \rfloor) + S(\lceil \frac{n}{2} \rceil) + 1$。代入 $1,2,3,4$ 试试：$S=0,1,2,3$，那么通项会是$n-1$ 吗，我们用加强的归纳法尝试：
[!归纳]
奠基步： $S(1)=1-1=0$ ，成立。归纳步：假设 $P(1),…,P(n-1)$ ，$S(n)=S(\lfloor \frac{n}{2} \rfloor) + S(\lceil \frac{n}{2} \rceil) + 1$，利用假设得到$S(n)=\lfloor \frac{n}{2} \rfloor -1 + \lceil \frac{n}{2} \rceil -1+ 1$，尽管不知道$n$的奇偶性，但是$\lfloor \frac{n}{2} \rfloor + \lceil \frac{n}{2} \rceil$总会是$n$，那么$S(n)=n-1$ 也成立。
那么利用归纳公理就得到原命题成立。
那么也就是说 $S(n)\sim n$，从$n-1$到$1$ ，对数就消失了。
之前我们总是能通过猜和代入递推式解决，但是并不总是那么美妙。
$$ T(x) = \begin{cases} 2T\left(\frac{x}{2}\right) + \frac{8}{9}T\left(\frac{3x}{4}\right) + x^2 & \text{for } x \geq 1 \\ 0 & \text{for } x < 1 \end{cases} $$
这如果进行代入，就是大工程了（
Akra-Bazzi 定理
形如下式的递归方程：
$$ T(x) = \sum_{i=1}^{k} a_i T(b_i x + h_i(x)) + f(x) $$
$a_i$：子问题的系数（如你图中 $T(x/2)$前面的$2$）。
$b_i$：规模缩减比例（如 $1/2$和$3/4$）。
$f(x)$：合并开销，必须是多项式，而且要求$|f’(x)|\leq x^c$。
$h_i(x)$：微小的扰动（比如之前的取整符号 $\lfloor \dots \rfloor$），要求 $|h_i(x)|\leq O(\frac{x}{log_2x})$。
第一步：求出关键指数 $p$这是最核心的一步。你需要找到一个$p$，使得下列等式成立：
$$ \sum_{i=1}^{k} a_i b_i^p = 1 $$
这个 $p$ 决定了递归树中“叶子节点”的生长速度。
第二步：代入公式
一旦算出 $p$，直接套用这个积分公式：
$$ T(x) = \Theta\left( x^p \left( 1 + \int_{1}^{x} \frac{f(u)}{u^{p+1}} du \right) \right) $$
据教授说，这个式子通过猜测得到（
如果你愿意，可以尝试用归纳法验证，但有些 $painful$ 。
我们尝试用用：$T(n)=2T(\frac{n}{2})+n-1$，这个归并排序的递推式，$a_1=2,b_1=1/2$ ，$p=1$就能让$a_1b_1^p=1$ 。那么利用上述定理：
$$ T(x)=\Theta(x+x\int_1^x\frac{u-1}{u^2}du) $$
积分只要拆开就行，是容易的，最后也就得到
$$ T(x)=\Theta(x+x(lnu+\frac{1}{u})\bigg|_1^x)=\Theta(xlnx) $$
这并不很能显示定理的强大，我们看这个 $nasty\ guy$ :
$$ T(x) = \begin{cases} 2T\left(\frac{x}{2}\right) + \frac{8}{9}T\left(\frac{3x}{4}\right) + x^2 & \text{for } x \geq 1 \\ 0 & \text{for } x < 1 \end{cases} $$
运用定理，我们要找到 $p$ 使得：
$$ 2(\frac{1}{2})^p+\frac{8}{9}(\frac{3}{4})^p=1 $$
幸运的是 $p=2$ 恰好符合方程，那么就有：
$$ T(x)=\Theta(x^2+x^2\int_1^x\frac{u^2}{u^3}du)=\Theta(x^2lnx) $$
看起来可怕的递推变成了无脑的计算。但是 $p$ 未必总是那么漂亮，例如：
$$ T(x)=3T(\frac{x}{3})+4T(\frac{x}{4})+x^2 $$
我们就要考虑：
$$ 3(\frac{1}{3})^p+4(\frac{1}{4})^p=1 $$
$p$就不是整数了。 计算$p=2$，会发现左侧比$1$小，说明$p<2$，同样我们发现$p>1$ 。但好处是，我们直接看积分：
$$ T(x)=\Theta(x^p+x^p\int_1^x\frac{u^2}{u^{1+p}}du) $$
积分那项却很简单：
$$ x^p\int_1^x\frac{u^2}{u^{1+p}}du=x^p(x^{2-p}-1)\frac{1}{2-p} $$
出来一个 $x^2$，由于$p<2$ ，可以扔掉，就得到：
$$ T(x)=\Theta(x^2) $$
我们并不需要知道具体的 $p$ 。实际上这是一个定理：
$$ \text{如果： }f(x)=\Theta(x^t),t\ge 0, \text{使得} \sum_{i=1}^{k} a_ib_i^t< 1,\text{那么 } T(x)=\Theta(g(x)) $$
可以类似上方地证明。这样就十分方便了。