柯西的反向归纳法

1. 柯西的反向归纳法

命题1.1：“AM-GM”不等式

$a_1,\cdots ,a_n$为$n$个非负实数，那么 $\frac{a_1+\cdots +a_n}{n}\ge \sqrt[n]{a_1\cdots a_n}$等式成立当且仅当$a_1=\cdots =a_n$。

柯西在证明这个不等式的时候使用了归纳法，但不同于一般的归纳法假设$n=k$的时候成立然后推导$n=k+1$的时候成立，而是采用了其自创的一种归纳方法，称之为“反向归纳法”（backward induction），或者更具体一点“柯西反向归纳法”:

命题1.2：柯西反向归纳法

如果关于自然数$n$的命题$P(n)$满足：

1. $P(1)$成立。
2. 如果$P(n)$成立，那么$P(2n)$成立。
3. 如果$P(m+1)$成立，那么$P(m)$成立。

那么该命题对任意$n=1,2,\cdots$都成立。

• 我们可以从对正整数的dyadic分解来理解这个归纳法。我们定义$I_k:=\{2^k+1,\cdots ,2^{k+1}\}$然后正整数集合可以分解为:${\mathbb{Z}}^{+}=\{1\}\cup I_1\cup \cdots \cup I_k\cup \cdots$然后我们证明了对于命题$P(n)$，在$\{1\}$以及任意一个$I_k$的右端点上成立。不仅如此，在任意一个$I_k$上，由于$P(2^{k+1})$成立那么$P(2^{k+1}-1)$成立，然后$P(2^{k+1}-2)$也成立。如此这般推导，我们可以证明$P(n)$在任何一个$I_k$上成立，那么很自然$P(n)$在整个正整数集上成立。

对于”AM-GM”不等式而言$n=1$是平凡的。

现在假设$n=k$成立，那么$\begin{array}{rl}\frac{a_1+a_2+\cdots +a_{2k}}{2k}& =\frac{\frac{a_1+\cdots +a_k}{k}+\frac{a_{k+1}+\cdots +a_{2k}}{k}}{2}\\ & \ge \frac{\sqrt[k]{a_1\cdots a_k}+\sqrt[k]{a_{k+1}\cdots a_{2k}}}{2}\\ & \ge \sqrt{\sqrt[k]{a_1\cdots a_k}\sqrt[k]{a_{k+1}\cdots a_{2k}}}\\ & =\sqrt[2k]{a_1\cdots a_{2k}}\end{array}$于是我们便验证了$P(k)⟹P(2k)$。

然后假设$P(k)$成立,于是$\begin{array}{rl}\frac{a_1+\cdots +a_{k-1}+\sqrt[k-1]{a_1\cdots a_{k-1}}}{k}& \ge \sqrt[k]{a_1\cdots a_{k-1}\sqrt[k-1]{a_1\cdots a_{k-1}}}\\ & =\sqrt[k-1]{a_1\cdots a_{k-1}}\end{array}$这个结果可以推出$\frac{a_1+\cdots +a_{k-1}}{k-1}\ge \sqrt[k-1]{a_1\cdots a_{k-1}}$也就是说$P(k)⟹P(k-1)$。

综上所述，根据“命题2”不等式对任意正整数都成立。

2. 反向归纳法的应用1：中点凸就能满足Jensen不等式

定义2.1

$f:I\to \mathbb{R}$是中点凸的，如果对任意$x,y$都有$\frac{f(x)+f(y)}{2}\ge f\left(\frac{x+y}{2}\right)$

[!命题2.2] $f:I\to \mathbb{R}$是中点凸的,那么对任意正整数$n$，它满足Jensen不等式。即对任意$x_1,\cdots ,x_n\in I$都有$\frac{f(x_1)+\cdots +f(x_n)}{n}\ge f\left(\frac{x_1+\cdots +x_n}{n}\right)$

我们可以通过柯西反向归纳法来证明这件事。

$n=1$是平凡的，$n=2$就是中点凸的定义，这两项直接满足。

如果$P(n)$成立，我们来推导$P(2n)$也成立：$\begin{array}{rl}f\left(\frac{x_1+\cdots +x_{2n}}{2n}\right)& =f\left(\frac{1}{2}\left(\frac{x_1+\cdots +x_n}{n}+\frac{x_{n+1}+\cdots +x_{2n}}{n}\right)\right)\\ & \le \frac{1}{2}f\left(\frac{x_1+\cdots +x_n}{n}\right)+\frac{1}{2}f\left(\frac{x_{n+1}+\cdots +x_{2n}}{n}\right)\\ & \le \frac{f(x_1)+\cdots +f(x_n)}{2n}+\frac{f(x_{n+1})+\cdots +f(x_{2n})}{2n}\\ & =\frac{f(x_1)+\cdots +f(x_{2n})}{2n}\end{array}$ 然后我们验证如果$P(n)$成立那么$P(n-1)$也成立：

$\begin{array}{rl}f\left(\frac{x_1+\cdots +x_{n-1}}{n-1}\right)& =f\left(\frac{x_1+\cdots +x_{n-1}+\frac{x_1+\cdots +x_{n-1}}{n-1}}{n}\right)\\ & \le \frac{f(x_1)+\cdots +f(x_{n-1})+f\left(\frac{x_1+\cdots +x_{n-1}}{n-1}\right)}{n}\end{array}$ 整理式子可得$f\left(\frac{x_1+\cdots +x_{n-1}}{n-1}\right)\le \frac{f(x_1)+\cdots +f(x_{n-1})}{n-1}$于是根据柯西的反向归纳法，该命题成立。

3. 反向归纳法的应用2：关于环的幂零元

[!命题3.1] 如果环$R$当中任何一个元素$a$都满足性质（$a^2=0⟹a=0$），那么环$R$当中的幂零元只有$0$。

如果我们把这个问题看成是一个关于正整数$n$的命题$P(n)$：对任意$x\in R$，如果$x^n=0$，则$x=0$。如果这个命题对任意正整数$n$都成立，那么自然就能证明目标命题。现在我们从归纳法的角度来理解这个问题:

1. $n=1$的情况是平凡的，显然成立。$n=2$的时候是成立的，因为这是目标命题的前提条件。
2. 我们发现如果$x^{2n}=(x^n{)}^2=0$那么一定有$x^n=0$然后如果假设$P(n)$成立，那么就能得到$x=0$。也就是说我们可以证明$P(n)⟹P(2n)$
3. 然后我们需要检验，如果$P(n),n>1$成立是否能导出$P(n-1)$。也就是说假设$x^{n-1}=0$我们需要导出$x=0$。这是一定的，因为$x\cdot x^{n-1}=x\cdot 0=0$于是我们便导出$x^n=0$。而我们已经假设$P(n)$成立，那么一定有$x=0$。于是我们得到$x^{n-1}=0⟹x=0$对任意$x\in R$成立，也就是说$P(n-1)$成立。

那么根据柯西的反向归纳法，我们可以得到对于任意的正整数$n$成立，于是目标命题成立。

4. 反向归纳法的应用3：Hilbert空间的自伴有界算子范数的一个性质

命题4.1:Hilbert空间的自伴有界算子范数的一个性质

设$A:H\to H$是实Hilbert空间$(H,⟨\cdot ,\cdot ⟩)$上的一个有界，自伴算子,$||\cdot ||$是其算子范数，那么$||A^n||=||A|{|}^n$对任意正整数成立。

我们从分析的角度切入这个问题，首先我们通过算子范数的次可积性(submultiplicativity)知道$||A^n||\le ||A|{|}^n$所以这里的关键是另外一边的不等式，即对于任意正整数$n$都有$||A^n||\ge ||A|{|}^n$这里我们可以尝试利用柯西的反向归纳法来处理这个问题。因为如果我们把上面的不等式视为一个命题$P(n)$，我们会发现它符合柯西反向归纳法的一些条件：

• 首先对于$n=1$的时候一定是成立的，这种情况下命题是平凡的。
• 然后我们发现，如果假设$P(n)$成立然后我们实际上可以导出$P(n-1)$成立。因为$||A^{n-1}||\cdot ||A||\ge ||A^n||\ge ||A|{|}^n⟹||A^{n-1}||\ge ||A|{|}^{n-1}$
• 于是我们想到，如果可以验证$P(n)⟹P(2n)$，那么就可以利用柯西的反向归纳法证明上述命题。由于$A$是自伴算子，加上Hilbert空间上的柯西不等式，以及假设$P(n)$的命题成立，于是我们可以得到$P(2n)$成立:$\begin{array}{rl}||A^{2n}||& =\underset{||x||\le 1}{\sup }||A^{2n}x||\\ & \ge \underset{||x||\le 1}{\sup }|⟨A^{2n}x,x⟩|\\ & =\underset{||x||\le 1}{\sup }|⟨A^{n}x,A^{n}x⟩|\\ & =||A^n|{|}^2\\ & \ge ||A|{|}^{2n}\end{array}$ 所以根据柯西的反向归纳法，我们知道该命题对任意正整数$n$成立。