凹数列的反向柯西不等式的严格论证
参见：牟晓生.《凹数列的反向柯西不等式》
注记：这个问题是Barnes的一个猜想，其证明的是积分形式以及两数列单调的情形，这里给出的是离散形式的证明，主要的证明步骤来自牟神，此版本是对原证明的说明与补充，在思路上也更加清晰完整。这个优雅的问题的完整严格证明是十分困难的，有兴趣的同学可以对本文中的任何一个省略的细节加以完善。
此题的意义：对于一般的反向柯西不等式（康罗托维奇budengshi),此题给出了更一般的结论，不用在可疑的附加数列有界这个条件。
下附lex以便自修：
$i=1,2,...,n;a_i,b_i\ge 0;$对于$1<i<n$,我们有$a_i\ge \frac{a_{i-1}+a_{i+1}}{2} ,b_i\ge \frac{b_{i-1}+b_{i+1}}{2}$ ;证明：$$\sum_{i=1}^{n} a_ib_i\ge \frac{n-2}{2n-1} \sqrt{\sum_{i=1}^{n} a_i^2\sum_{i=1}^{n} b_i^2} $$
$$引理一：i=1,2,..,n;a_i,b_i\in R,则有\sum_{i=1}^{n} a_ib_i+\sqrt{\sum_{i=1}^{n} a_i^2\sum_{i=1}^{n} b_i^2} \ge \frac{2}{n}\sum_{i=1}^{n} a_i\sum_{i=1}^{n} b_i$$
Let
$$ x_i = \displaystyle \frac{a_i}{ \displaystyle\sqrt{\sum_{i=1}^n a_i^2}} ,
y_i = \displaystyle \frac{b_i}{ \displaystyle \sqrt{\sum_{i=1}^n b_i^2}}$$
for $1 \le i \le n$. We notice that
\[
\sum_{i = 1}^n x_i^2 = \sum_{i=1}^n y_i^2 = 1
\]
It suffices to show that
\[
\sum_{i=1}^n x_iy_i + 1 \ge \frac{2}{n}\cdot\left(\sum_{i=1}^n x_i\right)\cdot\left(\sum_{i=1}^n y_i\right)
\]
or
\[
\sum_{i=1}^n (x_i + y_i)^2 \ge \frac{4}{n} \cdot\left(\sum_{i=1}^n a_i\right)\cdot\left(\sum_{i=1}^n b_i\right)
\]
This comes directly from Cauchy-Schwarz and $(a + b)^2 \ge 4ab$ inequality as follows
\[
\sum_{i=1}^n (x_i + y_i)^2 \ge \frac{1}{n}\cdot \left(\sum_{i=1}x_i + \sum_{i=1}y_i\right)^2 \ge \frac{4}{n} \cdot\left(\sum_{i=1}^n a_i\right)\cdot\left(\sum_{i=1}^n b_i\right)
\]
Therefore, we complete our proof.
引理二：设 $ a_{1}, a_{2}, \ldots, a_{n} $ 是一个单调的非负凹数列, 且满足 $ \sum_{i=1}^{n} a_{i}=\frac{n(n-1)}{2}$ . 则
$$ \sum_{i=1}^{n} a_{i}^{2} \leq \sum_{i=1}^{n}(i-1)^{2}=\frac{n(n-1)(2 n-1)}{6}$$ .
证明 不妨设 $a_{1} \leq a_{2} \leq \cdots \leq a_{n}$ . 由 Karamata 不等式, 只需证明对每 个 $ 1 \leq k \leq n-1$ 有
$$\sum_{i=k+1}^{n} a_{i} \leq \sum_{i=k+1}^{n}(i-1) .$$
注意到对每个 $ 1 \leq j \leq k<i \leq n ,$ 由凹数列性质有
$$a_{j} \geq \frac{j-1}{i-1} \cdot a_{i}+\frac{i-j}{i-1} \cdot a_{1} \geq \frac{j-1}{i-1} \cdot a_{i} $$.
重写为 $ \frac{i-1}{j-1} \cdot a_{j} \geq a_{i} $, 对 i 求和得到
$$\frac{\sum_{i=k+1}^{n}(i-1)}{j-1} \cdot a_{j} \geq \sum_{i=k+1}^{n} a_{i}, \forall 1 \leq j \leq k .$$
如果 $ \sum_{i=k+1}^{n} a_{i}>\sum_{i=k+1}^{n}(i-1) $, 那么由上面的不等式可知 $a_{j}>j-1, \forall 1 \leq j \leq k $. 这样导致所有 $ a_{i}$ 的和大于$ \sum_{i=1}^{n}(i-1)$ , 与引理条件矛盾. 于是引理得证!
情况一：
$\left \{ a_i \right \} ,\left \{ b_i \right \}$ 均为单调数列，我们设$\sum_{i=1}^{n} a_i=\sum_{i=1}^{n} b_i=\frac{n(n-1)}{2} $,那么利用引理一和二：$$LHS-RHS=\sum_{i=1}^{n}a_ib_i\ge \frac{2}{n}\sum_{i=1}^{n}a_i\sum_{i=1}^{n}b_i- \sqrt{\sum_{i=1}^{n}a_i^2\sum_{i=1}^{n}b_i^2}- \frac{n-2}{2n-1} \sqrt{\sum_{i=1}^{n} a_i^2\sum_{i=1}^{n} b_i^2} \ge \frac{n(n-1)(n-2)}{3} $$
引理三（情况二：对任何$i\ne j,b_i=b_j$）：$\sum_{i=1}^{n}a_i=\frac{n(n-1)}{2} ,a_i仍然保持凹性，$那么$$\sum_{i=1}^{n}a_i^2\le \frac{n^2(n-1)(2n-3)}{6\left ( n-2 \right ) } $$
证明：
首先验证$$LHS=F(a_1,a_2,...,a_n),
取到最大值时必有\min\left \{ a_i \right \} =0$$
$$记a_k=\max\left \{ a_i \right \} ,我们断言a_{k+1}或者a_{k-1}为\left \{ a_i \right \}中第二者大的，无妨设\left \{ a_i \right \}中第二者大的为a_{k-1},$$
$$我们记k-1=i+1,n-k=j,2\le t\le i+1,a_t=a_1+\sum_{k=1}^{t-1} x_k,同样的k\le t\le n,\\我们有a_{n-k+1}=b_k,无妨设：a_1\le a_n,b_1=a_1+x_1,...,b_{1\le k\le j}=a_1+\sum_{t=1}^{k} y_t,x_k,y_k\ge 0$$
$$我们将a_{ 1\le k\le i+1 } 调整为a_1\left ( \frac{n}{n-1} \right ) +\sum_{t=1}^{k-1} x_t=a^*_k,同理a_1\left ( \frac{n}{n-1} \right ) +\sum_{t=1}^{k} y_t=b^*_k$$
$$\sum_{t=1}^{i+1} \left ( a_t^* \right ) ^2+\sum_{t=1}^{j} \left ( b_t^* \right ) ^2-\sum_{i=1}^{n}a_i^2\\=\frac{n}{n-1} a_1^2+2\frac{1}{n-1}\sum_{k=1}^{i} \left ( i-k+1 \right )x_ka_1+2\frac{1}{n-1}\sum_{k=1}^{j} \left ( j-k+1 \right )y_ka_1 \ge 0 $$
$$(i,a_i)=A_i,调整过后A_1下降，A_2A_3...A_n沿着y轴方向整体上升\frac{1}{n-1}a_1,即调整过后的序列仍然是凸的$$
于是无妨设$a_1=0$;
$$引理 1^* 对任何 1 \leq i \leq j \leq n-1 , 有a_{i}+a_{j} \geq a_{i-1}+a_{j+1} .$$
$$引理 2 对任何 0 \leq i \leq m \leq j \leq n , 有a_{m} \geq \frac{(j-m) a_{i}+(m-i) a_{j}}{j-i} .$$
$$设 a_{k}, S_{1}, S_{2} 的定义同分析. 结合引理 1 , 通过配对不难证明\\k a_{k} \geq S_{1} \geq \frac{k+1}{2} a_{k},(n-k+1) a_{k} \geq S_{2} \geq \frac{n-k+1}{2} a_{k} .$$
$$故可取到最小正整数 i(1 \leq i \leq k) , 以及最大正整数 j(k \leq j \leq n) , 分别满足\\k a_{k}-\frac{i-1}{2} a_{k} \leq S_{1}, \frac{n+j+1}{2} a_{k}-k a_{k} \leq S_{2} .$$
$$对于 j \leq n-2 的情形. 我们令$$
$$b_{m}=\left\{\begin{array}{ll}
K_{1} m, & 0 \leq m \leq i-1 ; \\
a_{k}, & i \leq m \leq j ; \\
K_{2}(n-m), & j+1 \leq m \leq n .
\end{array}\right.$$
$i, j $ 的选取可以验证$ \left\{b_{m}\right\} $的确符合趧设条件, 且有
$$\sum_{i=1}^{k} b_{i}=\sum_{i=1}^{k} a_{i}, \sum_{i=k}^{n} b_{i}=\sum_{i=k}^{n} a_{i,} a_{k}=\max _{1 \leq i \leq n}\left\{a_{i}\right\}=b_{k}=\max _{1 \leq i \leq m}\left\{b_{i}\right\} .$$
$$并且 0=b_{b}<\cdots<b_{i-1} 构成等差数列, b_{i}, \cdots, b_{j} 构成常数列,\\ 而 \left.b_{j+1}>\cdots\right\rangle b_{n}=0 构成递减等差数列.$$
$$下面我们尝试证明 \sum_{i=1}^{n} b_{i}^{2} \geq \sum_{i=1}^{n} a_{i}^{2} .$$
注意到 $a_{k}=b_{k}$ , 因此只要分别证明
$$\sum_{i=1}^{k} b_{i}^{2} \geq \sum_{i=1}^{k} a_{i}^{2} \text { 以及 } \sum_{i=k}^{n} b_{i}^{2} \geq \sum_{i=k}^{n} a_{i}^{2}$$
即可.
$$取最大的正整数 l(1 \leq l \leq i-1) 使得 b_{l}<a_{l} (若这样的 l 不存在, 则必有 a_{m}=b_{m}, 1 \leq m \leq k ), \\下面我们证明: b_{m}<a_{m}, \forall 1 \leq m \leq l .$$
任取 $ 1 \leq m \leq l$ , 由引理 2 知
$$a_{m} \geq \frac{m a_{l}+(l-m) a_{0}}{l}=\frac{m a_{l}}{l} .$$
又由 $b_{0}, b_{1}, \cdots, b_{l} $成等差数列, 可知
$$b_{m}=\frac{m b_{l}+(l-m) b_{0}}{l}=\frac{m b_{l}}{l} .$$
因此由$ a_{l}>b_{l} 可知 a_{m}>b_{m}, \forall 1 \leq m \leq l .$
再由 l 最大性知, $b_{m} \geq a_{m}, \forall l+1 \leq m \leq k .$ 这样我们便推出: $$序列 \left\{b_{k}, b_{k-1}, \cdots, b_{1}\right\} 优超序列 \left\{a_{k}, a_{k-1}, \cdots, a_{1}\right\} . $$
$$从而由 Karamata 不等式立得到 \sum_{i=1}^{k} b_{i}^{2} \geq \sum_{i=1}^{k} a_{i}^{2} .$$
同理得另一个不等式. 因此在 $ j \leq n-2 时$, 我们成功得到了想要的情形
对于$ j=n-1, n $ 的情形, 类似上面的方法, $$可以将数列 \left\{a_{m}\right\} 调整为 0=b_{0}<\cdots<b_{i-1} 成等差数列, 而 b_{i}=\cdots=b_{n-1} \geq b_{n} 的情形.$$
因此我们只需 对这两种特粖情形证明结论即可. 我们可以证明, 这两种情形下均有
$$\left(\sum_{i=1}^{n} a_{i}\right)^{2}-\frac{3 n-\frac{3 n}{2 n-1}}{4} \sum_{i=1}^{n} a_{i}^{2} \geq 0 .$$
我们继续做一些简化, 例如 将第一种情况再化归到 $a_{0}, \cdots, a_{i-1}, a_{i} 成等差数列， a_{i}=\cdots=a_{j} , a_{j}, a_{j+1}, \cdots, a_{n} $ 也成等差数列的情形.
在以上基础上：
首先证明至多存在一个 $ j(2 \leq j \leq n-1)$ , 使得 $2 a_{j}>a_{j-1}+a_{j+1}$ . 假设不然, 则存在 $1<j_{1}<j_{2}<n $ 使得
$$2 a_{j_{1}}>a_{j_{1}-1}+a_{j_{1}+1} \text { 且 } 2 a_{j_{2}}>a_{j_{2}-1}+a_{j_{2}+1} .$$
考虑一个辅助数列$ \left\{\delta_{i}\right\}_{i=1}^{n} $ : 当 $ 1 \leq i \leq j_{1} $时 $\delta_{i}=i-1 $ ; 当 $j_{2} \leq i \leq n $ 时 $ \delta_{i}=\lambda(i-n) $(其中 $\lambda $ 是待定的正数); 当 $ j_{1}<i<j_{2} $时 $\delta_{i}=\frac{j_{2}-i}{j_{2}-j_{1}} \cdot \delta_{j_{1}}+\frac{i-j_{1}}{j_{2}-j_{1}} \cdot \delta_{j_{2}} $. 从几何角度来说, $ n 个点 \left(i, \delta_{i}\right) $ 连接成三个线段, 而拐点恰好出现在 $ i=j_{1}, j_{2} .$ 易知存在唯一的 $ \lambda$ 使得 $ \sum_{i} \delta_{i}=0 .$ 这时考虑两个数列 $a_{i}^{\prime}=a_{i}+\epsilon \cdot \delta_{i} 以 及 a_{i}^{\prime \prime}=a_{i}-\epsilon \cdot \delta_{i} ,$ 它们的和都等于 $ \frac{n(n-1)}{2}$ . 注意到数列 $ \left\{a_{i}\right\} $ 是凹的, 并且在 $ i= j_{1}, j_{2} $处是严格凹的. 而数列 $ \pm\left\{\delta_{i}\right\} $ 在 $ i \neq j_{1}, j_{2}$ 处是线性的, 所以对充分小的正 数$ \epsilon$ , 数列 $\left\{a_{i}^{\prime}\right\},\left\{a_{i}^{\prime \prime}\right\}$ 都是凹的. 又由于 $\delta_{1}=\delta_{n}=0, a_{1}^{\prime}=a_{1}^{\prime \prime}=a_{1}, a_{n}^{\prime}=a_{n}^{\prime \prime}=a_{n} $ 都是非负的. 由凹数列的性质, $ \left\{a_{i}^{\prime}\right\} 与 \left\{a_{i}^{\prime \prime}\right\} $都是非负的. 故 $\left\{a_{i}^{\prime}\right\},\left\{a_{i}^{\prime \prime}\right\} $ 都是符 合条件的数列, 但是
$$\sum_{i} a_{i}^{\prime 2}+\sum_{i} a_{i}^{\prime \prime 2}-2 \sum_{i} a_{i}^{2}=2 \epsilon^{2} \sum_{i} \delta_{i}^{2}>0,$$
与 $ \sum_{i} a_{i}^{2} $的最大性相矛盾!
所以我们证明了F取到最值时必然存在 $k(1 \leq k \leq n)$ , 使得$ a_{1}, a_{2}, \ldots, a_{k} $是 等差数列, 而 $a_{k}, a_{k+1}, \ldots, a_{n} $ 也是等差数列. 如果 $ k=1 或 k=n $, 那么 $ \left\{a_{i}\right\}$ 是单调的.
所以存在 $ 1<k<n$ 使得
$$a_{i}=\frac{i-1}{k-1} \cdot a_{k}, 1 \leq i \leq k \text {, 以及 } a_{i}=\frac{n-i}{n-k} \cdot a_{k}, k<i \leq n .$$
利用 $\sum_{i} a_{i}=\frac{n(n-1)}{2} 可知 a_{k}=n$ , 于是可以直接求出
$$\sum_{i} a_{i}^{2}=n^{2} \cdot\left(\sum_{i=1}^{k}\left(\frac{i-1}{k-1}\right)^{2}+\sum_{i=k+1}^{n}\left(\frac{n-i}{n-k}\right)^{2}\right)=\frac{n^{2}}{6} \cdot\left(2 n-2+\frac{1}{k-1}+\frac{1}{n-k}\right) .$$
由于$ \frac{1}{x}$ 是凸函数, 容易看出上面最右边的式子在 $ k=2 或 k=n-1 $ 时最 大. 最大值是 $$\frac{n^{2}}{6} \cdot\left(2 n-2+1+\frac{1}{n-2}\right)=\frac{n^{2}}{6} \cdot \frac{(n-1)(2 n-3)}{n-2} ,$$ 于是得证!
事实上，我们可以对上面“拐点数缩小"的验证中的n缩小成k，使得验证的序列成为原序列中一个连续的子列，通过一种比较怪异的归纳法（保证数列中的最大项在这个子列中，然后逐步扩大k至n)，这么反复归纳就可以得到我们的结论。
[b]一般情况[/b]
这一节我们证明定理 3 对一般的非负凹数列 $ \left\{a_{i}\right\},\left\{b_{i}\right\}$ 都成立.
不妨假设 $\sum_{i} a_{i}=\sum_{i} b_{i}=\frac{n(n-1)}{2} . $只需证明在这些条件下有
$$\sum_{i} a_{i} b_{i} \geq \frac{n-2}{2 n-1} \sum_{i} a_{i}^{2} .........(4)$$
如果 (4) 式成立, 那么对称地有
$$\sum_{i} a_{i} b_{i} \geq \frac{n-2}{2 n-1} \sum_{i} b_{i}^{2},$$
于是 (1) 式一定成立.
我们将$\sum_{i=1}^{n}a_i^2$取得最大值$\sum_{i=1}^{n}a_(k,i)^2$时 $a_i$的可以调整成的状态划分为以下几种情况：
$(i) a_{i}=i-1,1 \leq i \leq n ,$
$(ii) a_{i}=n-i, 1 \leq i \leq n $ 或者
$(iii) 存在 1<k<n 使得 a_{i}=\frac{i-1}{k-1} \cdot n, 1 \leq i \leq k , 以及 a_{i}=\frac{n-i}{n-k} \cdot n, k<i \leq n . $
上述三种情况仅用于$\sum_{i=1}^{n} a_i^2$的放缩,当$\sum_{i=1}^{n} a_i^2在(i)(ii)\left ( iii \right )$ 的情况下取得最大值，那么左边的式子可以微微调整$\min \left \{ b_i \right \} \min \left \{ a_i \right \}$，使得左边和的项的首与末项为零
具体如下：
先考虑前两种(对称的)情况, 此时只要证明
$$\sum_{i=1}^{n}(i-1) b_{i} \geq \frac{n(n-1)(n-2)}{6} . $$
由于左边是 $ b_{i} $ 的线性和, 我们可以再用调整法使得数列 $ \left\{b_{i}\right\} $也属于上面三种情 况之一, 详见角注. $ { }^{1} $
如果 $ b_{i}=i-1 $, $\sum_{i} a_{i} b_{i}=\frac{n(n-1)(2 n-1)}{6} $ . 如果 $ b_{i}=n-i, \sum_{i} a_{i} b_{i}=\frac{n(n-1)(n-2)}{6} $ . 最后假设数列 $ \left\{b_{i}\right\} $ 属于情况 $(iii) $, 此时我们将 $ 2 \sum_{i} a_{i} b_{i} \geq \frac{n(n-1)(n-2)}{3} $改写为
$$\sum_{i}\left(a_{i}+b_{i}\right)^{2} \geq \sum_{i} a_{i}^{2}+\sum_{i} b_{i}^{2}+\frac{n(n-1)(n-2)}{3}, $$
也就是
$$\begin{aligned}
\sum_{i}\left(a_{i}+b_{i}-n+1\right)^{2} & \geq \sum_{i} a_{i}^{2}+\sum_{i} b_{i}^{2}-\frac{n(n-1)(2 n-1)}{3} \\
& =\sum_{i} b_{i}^{2}-\frac{n(n-1)(2 n-1)}{6} .
\end{aligned}$$
由于$ a_{1}=b_{1}=0,(5) $式左边至少是$ (n-1)^{2}$ . 而由引理 5, (5) 式右边至多是
$$\frac{n^{2}(n-1)(2 n-3)}{6(n-2)}-\frac{n(n-1)(2 n-1)}{6}=\frac{n(n-1)^{2}}{3(n-2)} \leq(n-1)^{2} .$$
故定理成立.
最后假设 $ \left\{a_{i}\right\} $属于情况(iii). 由引理 5 知 (4) 式的右边至多是 $\frac{n^{2}(n-1)(2 n-3)}{6(2 n-1)}$ . 于是只要证明 $2 \sum_{i} a_{i} b_{i} \geq \frac{n^{2}(n-1)(2 n-3)}{3(2 n-1)} $, 即
$$\sum_{i}\left(a_{i}+b_{i}-n\right)^{2} \geq \sum_{i} a_{i}^{2}+\sum_{i} b_{i}^{2}+\frac{n^{2}(n-1)(2 n-3)}{3(2 n-1)}-n^{2}(n-2) .$$
如果 $\left\{b_{i}\right\} $ 属于情况 $(iii)$, 那么 $ a_{1}=b_{1}=a_{n}=b_{n}=0 $. 此时 (6) 式左边至少 是 $2 n^{2} .$ 而由引理 (5) 可知 (6) 式右边至多是
$$\frac{n^{2}(n-1)(2 n-3)}{3(n-2)}+\frac{n^{2}(n-1)(2 n-3)}{3(2 n-1)}-n^{2}(n-2)=n^{2} \cdot \frac{2 n^{2}-4 n+1}{(n-2)(2 n-1)} \leq 2 n^{2} .$$
${}^1$具体来说, 我们可以取数列$ \left\{b_{i}\right\} $使得 $\sum_{i} a_{i} b_{i} $ 最大, 并在此条件下要求满足 $ 2 b_{j}>b_{j-1}+b_{j+1} 的下标 j $ 最少(称这样的下标为 “拐点”). 如果还有多个数列则尽量要求 $ b_{1}, b_{n} $ 等于零. 同 引理 5 的证明, 至多有一个下标 $ j $ 使得 $2 b_{j}>b_{j-1}+b_{j+1}$ . 否则 $ \left\{b_{i} \pm \epsilon \delta_{i}\right\} $ 也符合条件, 并 且 $$ \sum_{i} a_{i}\left(b_{i}+\epsilon \delta_{i}\right)+\sum_{i} a_{i}\left(b_{i}-\epsilon \delta_{i}\right)=2 \sum_{i} a_{i} b_{i}$$ (辅助数列 $ \delta_{i} $同引理 5 的证明). 那样由最大性得 到$$ \sum_{i}^{i} a_{i}\left(b_{i} \pm \epsilon \delta_{i}\right)=\sum_{i}^{i} a_{i} b_{i} $$. 然而通过取适当的 $\epsilon $可以使得$ \left\{b_{i} \pm \epsilon \delta_{i}\right\}$ 中的一个数列比$ \left\{b_{i}\right\} $ 少 一个拐点, 与我们选取 $ \left\{b_{i}\right\} $的方法矛盾! 于是 $ \left\{b_{i}\right\} $要么是单调的, 要么只有一个拐点. 如果单 调, 我们可以用同样方法进一步证明$ b_{1}=0 或者 b_{n}=0$ , 于是 $b_{i}=i-1 $ 或者 $b_{i}=n-i $. 如 果 $2 b_{k}>b_{k-1}+b_{k+1} $ 是一个拐点, 则可以证明 $ b_{1}=b_{n}=0 $ . 否则对适当的 $ \epsilon $ , 数列 $\left\{b_{i} \pm \epsilon \delta_{i}\right\} $ 也 达到最大值, 并且要么少一个拐点, 要么在 $ b_{1}, b_{n} $处多一个零.如果 $ \left\{b_{i}\right\} $ 属于情况 (i) 或 (ii), 那么 (6) 式左边至少是 $n^{2} $. 而由引理 4 和引 理 5 可知 (6) 式右边至多是
$$\begin{aligned}
& \frac{n^{2}(n-1)(2 n-3)}{6(n-2)}+\frac{n(n-1)(2 n-1)}{6}+\frac{n^{2}(n-1)(2 n-3)}{3(2 n-1)}-n^{2}(n-2) \\
= & n^{2}-\frac{n(n-1)\left(2 n^{2}-6 n+1\right)}{3(n-2)(2 n-1)} \leq n^{2} .
\end{aligned}$$
故无论如何 (6) 式都成立, 我们也就完成了定理 3 的证明!
到此结束，谢谢观看
