Part 1 递归式

1.1 汉诺塔问题

设 \(T_n\) 是将 \(n\) 个圆盘从一个柱桩移动到另一根柱桩所需要的最少移动步数。

不难得到 \(T_n = 2 T_n +1\)。

为了将求 \(T_n\) 从 \(O(n)\) 转化到 \(O(1)\)，需要将递推式转化为封闭形式。

找规律不难发现 \(T_n=2^n - 1\)，考虑严谨的证明。

数学归纳法

1. 证明当 \(n\) 较小时，结论成立；
2. 证明若结论在 \(n=k\) 时成立，那么 \(n=k+1\) 时也成立。

\(T_{k+1}=2T_k+1=2\times(T_k-1)+1=2^{k+1}-1\)。

换元

主要形式是 \(a_n=p\times a_{n-1} + q\)，求 \(a_n\) 的通项公式。

首先考虑 \(q=0\) 时，\(a_n=p\times a_{n-1}=p^2 \times a_{n-2}=\dots=p^{n-1}\times a_1=p^n \times a_0\)。

接下来解决 \(q \not= 0\) 的情况。

考虑找到一个 \(b_n\)，使得其与 \(a_n\) 有一定的关系。

令 \(b_n = a_n + \frac{q}{p-1}\)，带入可得 \(b_n=p^b_{n-1}\)，可得 \(b_n\)，从而得到答案 \(a_n\)。