具体数学 第一章 递归问题

No 9

运用 反向归纳法 证明：

$\begin{aligned}P(n):x_1 \cdots x_n \le (\frac{x_1+\cdots x_n}{n})^n\end{aligned}$

首先证明简单情形：

当 $n=2$ 时，$(x_1+x_2)^2-4x_1x_2=(x_1-x_2)^2\ge 0$

证明 $n>1$ 时，可以由 $P(n)$ 推出 $P(n-1)$。（往小的方向推）

只要令 $x_n=(x_1+x_2+\cdots+x_{n-1})/(n-1)$，如何构造的？可以观察取等条件是 $x_1=x_2=\cdots=x_n$，于是猜想 $x_n$ 为 $x_1+x_2+\cdots+x_{n-1}$ 的平均数。

而下面证明 $P(2)$ 和 $P(n)$ 能够推出 $P(2n)$：

$\begin{aligned} x_1x_2\cdots x_{2n-1} &\le (\frac{x_1+x_2+\cdots x_n}{n} \times \frac{x_{n+1}+x_{n+2}+\cdots x_{2n}}{n})^n \\ &\le ((\frac{x_1+x_2+\cdots x_n}{n}+\frac{x_{n+1}+x_{n+2}+\cdots x_{2n}}{n})/2)^{2n}\\ &=(\frac{x_1+x_2+\cdots+x_{2n}}{2n})^{2n} \end{aligned}$

而对于任意的 $n$，不妨假设 $n \le 2^k$，由 $P(2)$ 推出 $P(4), P(8), \cdots P(2^k)$，而由 $P(2^k)$ 逐步减一，得到 $P(n)$，得证。

No 10

设剩下来的柱子是 C，注意到 $Q_n$ 相当于“顺时针转一个”，$R_n$ 相当于 “顺时针转两个”，其起始点并无影响。

对于 $Q_n=2R_{n-1}+1$，先把 $n-1$ 个圆盘从 A 移向 C，再把最大的圆盘移向 B，最后把 C 上的 $n-1$ 个圆盘移向 B，即可证明 $Q_n \le 2R_{n-1}+1$，而不妨考虑最大的圆盘什么时候移动到 B，只有当 A 上的 $n-1$ 个圆盘都到 C 时才可以（它们不能到 B 上，否则最大圆盘不能移动到 B，也不能留在 A 上，否则取不出最大圆盘），这时我们已经需要 $R_{n-1}$ 次操作了，移动一次最大圆盘到 B，又至少需要 $R_{n-1}$ 次操作将 $n-1$ 个圆盘移向 B，这样就能证明 $Q_n \ge 2R_{n-1}+1$，于是 $Q_n=2R_{n-1}+1$。

对于 $R_n=Q_n+Q_{n-1}+1$，首先需要将 B 上的 $n-1$ 个圆盘移向 A，再将最大圆盘移到 C，将 $n-1$ 个圆盘从 A 移到 B 之后，再次移动最大圆盘到 A，最后将 $n-1$ 个圆盘从 A 移到 C，这样总共是 $R_{n-1}+1+Q_{n-1}+1+R_{n-1}=Q_n+Q_{n-1}+1$，我们可能会认为 $R_{n}=2Q_{n}$，但是有些中间的过程可以省略。如何分析我们的问题出现在哪里？观察最大圆盘的运动，为了使移动次数最少，第一次一定是从 B 到 C，第二次一定是从 C 到 A，回顾最大圆盘移动的要求，需要它的上面没有圆盘，移动到的位置没有圆盘，于是我们可以得出上述的最小移动结果，而我们的错误结果将最大圆盘移动了 4 次，因此不是最少。

No 16

成套方法：

使用待定系数法，找出有无穷组解的方程表达形式 $g(n)=h(n)$，推测 $g(n)$ 的系数。

我们设 $g(n)=A(n)\alpha+B(n)\gamma+C(n)\beta_{0}+D(n)\beta_1$。

代入 $g(n)=1$，$1=\alpha,1=3+\gamma n+\beta_j$，得到 $\alpha=1,\gamma=0,\beta_j=-2$。

代入 $g(n)=n$，$1=\alpha,2n+j=3n+\gamma n+\beta_j$，得到 $\alpha=1,\gamma=-1,\beta_j=j$。

考虑 $\alpha=1,\gamma=0,\beta_j=0$ 的情形，有 $g(1)=1,g(2n+0,1)=3g(n)$，不妨设 $n=2^m+l,0\le l <2^m$，那么 $A(n)=3^m$。

考虑 $\alpha=0,\gamma=1,\beta_j=0$ 的情形，有 $g(1)=0,g(2n+0,1)=3g(n)+n$

于是我们有：

$\begin{aligned} A(n)=3^m\\ A(n)-2(C(n)+D(n))=1\\ A(n)-B(n)+D(n)=n \end{aligned}$