2

Let $\{q_1,\dots,q_n\}$ be a set of real numbers s.t. $0\leq q_i\leq 1$ for every $i$ and $\sum_{i=1}^n q_i = k$ for $k\in \mathbb{N}$. And let $\{r_1\geq r_2\geq \dots \geq r_n\}$ be real numbers.

Prove that $$\sum_{i=1}^{n}q_i r_i \leq \sum_{i=1}^k r_i$$

For $k=1$ it's clearly true by replacing all $r_i$ with $r_1$: $$\sum_{i=1}^{n}q_i r_i \leq \sum_{i=1}^{n}q_i r_1 = r_1$$

Can this be used for $k>1$?

Thank you!

sillyme
  • 77

1 Answers1

1

Intuitively, dividing both sides by $k$, we have two weighted averages, then the side with more weights for large values dominate. To prove it:

\begin{align} \sum_{i=1}^n q_i r_i = &\sum_{i=1}^n q_i r_i + \sum_{i=1}^k (1-q_i)r_i - \sum_{i=1}^k(1-q_i)r_i\\ = &\sum_{i=1}^k r_i + \sum_{i=k+1}^n q_i r_i - \sum_{i=1}^k(1-q_i)r_i \end{align}

and with $M = \sum_{i=k+1}^n q_i = \sum_{i=1}^k(1-q_i)$ we have:

$$\sum_{i=k+1}^n q_i r_i - \sum_{i=1}^k(1-q_i)r_i \leq \left(\sum_{i=k+1}^n q_i\right)r_{k+1} - \left(\sum_{i=1}^k(1-q_i)\right)r_k = M(r_{k+1} - r_k) \leq 0$$

so we have the conclusion

Petite Etincelle
  • 14,767
  • Thank you. I too tried to split the sum... how did you come up with using $+ \sum_{i=1}^k (1-q_i)r_i - \sum_{i=1}^k(1-q_i)r_i$? – sillyme Nov 30 '14 at 19:27
  • 1
    @sillyme I wanted to make coefficients before $r_i,i=1,2,\cdots, k$ equal to $1$, then write explicitly the differences between the two sums. You are welcome:) – Petite Etincelle Nov 30 '14 at 19:35