# prove $\sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j}\ge \frac{2}{n}-\frac{1}{n^2}$

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?

• The right-hand side is $1-\left(1-\frac{1}{n}\right)^2$, so maybe subtract the left-hand side from $1=\sum_{i=1}^{n}{x_i}$? This is not a hint, just looking for possible approaches. Sep 24, 2022 at 3:50
• You need $x_1\neq 0$ for the left side of the inequality to even be defined... Sep 24, 2022 at 4:12
• it looks like inequality can hold $n=2$ and all variables are equal, otherwise equality is attained in some weird combination. Also, this is a quadratic in $x_n$, so finding the discriminant might directly yield the problem if expanded careful enough. Sep 24, 2022 at 4:13
• if you construct positive variables $a_2, a_3,\dots a_n$ such that you use AM-GM as: $$\dfrac{x_i^2}{x_1+x_2+\dots +x_i}\geq 2a_ix_i- a_i^2(x_1+x_2+\dots +x_i)$$ and then you add all of them together to get the coefficients $\dfrac{2n-1}{n^2}$ in front of each of $x_1,x_2,\dots x_{n-1},$ the coefficient in front of $x_n$ will be larger than $\dfrac{2n-1}{n^2}$, which finishes the problem. But this is a pain the ass to write out in detail. Sep 24, 2022 at 4:46
• FWIW, the lower bound $2/n-1/n^2$ isn't tight when $n \ge 3$. Computing the minimum of the sum over all non-negative $x_i$ that sum to 1 for small $n$ suggests that this minimum is $b_1 = 1$ and $b_n = 1 - (1-b_{n-1}/2)^2$ for all $n > 1$. Sep 24, 2022 at 7:37

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.

• +1. I was thinking exactly this once I realized the whole thing is a quadratic in $x_n.$ Sep 24, 2022 at 20:48
• @dezdichado Thanks. For your idea in comment, we can obtain $a_2 = 1/2$, $a_{i+1} = \frac12f(a_i)$ for $i=2, 3, \cdots, n-2$, and $a_n = \sqrt{f(a_{n-1}) - (2n-1)/n^2}$ where $f(u) = 2u - u^2$. Perhaps there are no closed form. Sep 24, 2022 at 23:21
• yeah for $n=3,4$ I manually checked but there was no closed form for the last $a_n$ Sep 24, 2022 at 23:31
• @dezdichado Also, I evaluated the minimum for small $n$ in which the minimum is attained when $\frac{x_2}{x_1} \approx 1$, $\frac{x_{k+1}}{x_k} \approx \frac{k+4}{k+3}$ for $k=2, 3, \cdots, n-1$, that is $x_1 \approx \frac{10}{n^2+7n+2}$ and $x_k = \frac{2(k+3)}{n^2+7n+2}$ for $k\ge 2$. Not sure if it is the case for large $n$. Sep 24, 2022 at 23:32
• @dezdichado For $n=3, 4$, all $a_i$'s should be found in closed form, right? Do you do something like $$\sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j} \ge x_1 + \sum_{i=2}^n \left(2y_i x_i - y_i^2 \sum_{j=1}^i x_j\right) =\left(1 - \sum_{i=2}^n y_i^2\right)x_1 + \sum_{k=2}^n \left(2y_k - \sum_{i=k}^n y_i^2\right)x_k?$$ Let $c_i$ be the coefficients of $x_i$ for $i=1, 2, \cdots, n$. We do $c_1 - c_2, ~ c_2 - c_3, ~ \cdots, ~ c_{n-1} - c_n$ to solve $a_i$'s. Sep 24, 2022 at 23:37

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 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.

• "And now for the step..." But $\sum_{i=1}^n x_i<1,$ so you can't use the induction step. Your argument would say that the left side is always more than $1.$ Sep 24, 2022 at 13:41
• But how is $\sum_{i=1}^n x_i<1$ as it is given that 'Let $x_1,x_2,⋯,x_n$ be $n$ non-negative numbers such that $x_1+x_2+⋯+x_n=1$' Sep 24, 2022 at 16:30
• You are trying to prove it for $n+1,$ so now $\sum_{i=1}^{n+1} x_i=1.$ That means $\sum_{i=1}^n x_i=1$ only when $x_{n+1}=0.$ Sep 24, 2022 at 18:06