A summation identity which is for me hard to verify

Question

I found a summation identity when I try to figure out the proof of an exercise in Apostol's Mathematical Analysis (Page 27, Exercise 1.26):

$\ ~~~~$ If $a_1\geq a_2\geq \dots\geq a_n$ and $b_1\geq b_2\geq \dots\geq b_n,$ prove that $$\sum_{k=1}^n a_k\cdot\sum_{k=1}^n b_k\leq n\sum_{k=1}^n a_kb_k.$$ I have at last proved this reslut based on the summation identity. That summation identity is \begin{gather*} \sum_{1\leq i<j\leq n} (\alpha_i+\beta_j)=\sum_{i=1}^{n-1} (n-i)\alpha_i+\sum_{i=1}^{n-1}i\beta_{i+1},~\forall \alpha_i,\beta_j\in\mathbb{C}, 1\leq i<j\leq n. \end{gather*} And I want to verify this identity, for I have never seen it. I have tried using induction on index $n,$ but was stuck. Although this identity is obvious, so is the proof, I have trouble in verifying it. Can anyone give me some clues?

Answer 1

I have two different proofs of the initial inequality, not based on the equality you cite. The first one is the simpler one, while the second one is perhaps more "analytical".

First, we can notice that for any $i,j$, we have $$ (a_i-a_j)(b_i-b_j)\ge0 \implies a_ib_i+a_jb_j\ge a_ib_j+a_jb_i. $$ E.g. if $i<j$, both $a_i-a_j\ge0$ and $b_i-b_j\ge0$, and the product is non-negative; if $i>j$, both factors are $\le0$, and the product is again non-negative.

Now, we have $$ \sum_{i=1}^n a_i\cdot\sum_{j=1}^n b_j =\sum_{i,j}a_ib_j=\frac12 \sum_{i,j}a_ib_j+a_jb_i \le\frac12 \sum_{i,j} a_ib_i+a_jb_j =n\sum_{i=1}^n a_ib_i. $$

---

The second proof starts of with the interpretation of this inequality that is used in statistics.

First, if we let $\bar a=\frac{1}{n}\sum_{i=1}^n a_i$ and $\bar b=\frac{1}{n}\sum_{i=1}^n b_i$, we can rewrite the inequality as $$ \text{cov}[A,B]= \frac{1}{n}\sum_{i=1}^n(a_i-\bar a)(b_i-\bar b) =\left(\frac{1}{n}\sum_{i=1}^n a_ib_i\right)-\bar a \bar b \ge0 $$ which is simply the expression for the covariance of the two series, with $A=(a_1,\ldots,a_n)$ and $B=(b_1,\ldots,b_n)$ representing the series.

In particular, we see from this that adding a constant to either of the series, i.e. $a'_i=a_i+\alpha$ and $b'_i=b_i+\beta$, does not change this covariance: $\text{cov}[A+\alpha,B+\beta]=\text{cov}[A,B]$.

Now, pick $\alpha=-a_n$ and $\beta=-b_n$, so we get $a'_1\ge \cdots\ge a'_n=0$ and $b'_1\ge \cdots\ge b'_n=0$. So proving the inequality for the original series is equivalent to proving it for $A'=(a'_i)$ and $B'=(b'_i)$: i.e. we need to prove that $$ \sum_{i=1}^{n}a'_i\cdot\sum_{i=1}^{n}b'_i\le n\cdot\sum_{i=1}^n a'_ib'_i. $$ However, since $a'_n=b'_n=0$, we can drop the $n$th term and only sum for $i=1$ to $n-1$, which reduces the problem to a shorter series. Now, we can use induction. The inequality certainly holds for $n=1$. If we assume it holds for sequences of length $n-1$, we know that $$ \sum_{i=1}^{n-1}a'_i\cdot\sum_{i=1}^{n-1}b'_i\le (n-1)\cdot\sum_{i=1}^{n-1} a'_ib'_i $$ by the induction hypothesis. And since the $a'_i$ and $b'_i$ are all non-negative, this makes $$ \sum_{i=1}^{n} a'_i\cdot\sum_{i=1}^{n}b'_i =\sum_{i=1}^{n-1}a'_i\cdot\sum_{i=1}^{n-1}b'_i \le (n-1)\cdot\sum_{i=1}^{n-1} a'_ib'_i \le n\cdot\sum_{i=1}^{n} a'_ib'_i. $$

Answer 2

This is just counting.

Among the integer pairs $(i,j)$ with $1\leq i < j \leq n$, for every fixed value of $j$, there are $j-1$ possible values for $i$, therefore there are $j-1$ pairs with a given $j$.

Consequently, the sum on the left-hand side adds $\beta_j$ precisely $j-1$ times.

Likewise, if we instead fix $i$ and look for pairs $(i,j)$ with $1\leq i < j \leq n$, we find $(n-i)$ valid values for $j$, hence there are precisely $(n-i)$ pairs $(i,j)$ for given $i$.

Which means that the left hand side adds $\alpha_i$ precisely $(n-i)$ times.

Your summation identity combines those two facts, that's all.