Prove that for any real number $x, \sum_{i=1}^n a_i \lfloor ix \rfloor\ge 0$

Question

Let $n\ge 1$ and let $a_1\leq a_2\leq \cdots \leq a_n$ be real numbers such that $a_1 + 2a_2 + \cdots + na_n = 0$. Prove that for any real number $x, \sum_{i=1}^n a_i \lfloor ix \rfloor\ge 0$.

The result clearly holds for $n=1$. Suppose it holds for some $n\ge 1$ and let $a_1,\cdots, a_{n+1}$ satisfy that $a_1+2a_2+\cdots + na_n = 0$. Now for the inductive step, we naturally think of defining a new sequence in terms of the $a_i$'s. Let $b_i = a_i + (2/n) a_{n+1}$ for $1\leq i\leq n$. Then $$b_1 +2b_2+\cdots + nb_n = (2/n)a_{n+1}\cdot n(n+1)/2 + (a_1+2a_2+\cdots + na_n) = (n+1)a_{n+1} + (a_1+\cdots + na_n) = 0.$$ By the inductive hypothesis, for any real number $x$, $\sum_{i=1}^n (b_i)\lfloor ix \rfloor \ge 0\Leftrightarrow \sum_{i=1}^n (a_i\lfloor ix\rfloor + (2/n) a_{n+1}\lfloor ix\rfloor) \ge 0$. But how do I proceed from here? I don't think there's a closed form formula for $\sum_{i=1}^n \lfloor ix\rfloor$, but I know that $\sum_{i=0}^{n-1} \lfloor x + i/n\rfloor = \lfloor nx\rfloor$ for any real number x.

Answer 1

OP has essentially everything that is needed, and just needs to push through the algebra.

Following OP's induction proof,

1. (From OP) We want to show that $ \sum_{i=1}^{n+1} a_i \lfloor ix \rfloor \geq 0$
2. (From OP) We have by induction that $$ \sum_{i=1}^n a_i \lfloor ix \rfloor + \frac{2}{n} a_{n+1} \lfloor ix \rfloor \geq 0.$$
3. (Taking the difference of the previous two) So, it remains to show that $$a_{n+1} \lfloor (n+1) x \rfloor \geq \sum_{i=1}^n \frac{2}{n} a_{n+1} \lfloor ix \rfloor. $$
4. (Simplifying 3) Since $a_{n+1} \geq 0 $ (WHY?), we want to show that $$n \lfloor (n+1) x \rfloor \geq \sum_{i=1}^n 2 \lfloor i x\rfloor.$$
   • Notice that this gets rid of all the $a_i$. It doesn't matter what their values are.
5. (Proving 4) This follows from $ \lfloor a + b \rfloor \geq \lfloor a \rfloor + \lfloor b \rfloor $, applied suitably. (Fill in this gap.)

---

Note: I recognize a variant of this problem, where for an increasing sequence $A_i$ and decreasing sequence $B_i$ such that $ \sum i A_i = \sum i B_i$, then $ \sum A_i \lfloor i x \rfloor \geq \sum B_i \lfloor i x \rfloor$.

The problem follows from the variant by setting $B_i = 0$.
The proof by induction is similar to the above.
There is also a direct proof that essentially chains all of these inequalities together.

Conversely, the variant follows from the problem by setting $a_i = A_i - B_i$.