1
$\begingroup$

Prove that:

$ \rightarrow\sum_{k=1}^n f(\frac{k}{n})\sum_{k=1}^n k{f(\frac{k}{n})}^2\le\sum_{k=1}^n kf(\frac{k}{n})\sum_{k=1}^n{f(\frac{k}{n})}^2 $

Given $f(x)$ is a positive function and also monotonic decreasing function.

  • 0
    write it down for all permutations and sum over the permuations, and it gives the correaltion inequality.2012-10-23

1 Answers 1

3

Denote $a_k=f\left(\frac{k}{n}\right).$
(Proof by induction). Let $P(n)$ be the statement $\sum\limits_{k=1}^n f\left(\frac{k}{n}\right)\sum\limits_{k=1}^n k\left(f\left(\frac{k}{n}\right)\right)^2\leqslant\sum\limits_{k=1}^n kf\left(\frac{k}{n}\right)\sum\limits_{k=1}^n\left(f\left(\frac{k}{n}\right)\right)^2$ or, in shorter form $\sum\limits_{k=1}^n a_k\sum\limits_{k=1}^n ka_k^2\leqslant\sum\limits_{k=1}^n ka_k\sum\limits_{k=1}^na_k^2.$

  1. (Basis) For $n=1$ we have: $a_1\cdot a_1= a_1\cdot a_1$
  2. (Induction step). We assume that $P(n)$ is true and prove that $P(n+1)$ is true. For LHS of $P(n+1)$: \begin{equation} \sum\limits_{k=1}^{n+1} a_k\sum\limits_{k=1}^{n+1} ka_k^2 = \left(\sum\limits_{k=1}^{n} a_k +a_{n+1} \right) \left(\sum\limits_{k=1}^{n} k a_k^2 + (n+1) a_{n+1}^2 \right)=\\ \sum\limits_{k=1}^{n} a_k\sum\limits_{k=1}^{n} ka_k^2 + (n+1)a_{n+1}^2 \sum\limits_{k=1}^{n} a_k + a_{n+1} \sum\limits_{k=1}^{n} ka_k^2 + (n+1)a_{n+1}^3 \leqslant \\ \sum\limits_{k=1}^n ka_k\sum\limits_{k=1}^na_k^2 + (n+1)a_{n+1}^2 \sum\limits_{k=1}^{n} a_k + a_{n+1} \sum\limits_{k=1}^{n} ka_k^2 + (n+1)a_{n+1}^3\overset{def}{=} A. \end{equation} RHS of $P(n+1)$ equals: \begin{equation}\sum\limits_{k=1}^{n+1} ka_k\sum\limits_{k=1}^{n+1} a_k^2 = \left(\sum\limits_{k=1}^{n} ka_k + (n+1)a_{n+1}\right)\left(\sum\limits_{k=1}^{n} a_k^2 + a_{n+1}^2 \right) = \\ \sum\limits_{k=1}^n ka_k\sum\limits_{k=1}^na_k^2 + (n+1)a_{n+1}\sum\limits_{k=1}^{n} a_k^2 +a_{n+1}^2\sum\limits_{k=1}^{n} ka_k + (n+1)a_{n+1}^3\overset{def}{=} B. \end{equation} Next, \begin{equation} A-B= \left((n+1)a_{n+1}^2 \sum\limits_{k=1}^{n} a_k + a_{n+1} \sum\limits_{k=1}^{n} ka_k^2 \right) - \\ \left( (n+1)a_{n+1}\sum\limits_{k=1}^{n} a_k^2 +a_{n+1}^2\sum\limits_{k=1}^{n} ka_k \right) = \\ (n+1)a_{n+1} \left(a_{n+1}\sum\limits_{k=1}^{n} a_k -\sum\limits_{k=1}^{n} a_k^2 \right) + a_{n+1} \left(\sum\limits_{k=1}^{n} ka_k^2 - a_{n+1}\sum\limits_{k=1}^{n} k a_k \right)=\\ a_{n+1}^2 \sum\limits_{k=1}^{n} \left((n+1)a_k -k a_k \right) + a_{n+1}\sum\limits_{k=1}^{n} \left(k a_k^2 - (n+1)a_k^2 \right)=\\ a_{n+1}^2 \sum\limits_{k=1}^{n} {a_k(n+1-k)} - a_{n+1} \sum\limits_{k=1}^{n} {a_k^2(n+1-k)}=\\ a_{n+1} \sum\limits_{k=1}^{n} \left(a_{n+1}a_k (n+1-k) - {a_k^2(n+1-k)} \right)=\\ a_{n+1} \sum\limits_{k=1}^{n}{(n+1-k)(a_{n+1}a_k - a_k^2)}=\\ a_{n+1} \sum\limits_{k=1}^{n}{(n+1-k)a_k(a_{n+1} - a_k)}<0 \end{equation} since $\{a_k \}$ decreases.