solution: http://tieba.baidu.com/p/2233235567

any other elementary proofs?

offical solution: First,open it up. we get $RHS=\frac{4}{45}\sum_{i,j}\binom{n}{i}\binom{n}{j}a_ia_j$ $LHS=\sum_{i,j}a_ia_j(\frac{1}{n}\sum_{k=0}^{n-1}\binom{k}{i}\binom{k}{j}-\frac{1}{n^2} \binom{n+1}{i+1}\binom{n+1}{j+1} )$ Then prove $\frac{1}{n}\sum_{k=0}^{n-1}\binom{k}{i}\binom{k}{j}-\frac{1}{n^2} \binom{n+1}{i+1}\binom{n+1}{j+1} \le \frac{4}{45}\binom{n}{i}\binom{n}{j}$ use a inequality $\frac{\binom{k}{i}\binom{k}{j}}{\binom{n}{i}\binom{n}{j}} \le (\frac{k}{n})^{i+j}$ then we need to prove $\frac{1}{n}\sum_{k \ge max {i,j} }^{n-1}(\frac{k}{n})^{i+j}-\frac{1}{n^2} \frac{n+1}{i+1}\frac{n+1}{j+1} \le \frac{4}{45}$ and $\sum_{1}^{n-1}k^{i+j}\le \frac{n^{i+j+1}}{i+j+1}$ then $LHS \le \frac{1}{i+j+1}-\frac{1}{i+1}\frac{1}{j+1}$ then prove $\frac{1}{i+j+1}-\frac{1}{i+1}\frac{1}{j+1}\le \frac{4}{45}$ which is easy Also, after opening up the inequality, it's sufficient to prove it for all $ai_^2$

duanby, could you write your solution with more detail please. It looks wonderful though!

First, the RHS becomes $$\sum_{n \ge i,j \ge 1} a_ia_j \frac{4}{45} \binom{n}{i} \binom{n}{j}$$and the LHS becomes $$\sum_{n \ge i,j \ge 0}a_ia_j \left(\frac{1}{n}\sum_{k=0}^{n-1}\binom{k}{i}\binom{k}{j}-\frac{1}{n^2} \binom{n+1}{i+1}\binom{n+1}{j+1} \right).$$Consider a summand on the LHS. If one of $i,j$ is $0,$ then assume WLOG it is $i.$ Then $$\frac{1}{n} \sum_{k=0}^{n-1}\binom{k}{j}-\frac{1}{n^2} \binom{n+1}{1}\binom{n+1}{j+1}=\frac{1}{n} \binom{n}{j+1}-\frac{n+1}{n^2} \binom{n+1}{j+1} $$which is less than $0.$ So we can neglect terms on the LHS where one of $i,j$ is $0.$ It suffices to prove the inequality $$\sum_{n \ge i,j \ge 1}a_ia_j \left(\frac{1}{n}\sum_{k=0}^{n-1}\binom{k}{i}\binom{k}{j}-\frac{1}{n^2} \binom{n+1}{i+1}\binom{n+1}{j+1} \right) \le \sum_{n \ge i,j \ge 1} a_ia_j \times \frac{4}{45} \binom{n}{i} \binom{n}{j}.$$We compare corresponding summands together: it clearly suffices to prove \begin{align*} \frac{1}{n} \times \sum_{k=0}^{n-1}\frac{\binom{k}{i}\binom{k}{j}}{\binom{n}{i} \binom{n}{j}}-\frac{(n+1)^2}{n^2 (i+1)(j+1)} \le \frac{4}{45} \end{align*}for all integers $1 \le i,j \le n,$ and this is actually true. We have \begin{align*} \frac{1}{n} \sum_{k=0}^{n-1}\frac{\binom{k}{i}\binom{k}{j}}{\binom{n}{i} \binom{n}{j}}-\frac{(n+1)^2}{n^2 (i+1)(j+1)} &\le \frac{1}{n} \sum_{k=0}^{n-1}\frac{\binom{k}{i}\binom{k}{j}}{\binom{n}{i} \binom{n}{j}}-\frac{1}{(i+1)(j+1)} \\ &= \frac{1}{n} \sum_{k=0}^{n-1}\frac{(k \times \cdots \times (k-i+1))(k \times \cdots \times (k-j+1))}{(n \times \cdots \times (k-i+1))(n \times \cdots\times (n-j+1))}-\frac{1}{(i+1)(j+1)} \\ &\le \frac{1}{n} \sum_{k=0}^{n-1}\frac{k^{i+j}}{n^{i+j}}-\frac{1}{(i+1)(j+1)} \\ &= \frac{1}{n^{i+j+1}} \sum_{k=0}^{n-1} k^{i+j}-\frac{1}{(i+1)(j+1)} \\ &\le \frac{1}{i+j+1} - \frac{1}{(i+1)(j+1)}, \end{align*}where we have used the inequality $\sum_{k=1}^{n-1}k^{i+j}\le \frac{n^{i+j+1}}{i+j+1}$ which may be verified easily by induction. To finish, see $$\frac{1}{i+j+1} - \frac{1}{(i+1)(j+1)} \le \frac{1}{i+j+1} - \frac{1}{(\frac{i+j}{2}+1)(\frac{i+j}{2}+1)}$$and since $i+j$ is an integer the RHS cannot be $>\frac{4}{45}$ unless $i+j = 3$ (just treat $i+j$ as a single variable and the rest is just busy work), but manually verifying $(i,j) = (1,2)$ shows that even though the bound of $\frac{4}{45}$ on the RHS doesn't hold in this case, the bound on the LHS will still hold finishing all cases. $\square$ Funny anecdote: When I first saw this problem it was on the AoPS Wiki "Competition ratings" page (listed as a supposedly "9.5-10" difficulty problem), and at that time it was one of the scariest problems I'd ever seen. Now it doesn't seem so bad (it seems really weak). Maybe replace it?