背景
来自于我在CMO考试之前的一道模拟第三题，拼尽全力无法战胜。看了解答才发现这里使用了很多分析学的技巧，无论是在高中竞赛还是在分析学学习中都有很深的意义，目前是我最喜欢的高中数学竞赛代数问题之一，故写文章。
问题
无限大的平面方格表的每个格子里写有一个非负实数，满足对任意i , j ∈ Z i,j \in \mathbb{Z} i , j ∈ Z
a i , j = a i + 1 , j + a i , j + 1 . a_{i,j}=a_{i+1,j}+a_{i,j+1}.
a i , j = a i + 1 , j + a i , j + 1 .
证明： 对任意i , j ∈ Z i,j\in \mathbb{Z} i , j ∈ Z k k k
a i , j 2 ≤ a i − k , j + k ⋅ a i + k , j − k . a_{i,j}^{2}\le a_{i-k,j+k}\cdot a_{i+k,j-k}.
a i , j 2 ≤ a i − k , j + k ⋅ a i + k , j − k .
分析
首先注意到问题是有非平凡取等的，当a i , j = ( q + 1 ) − ( i + j ) ⋅ q i a_{i,j}=(q+1)^{-(i+j)}\cdot q^{i} a i , j = ( q + 1 ) − ( i + j ) ⋅ q i k = 1 k=1 k = 1
容易注意到或者猜测，a i , j a_{i,j} a i , j
结合题目条件，我们可以猜测题目条件是用来将要证的不等式放在极远的区域，这样比较容易在0上作较松的放缩而不导致问题。并且我们倾向于在同一个等级（即i + j i+j i + j
此外不等式存在取等也成为严重的问题，这导致我们所能作出的放缩必须是无损的，但是右侧多出的两端项在左侧完全无法涉及，但却不能直接放缩成0。并且如果我们没有改变要证式的方法，那么要证明此题的唯一办法是找出满足条件的一组{ a i , j } \{a_{i,j}\} { a i , j }
这样的方法的确存在。我们介绍一个方法an epsilon of room，这个方法实为数学分析中的技巧：我们可以将不等号的较小一侧添加( 1 − ε ) (1-\varepsilon) ( 1 − ε ) a i , j a_{i,j} a i , j ε \varepsilon ε
这样的放缩和原式是等价的，我们已经解决了一个问题。但是乘积形式会导致证明冗长而复杂，对这部分作正定性判断也有些天方夜谭。注意到条件实则为若干个一次恒等式，故而我们十分希望把二次形式改写成一次形式，这样不仅能改善配方的困难——事实上更进一步，我们只需要在意每个a i , j a_{i,j} a i , j
这是否可以做到？可以。我们仍然有一个方法bound relax（这名字是我起的），办法是引入一组新的变量，使得不等号的一侧可以作为常量通过这一组新变量的方式保证大小的情况下放缩成一个合适的形式，且可以仅通过改变新变量的方式取等。比如在本题中：我们希望不等式变为一次，事实上相当于将不等号右侧变为X 2 X^2 X 2 X X X
这样完美地解决了我们所面临的两个问题，剩下的步骤便是熟练的套路化工作：取出上述我们需求的变量，将所需证明作充分大次展开，将相同的系数放在一起，剩下的不等式是容易的。下面撰写过程。
解答
注意到只需要解决k=1的情形.ε , u v = 1 4 , \varepsilon,uv=\frac{1}{4}, ε , uv = 4 1 , ( 1 − ε ) a i , j ≤ u ⋅ a i − 1 , j + 1 + v ⋅ a i + 1 , j − 1 . (1-\varepsilon)a_{i,j}\le u\cdot a_{i-1,j+1}+v\cdot a_{i+1,j-1} . ( 1 − ε ) a i , j ≤ u ⋅ a i − 1 , j + 1 + v ⋅ a i + 1 , j − 1 . i , j ∈ Z i,j\in \mathbb{Z} i , j ∈ Z a i , j = ∑ k = 0 n ( n k ) a i + k , j + n − k . a_{i,j}=\sum_{k=0}^{n}\binom{n}{k}a_{i+k,j+n-k}. a i , j = ∑ k = 0 n ( k n ) a i + k , j + n − k .
0 ≤ u ⋅ a i − 1 , j + 1 + v ⋅ a i + 1 , j − 1 − ( 1 − ε ) a i , j = u ∑ k = 0 n ( n k ) a i − 1 + k , j + 1 + n − k + v ∑ k = 0 n ( n k ) a i + 1 + k , j − 1 + n − k − ( 1 − ε ) ∑ k = 0 n ( n k ) a i + k , j + n − k = u ⋅ a i − 1 , j + n + 1 + v ⋅ a i + n + 1 , j − 1 + ∑ k = 0 n ( u ( n k + 1 ) + v ( n k − 1 ) − ( 1 − ε ) ( n k ) ) a i + k , j + n − k . \begin{aligned}
0&\le u\cdot a_{i-1,j+1}+v\cdot a_{i+1,j-1}-(1-\varepsilon)a_{i,j}\newline
&=u\sum_{k=0}^{n}\binom{n}{k}a_{i-1+k,j+1+n-k}+v\sum_{k=0}^{n}\binom{n}{k}a_{i+1+k,j-1+n-k}-(1-\varepsilon)\sum_{k=0}^{n}\binom{n}{k}a_{i+k,j+n-k}\newline
&=u\cdot a_{i-1,j+n+1}+v\cdot a_{i+n+1,j-1}+\sum_{k=0}^{n}(u\binom{n}{k+1}+v\binom{n}{k-1}-(1-\varepsilon)\binom{n}{k})a_{i+k,j+n-k}.
\end{aligned}
0 ≤ u ⋅ a i − 1 , j + 1 + v ⋅ a i + 1 , j − 1 − ( 1 − ε ) a i , j = u k = 0 ∑ n ( k n ) a i − 1 + k , j + 1 + n − k + v k = 0 ∑ n ( k n ) a i + 1 + k , j − 1 + n − k − ( 1 − ε ) k = 0 ∑ n ( k n ) a i + k , j + n − k = u ⋅ a i − 1 , j + n + 1 + v ⋅ a i + n + 1 , j − 1 + k = 0 ∑ n ( u ( k + 1 n ) + v ( k − 1 n ) − ( 1 − ε ) ( k n ) ) a i + k , j + n − k .
这只需证求和号内每一项的系数均大于0,即
∀ k ∈ { 0 , 1 , … , n } , ( n k ) ( u ⋅ n − k k + 1 + v ⋅ k n − k + 1 − ( 1 − ε ) ) ≥ 0 ⟺ ( n + 1 ) ⋅ ( u k + 1 + v n − k + 1 ) − ( 1 − ε ) − u − v ≥ 0 ← ( n + 1 ) ⋅ ( u + v ) 2 n + 2 − ( u + v ) 2 + ε ≥ 0 ( ∵ u v = 1 4 a n d C a u c h y . ) \begin{aligned}
&\forall k\in\{0,1,\dots,n\},\binom{n}{k}\left( u\cdot \frac{n-k}{k+1}+v\cdot\frac{k}{n-k+1}-(1-\varepsilon) \right)\ge 0 \newline
&\iff (n+1)\cdot\left( \frac{u}{k+1} +\frac{v}{n-k+1}\right)-(1-\varepsilon)-u-v\ge 0 \newline
&\gets \frac{(n+1)\cdot(\sqrt{ u }+\sqrt{ v })^{2}}{n+2}-(\sqrt{ u }+\sqrt{ v })^{2}+\varepsilon\ge 0\left( \because uv=\frac{1}{4} and\ Cauchy. \right)\newline
\end{aligned}
∀ k ∈ { 0 , 1 , … , n } , ( k n ) ( u ⋅ k + 1 n − k + v ⋅ n − k + 1 k − ( 1 − ε ) ) ≥ 0 ⟺ ( n + 1 ) ⋅ ( k + 1 u + n − k + 1 v ) − ( 1 − ε ) − u − v ≥ 0 ← n + 2 ( n + 1 ) ⋅ ( u + v ) 2 − ( u + v ) 2 + ε ≥ 0 ( ∵ uv = 4 1 an d C a u c h y . )
在n充分大时成立。得证！
