过年几天没怎么看公开课，这两天补一下
1.
当 $n=2$ 时，两个集合为 ${1}, {2}$，交集为空，所以从 1 推到 2 的时候有问题。
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 $$3.
设 $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 $$得证。
4.
设 $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 $$得证。
5.
不能，一个新的圆和原来的圆最多增加两个交点，最多增加六块区域，6+8=14
6.
每多一条直线，和原有的每条直线增加一个交点，也就是增加n-1个交点，最多增加n-2个新区域
设有界区域的最大个数是$a_n$个，那么$a_n=a_{n-1}+n-2$
$$ a_1=a_2=0,a_n=\sum_{i=0}^{n-2}i $$7.
$H(1)=J(2)-J(1)=0 \neq 2$
8.
从$Q_2$写到$Q_6$，容易发现，$Q_k=Q_{k-5},k \ge 5$
9.
(a)
令
$$ x_n=\frac{x_1+\cdots+x_{n-1}}{n-1}, $$证明 $P(n)\Rightarrow P(n-1)$
取任意 $x_1,\dots,x_{n-1}\ge0$，记
$$ S=x_1+\cdots+x_{n-1},\qquad x_n=\frac{S}{n-1}. $$$$ x_1\cdots x_{n-1}\cdot\frac{S}{n-1} \le \left( \frac{S+\frac{S}{n-1}}{n} \right)^n. $$$$ x_1\cdots x_{n-1}\cdot\frac{S}{n-1} \le \left(\frac{S}{n-1}\right)^n. $$若 $S=0$，则 $x_1=\cdots=x_{n-1}=0$，显然 $P(n-1)$ 成立；
若 $S>0$，两边同除以 $\dfrac{S}{n-1}>0$，得
因此
$$ P(n)\Rightarrow P(n-1)\quad (n>1). $$(b)
设 $x_1,\dots,x_{2n}\ge 0$，记
$$ A=\frac{x_1+\dots+x_n}{n},\qquad B=\frac{x_{n+1}+\dots+x_{2n}}{n}. $$由 $P(n)$ 得
$$ x_1\cdots x_n \le A^n, \qquad x_{n+1}\cdots x_{2n} \le B^n. $$因此
$$ \prod_{i=1}^{2n} x_i= (x_1\cdots x_n)(x_{n+1}\cdots x_{2n}) \le A^n B^n= (AB)^n. $$由 $P(2)$
$$ (AB)^n \le \left(\frac{A+B}{2}\right)^{2n}. $$于是
$$ \prod_{i=1}^{2n} x_i \le (AB)^n \le \left(\frac{A+B}{2}\right)^{2n}. $$而
$$ \frac{A+B}{2}= \frac{ \frac{x_1+\dots+x_n}{n}+ \frac{x_{n+1}+\dots+x_{2n}}{n} }{2}= \frac{x_1+\dots+x_{2n}}{2n}. $$因此
$$ \prod_{i=1}^{2n} x_i \le \left( \frac{x_1+\dots+x_{2n}}{2n} \right)^{2n}. $$得证