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?


There are a few observations we can make:

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

Of course, one can put all of this into one "magic" solution: \begin{eqnarray} \sum_{i=1}^k \frac{x_i}{i} & \leq & \sum_{i=1}^{(\lfloor\sqrt{k}\rfloor+1)^2-1} \frac{x_i}{i} = \sum_{t=1}^{\lfloor\sqrt{k}\rfloor} \sum_{i=t^2}^{(t+1)^2-1} \frac{x_i}{i} \\ & \leq & \sum_{t=1}^{\lfloor\sqrt{k}\rfloor} \sum_{i=t^2}^{(t+1)^2-1} \frac{x_{t^2}}{t^2} = \sum_{t=1}^{\lfloor\sqrt{k}\rfloor} \frac{2t+1}{t}\frac{x_{t^2}}{t} \\ & \leq & 3\sum_{t=1}^{\lfloor\sqrt{k}\rfloor} \frac{x_{t^2}}{t} \leq 3 \end{eqnarray}

  • $\begingroup$ Amazing solution. I think this one deserves a bounty. $\endgroup$ – Gerard Nov 30 '13 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.