Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $x_1,x_2,\cdots,x_n$ be $n$ non-negative numbers such that $x_1+x_2+\cdots+x_n=1$. Show $$\sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j}\ge \frac{2}{n}-\frac{1}{n^2}.$$
We may consider using Cauchy. That is
$$\sum_{i=1}^n\sum_{j=1}^i x_j\cdot \sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j}\ge \left(\sum_{i=1}^nx_i\right)^2=1.$$
How to go on?
Fact 1: Let $n \ge 2$. Let $x_1, x_2, \cdots, x_n \ge 0$ and $x_1 > 0$. Then $$\sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j} \ge \frac{2n - 1}{n^2}(x_1 + x_2 + \cdots + x_n).$$ (The proof is given at the end.)
By Fact 1, we are done.
Proof of Fact 1:
We use Mathematical Induction.
It is easy to verify the case $n = 2$.
Assume that it is true for $n$.
For $n+1$, by the inductive hypothesis, we have \begin{align*} \sum_{i=1}^{n+1} \frac{x_i^2}{\sum_{j=1}^i x_j} &= \sum_{i=1}^{n} \frac{x_i^2}{\sum_{j=1}^i x_j} + \frac{x_{n+1}^2}{\sum_{j=1}^{n+1} x_j}\\ &\ge \frac{2n - 1}{n^2}(x_1 + x_2 + \cdots + x_n) + \frac{x_{n+1}^2}{\sum_{j=1}^{n+1} x_j}. \end{align*} It suffices to prove that $$\frac{2n - 1}{n^2}(x_1 + x_2 + \cdots + x_n) + \frac{x_{n+1}^2}{\sum_{j=1}^{n+1} x_j} \ge \frac{2n+1}{(n+1)^2}(x_1 + x_2 + \cdots + x_{n+1}).$$ Since the inequality is homogeneous, assume that $x_1 + x_2 + \cdots + x_n = 1$. Letting $y = x_{n+1}$, it suffices to prove that $$\frac{2n - 1}{n^2} + \frac{y^2}{1+y} \ge \frac{2n+1}{(n+1)^2}(1 + y)$$ or $$n^4y^2 + (-2n^3 + n^2 - 1)y + 2n^2 - 1 \ge 0$$ which is true (easy).
We are done.
We'll assume $x_1>0,$ since the left hand side is undefined if $x_1=0.$ But if ww treat the first term as zero when $x_1=0,$ we can just use that the right side is decreasing on $n.$
Try induction on $n.$ When $n=1,$ you have $x_1=1,$ the inequality becomes $1\geq 1.$
If true for $n,$ take $x_1,\dots,x_{n+1}.$
Since $x_{1}>0,$ then the $x_{n+1}<1.$
Let $y_i=\frac{x_i}{1-x_{n+1}}$ for $i=1,\dots,n.$
Then $\sum_1^n y_i=1,$ so we have:
$$\frac2n-\frac1{n^2}\leq \sum_{i=1}^n \frac{y_i^2}{\sum_{j=1}^i y_j}=\frac1{1-x_{n+1}}\sum_{i=1}^n\frac{x_i^2}{\sum_{j=1}^i x_j}$$
So $$\begin{align}\sum_{i=1}^{n+1}\frac{x_i^2}{\sum_{j=1}^i x_j}&\geq (1-x_{n+1})\left(\frac2n-\frac1{n^2}\right)+x_{n+1}^2\\\end{align}$$
In general, the minimum value for $f(x)=(1-x)a+x^2$ when $0<a\leq 1$ and $x\in [0,1]$ is at $x=a/2$ and the value is $a-\frac{a^2}{4}=1-(1-a/2)^2.$
So this is the recursion for the absolute minimum value of the left hand side:
$$m_1=1, m_{n+1}=\inf_{m\in[m_n,1]}1-(1-m/2)^2=1-(1-m_n/2)^2.$$
Because $1-(1-u/2)^2=u-\frac{u^2}4$ is increasing on $[0,1].$ We have, if $m_n\geq \frac2n-\frac1{n^2}$ then:
$$\begin{align}m_{n+1}&\geq 1-\left(1-\frac 1n+\frac1{2n^2}\right)^2\end{align}$$
Now, $$\frac2{n+1}-\frac1{(n+1)^2}=1-\left(1-\frac1{n+1}\right)^2$$
So you need $$\frac1{n+1}\leq \frac1{n}-\frac1{2n^2}=\frac{2n-1}{2n^2}$$
or $$2n^2\leq (n+1)(2n-1)=2n^2+n-1$$ which is obviously true for $n\geq1.$
Base Case:- $n=1$
$$\sum_{i=1}^1 \frac{x_i^2}{\sum_{j=1}^i x_j}\ge \frac{2}{1}-\frac{1}{1^2}$$
$$1 \ge 1$$
Thus the base case holds.
Hypothesis:-
$$\sum_{i=1}^{n+1} \frac{x_i^2}{\sum_{j=1}^i x_j}\ge \frac{2}{n+1}-\frac{1}{{(n+1)}^2}$$
And now for the step:-
$$\sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j} + \frac{x_{n+1}^2}{\sum_{j=1}^{n+1} x_j}\ge \frac{2}{n}-\frac{1}{n^2} + \frac{x_{n+1}^2}{\sum_{j=1}^{n+1} x_j}$$
$$\sum_{i=1}^{n+1} \frac{x_i^2}{\sum_{j=1}^i x_j} \ge \frac{2}{n}-\frac{1}{n^2} + \frac{x_{n+1}^2}{1}$$
This is as $x_1+x_2+\cdots+x_n+x_{n+1}=1$
As $n \ge 1$ so:-
$$2n^2\ge1$$
$$\Rightarrow 2n(n+1)\ge2n+1$$
$$\Rightarrow 2 \ge \frac{2n+1}{n(n+1)}$$
$$\Rightarrow 2\cdot\left[\frac{1}{n(n+1)}\right] \ge \frac{2n+1}{n^2(n+1)^2}$$
$$\Rightarrow 2\cdot\left[\frac{1}{n} - \frac{1}{n+1}\right]\ge \frac{1}{n^2}-\frac{1}{(n+1)^2}$$
$$\Rightarrow\frac{2}{n}-\frac{1}{n^2}\ge \frac{2}{n+1} -\frac{2}{(n+1)^2} $$
$$\Rightarrow\frac{2}{n}-\frac{1}{n^2} + x_{n+1}^2\ge \frac{2}{n+1} -\frac{1}{(n+1)^2} $$
This is as $x_{n+1}$ is non-negative.
Thus we finally get:-
$$\sum_{i=1}^{n+1} \frac{x_i^2}{\sum_{j=1}^i x_j} \ge \frac{2}{n}-\frac{1}{n^2} + x_{n+1}^2\ge \frac{2}{n+1} -\frac{1}{(n+1)^2} $$
completing the step.
