过年几天没怎么看公开课，这两天补一下
当 $n=2$ 时，两个集合为 ${1}, {2}$，交集为空，所以从 1 推到 2 的时候有问题。
设 $T(n)$ 是把 $n$ 个盘子从 A 移动到目标 B 的最少次数，初步可以得到递推式
$$ T(n)\le 3T(n - 1) + 2 $$模拟一下盘子的移动过程。
首先我们要让 $n-1$ 个较小的盘子从 A 移动到 B，然后让之前 A 上最大的盘子移动到 C，这一步要至少 $T(n-1)+1$ 步（+1 意思是最大的盘子移动）。
我们希望最大的盘子在 B 的最下方，所以还得先让 B 上较小的那些盘子回到 A，因此又需要 $T(n-1)+1$ 步。
最后最大盘到 B 后我们还需要把 $n-1$ 个盘子移动到 B，所以加起来至少需要
$$ 3T(n-1)+2 $$因此
$$ T(n)=3T(n-1)+2=3^n-1 $$设 $T(n)$ 是 $n$ 个盘子所有合法的状态集合，$T(1)=3, T(2)=9$，我们 guess
$$ T(n)=3^n $$假设 $n-1$ 时结论成立，下证 $n$ 时结论也成立。
回忆上一道题的过程，其实虽然一共有 5 步，但是这是一个类似周期的过程。总有一个时刻是最大的盘子在 A、B 或者 C 的柱子上，然后剩下的 $n-1$ 个盘子在做移动。
因此总共就是
$$ 3 \times 3^{n-1}=3^n $$得证。
设 $T(n)$ 是在合法状态下，存在 $n$ 个圆盘需要最多的移动次数$\le 2^n-1$
当 $n=1$ 时，需要一次移动，显然成立。
假设 $n-1$ 时结论成立，也就是说最多移动次数$\le 2^{n-1}-1$
$n$ 个盘子时候的第一个合法状态，如果最大的盘子已经在目标 B 柱上，那么只需要 $T(n-1)$ 次操作就可以，显然成立。
若最大盘子不在 B 柱上，我们首先需要将 $n-1$ 个盘子移动到中间柱 C，然后把大盘移动到 B，最后递归剩下的盘子，最多 $2^{n-1}-1$。
因此总步数就是
$$ 2^n-1 $$得证。