# Prove, for these set of constraints, $\sum_{i=1}^k \frac{x_i}{i} \leq 3$

Suppose $\left\langle x_1, x_2, \dots, x_n, \dots\right\rangle$ is a sequence of positive real numbers such that $x_1 \geq x_2 \geq \dots \geq x_n\dots$ and for all $n$:

$$\sum_{i = 1}^n \frac{x_{i^2}}{i} \leq 1$$

Prove, for all $k$,

$$\sum_{i = 1}^k \frac{x_{i}}{i} \leq 3$$

I have no idea how to even approach the problem. I tried various transformations, and tried solving the problem for specific $n$s and then trying to generalize, but nothing worked. Can you give a solution with motivations?

• The given inequality speaks only about certain terms (those whose index is a perfect square) in the sequence and ignores the others. Since the inequality to be proven is an upper bound on a sum of positive values, we can assume all the other terms of the sequence to be as large as possible. In other words, we can assume the sequence to be of the form $$\langle x_1, x_1, x_1, x_4, x_4, x_4, x_4, x_4, x_9, x_9, \ldots\rangle$$
• It's sufficient to look at the second inequality for $k$ of the form $k=m^2-1$ for positive integer $m$, as adding more terms can only increase the value of the sum.
• The terms in the second sum can be grouped as follows: $$\left(\frac{x_1}{1} + \frac{x_1}{2} + \frac{x_1}{3}\right) + \left(\frac{x_4}{4} + \frac{x_4}{5} + \frac{x_4}{6} + \frac{x_4}{7} + \frac{x_4}{8}\right) + \ldots + \left(\ldots + \frac{x_k}{k}\right)$$ (there are $(m-1)$ brackets in total, with $i$-th bracket containing $2i+1$ terms)
• $i$-th bracket can be bounded above by $\frac{2i+1}{i^2}x_{i^2}$ (first term in the bracket multiplied by number of terms) which, in turn, can be bounded by $\frac{3}{i}x_{i^2}$ since $2i+1 <= 3i$.
• Thus, the whole sum is bounded from above by $\sum\limits_{i=1}^{m-1} \frac{3}{i}x_{i^2} = 3\sum\limits_{i=1}^{m-1} \frac{x_i^2}{i}$. But we know this latter sum is bounded by $1$, which means the full expression is bounded by $3$, just as we wanted to prove.