# Proving a sequence inequality

Let $$(a_k)_1^n$$ and $$(b_k)_1^n$$ be two real sequences, and suppose that $$(b_k)$$ is nonnegative and decreasing. For $$k \in \{1,2,\ldots,n\}$$, define $$S_k = \sum_{i=1}^k a_i$$. Let $$M = \max \{S_1,\ldots, S_n\}$$ and $$m = \min \{S_1,\ldots,S_n\}$$. Prove that $$mb_1 \le \sum_{i=1}^n a_i b_i \le Mb_1$$

I am trying to prove this by assuming that $$m = S_j$$, so I get $$(a_1 + a_2 + \cdots + a_j)b_1 \le a_1b_1 + a_2b_2 + \cdots + a_nb_n$$ which is equivalent to \begin{align} & a_2(b_1-b_2) + \cdots + a_j(b_1-b_j) \\ \le {} & a_{j+1}b_{j+1} + \cdots + a_nb_n \tag 1 \end{align} Now if the $$a_i$$s are all positive then it is easy since from the fact that $$(b_k)$$ is a decreasing sequence, $$a_2(b_1-b_2) + \cdots + a_j(b_1-b_j) \le (a_2 + \cdots +a_j)(b_1-b_j)$$ But we also know that $$S_1 \ge S_j$$, so $$a_2 + \cdots + a_j \le 0$$, which implies that the LHS of $$(1)$$ is less than or equal to $$0$$, and as $$S_j\le S_n \Rightarrow a_{j+1} + \cdots + a_n \ge 0$$, so $$a_{j+1}b_{j+1} + \cdots + a_nb_n \ge (a_{j+1} + \cdots + a_n)b_n \ge 0$$ therefore the RHS of $$(1)$$ is greater than or equal to $$0$$, hence $$(1)$$ is proven. In a similar way, we can also prove that $$\sum_{i=1}^n a_ib_i \le Mb_1$$.

But the problem is that $$(a_k)$$ is a real sequence, not a positive sequence, which means there may be negative terms in it, and I don't have any idea how to proceed. Can anyone help? Thanks.

• Shouldn't the lower bound be $b_nm$? Dec 25, 2019 at 4:14
• Well, the original question stated the lower bound as $mb_1$, not $mb_n$...
– Vann
Dec 25, 2019 at 4:21

Since $$a_1 = S_1$$ and $$a_i = S_i - S_{i-1}, \ i = 2, 3, \cdots, n$$, we have \begin{align} &\sum_{i=1}^n a_i b_i \\ =\ & S_1b_1 + (S_2-S_1)b_2 + (S_3-S_2)b_3 + (S_4 - S_3)b_4 + \cdots + (S_n - S_{n-1})b_n\\ =\ &S_1(b_1 - b_2) + S_2(b_2 - b_3) + S_3(b_3 - b_4) + \cdots + S_{n-1}(b_{n-1} - b_n) + S_nb_n. \end{align} Since $$b_n \ge 0$$ and $$b_i - b_{i+1} \ge 0, \ i=1, 2, \cdots, n-1$$ and $$m \le S_i \le M, \ i = 1, 2, \cdots, n$$, we have \begin{align} &\sum_{i=1}^n a_i b_i \\ \ge\ & m(b_1 - b_2) + m(b_2 - b_3) + m(b_3 - b_4) + \cdots + m(b_{n-1} - b_n) + mb_n\\ =\ & mb_1 \end{align} and \begin{align} &\sum_{i=1}^n a_i b_i \\ \le\ & M(b_1 - b_2) + M(b_2 - b_3) + M(b_3 - b_4) + \cdots + M(b_{n-1} - b_n) + Mb_n\\ \le\ & Mb_1. \end{align} We are done.

See: Abel's summation by parts

______Editing my previous comment & extending the answer_____________

Case 1: When {$$a_i$$} is a sequence of positive terms.

Upper bound can be obtained easily.

Since {$$b_i$$} is decreasing, $$b_1\geq b_i$$ for all $$i=1,2...n$$. Hence, $$\sum_{i=1}^{n}a_ib_i\leq \sum_{i=1}^{n}a_ib_1=b_1\sum_{i=1}^{n}a_i=b_1S_n\leq b_1M$$.

Similarly, for the lower bound,

$$\sum_{i=1}^{n}a_ib_i\geq b_1a_1=b_1m$$, since $$a_i>0$$ for all $$i$$ & $$S_1=a_1 for all i.

Case 2: When {$$a_i$$} is a sequence of negative terms

$$\sum_{i=1}^{n}a_ib_i\leq a_1b_1$$. Note that $$S_1=a_1$$.Since $$a_i<0$$ & $$S_1 \geq S_i$$ for all $$i$$, $$M=S_1$$ so that $$\sum_{i=1}^{n}a_ib_i\leq Mb_1$$.

Similarly, for the lower bound,

$$S_n \leq S_i$$ for all $$i$$ & $$b_1 \geq b_i$$ for all $$i$$. So $$m=S_n$$, $$\sum_{i=1}^{n}a_ib_i \geq b_1 \sum_{i=1}^{n}a_i=b_1S_n=b_1m$$.

Case 3: When {$$a_i$$} consists of + & - terms,

Observe that $$\sum -|a_i|b_i \leq \sum a_ib_i \leq \sum |a_i|b_1$$

Rightmost term is the one we considered under case1 & leftmost term is the one under case 2. Since the result was proved for both cases, it trivially holds for this case as well.

• hmm..but how could you know that $\sum_{i=1}^{n} a_ib_i \le \sum_{i=1}^{n} a_ib_1$? Because the $a_i$s can also be negative(?)
– Vann
Dec 25, 2019 at 4:31
• It doesn't matter. $\sum a_ib_i= a_1b_1+a_2b_2+...+a_nb_n \leq a_1b_1+a_2b_1+...+a_nb_1=b_1(a_1+a_2+...+a_n)$ Dec 25, 2019 at 4:34
• What if we take $a_1 = -3, a_2 = -2, a_3 = -1, b_1 = 3, b_2 = 2, b_1 = 1$, then $\sum_{i=1}^{3} a_ib_i = -14$, however $\sum_{i=1}^{n} a_ib_1 = -18$, a contradiction? But the inequality $\sum_{i=1}^{n} a_ib_i \le Mb_1$ is still true though ($-14 \le (-3)(3)$).
– Vann
Dec 25, 2019 at 4:52
• Yeah correct. I missed that point. Editing my answer to indicate the case where {$a_i$} is a sequence of positive terms.But, according to your example, $m=-6$ & $b_1=1$ so that $mb_1=-6$. In this case, it can't be true that $mb_1 \leq \sum a_ib_i=-18$ . Dec 25, 2019 at 5:16
• Ups sorry...I wrote $b_1 = 3, b_2 = 2$, and $b_1 = 1$ again in my previous comment, where the latter should be $b_3$ instead of $b_1$...so $mb_1 = -18 \le \sum a_ib_i = -18$, which is still true I guess.
– Vann
Dec 25, 2019 at 5:24