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

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.

• Push through the algebra. Use the fact that $a_{n+1} > 0$. Nov 7, 2023 at 20:22

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