Ineqality problem My mentor gave this problem to our class. later on he also told the solution to the problem.but i did not understood the solution as it was done in a very complicated way. so can anyone help me the solve this problem with proper explanation
$$
x_1\geqslant x_2\geqslant x_3\geqslant...\geqslant x_n ....$$
$$\text{where }  x_i \in \mathbb{R}
$$
such that for $n\geqslant1$ ;
$$\frac{x_1}{1}+\frac{x_4}{2}+\frac{x_9}{3}+...+\frac{x_{n^2}}{n}\leqslant1$$
Then PROVE that
for $k\geqslant1$;
$$\frac{x_1}{1}+\frac{x_2}{2}+\frac{x_3}{3}+...+ \frac{x_k}{k}\leqslant3
$$
 A: Let's try to prove by induction that $\sum_{i=1}^{k} \dfrac{x_i}{i} \leq 3-f(k)$ for some suitable function $f(k) \geq 0$.
Let's consider the induction step.
We want to prove: $\dfrac{x_k}{k} \leq f(k-1)-f(k)$ for a suitable function $f$.
Thus, we need an upper bound for $x_k/k$. For this, let's use the given information.
We obtain: $x_{n^2}H_n \leq 1$, where $H_n=\sum_{i=1}^{n}\dfrac{1}{i}$.
Consider the function $A_n=\sum_{t=n+1}^{\infty} \dfrac{1}{t^2H_t}$. This is well-defined because the series is easily seen to be convergent.
Observe that $A_{n-1}-A_n=\dfrac{1}{n^2H_n}$.
Now the upper bound for $x_k/k$: write $n=\lfloor \sqrt{k} \rfloor$.
Then $\dfrac{x_k}{k} \leq \dfrac{x_{n^2}}{n^2} \leq \dfrac{1}{n^2H_n}$, and we have:
$\dfrac{x_k}{k} \leq A_{n-1}-A_n$.
Thus, we can now set $f(k)=A_{\lfloor \sqrt{k} \rfloor}$, and make the induction work.
Now the base case:
We want: $x_1 \leq 3-A_1$ and since $x_1 \leq 1$, it is sufficient to show that $A_1 \leq 2$, which is doable, for eg: $A_1 \leq \dfrac{\pi^2}{6}-1 <1$.
A: For a given $k \ge 1$ choose $n \ge 1$ such that $k < (n+1)^2$. Then
$$
\frac{x_1}{1}+\frac{x_2}{2}+\frac{x_3}{3}+...+ \frac{x_k}{k}
\le \sum_{j=1}^n \sum_{l=j^2}^{(j+1)^2-1} \frac{x_l}{l}
\le \sum_{j=1}^n (2j+1) \frac{x_{j^2}}{j^2} \le 3 \sum_{j=1}^n \frac{x_{j^2}}{j} \le 3 \, ,
$$
using
$$
 \frac{2j+1}{j^2} \le \frac 3j
$$
for all positive integers $j$, which is easy to verify.
