递归问题
汉诺塔问题
记三根柱子分别为 $A$ 、 $B$ 、 $C$ ，初始时所有 $n$ 个圆盘都在 $A$ 上，要将所有圆盘从 $A$ 移动到 $C$ ，且在移动过程中始终保持大盘在下小盘在上。设最少需要移动 $T_n$ 次。
- $n = 0$ 时，不需要移动， $T_0 = 0$ ；
- $n = k$ 时，最小的移动次数为 $T_k$ ；
-
$n = k + 1$
时，这个递归问题可以分解为三步：
- 先将上面的 $k$ 个圆盘从 $A$ 移动到 $B$ ，最少需要 $T_k$ 步；
- 再将最下面的第 $k + 1$ 个圆盘从 $A$ 移动到 $C$ ，需要 $1$ 步；
- 最后将 $k$ 个圆盘从 $B$ 移动到 $C$ ，需要 $T_k$ 步。
于是有：
$$T_{k+1} = T_k + 1 + T_k = 2T_k + 1.$$
对式子两边同时除以 $2^{k+1}$ ：
$$\frac{T_{k+1}}{2^{k+1}} = \frac{T_k}{2^k} + \frac{1}{2^{k+1}}.$$
$\{\frac{T_k}{2^k}\}$ 是一个等比数列，满足：
于是：
$$\frac{T_n}{2^n} = 1 - \frac{1}{2^n}.$$
于是：
$$T_n = 2^n - 1,\; n \ge 0.$$
通项为 $a_n = a_1 \cdot q^{n-1}$ ( $q \ne 1$ ) 的求和公式：
$$\sum_{i=1}^n a_i = \frac{a_1 \cdot (1-q^n)}{1-q} = \frac{a_1 - a_{n+1}}{1-q}$$