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!


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

  • $\begingroup$ 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$? $\endgroup$ – sillyme Nov 30 '14 at 19:27
  • 1
    $\begingroup$ @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:) $\endgroup$ – Petite Etincelle Nov 30 '14 at 19:35

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.