Understanding Summation Notation - Sum from j=i to i+k of A[j] - CLRS Problem 8-5

Question

I need help understanding the following inequality of summations from Problem 8-5 of Cormen, Leiserson, Rivest, and Stein (2009, p. 207):

$$\frac{\sum_{j=i}^{i+k-1}A[j]}{k}\le\frac{\sum_{j=i+1}^{i+k}A[j]}{k}$$

Kanev (n.d.) seemed to say that this means that every ith element is less than every ith element plus k. If this is true, I don't understand why, although Cormen et al. do seem to indicate this in part of the problem.

My interpretation is that the sum of elements, i through k-1, divided by k is less than or equal to the sum of elements, i+1 through k, divided by k. I first need to establish whether I am interpreting the summation notation correctly before continuing to prove that what Kanev (n.d.) wrote is true. What's tripping me up is the j=i part.

So, what is the difference between the subscript, j=i, and just using the subscript, i, and then using i instead of j for the index?

References:

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.) [ProQuest Ebook Central version]. Retrieved from https://ebookcentral.proquest.com

Kanev, S. (n.d.). Problem 8.5 [Blog post]. Retrieved from https://ita.skanev.com/08/problems/05.html

Answer 1

We have \begin{align*} \sum_{j=i}^{i+k-1}A[j]&=A[i]+A[i+1]+\cdots+A[i+k-1]\\ \sum_{j=i+1}^{i+k}A[j]&=A[i+1]+A[i+2]+\cdots+A[i+k] \end{align*}

and the meaning of the inequality is:

• The mean values of the sum of $k$ consecutive elements $A[j], j=i,\ldots,i+k-1$ are increasing with increasing $j=1,2,\ldots$.

Answer 2

Since k is positive and the same on both sides, you can ignore it.

The right side minus the left side then becomes $A[i+k]-A[i]$ so that inequality is the same as $A[i] \le A[i+k]$.

This will certainly hold if $A$ is non decreasing.

Answer 3

For students of Cormen, Leiserson, Rivest, and Stein (2009) who are still confused, and since I like to write up summaries of my questions after they are answered, I will reply with a proof of Problem 8-5c (p. 207).

Claim: For any integer $i\ge1$, $$\frac{\sum_{j=i}^{i+k-1}A[j]}{k}\le\frac{\sum_{j=i+1}^{i+k}A[j]}{k}\iff A[i] \le A[i+k]$$

Proof: Let i and k be integers, and assume they are both greater than or equal to one. By the definition of a k-sorted array (Cormen et al., 2009, p. 207), the following is true:

$$\frac{\sum_{j=i}^{i+k-1}A[j]}{k}\le\frac{\sum_{j=i+1}^{i+k}A[j]}{k}$$

If we multiply both sides of the inequality by k, we derive the following:

$$\sum_{j=i}^{i+k-1}A[j]\le\sum_{j=i+1}^{i+k}A[j]$$

Expanding the summations (as recommended by @Markus_Scheuer, 2019), we get the following inequality of arithmetic series:

$$[]+[+1]+⋯+[+−1] \le [+1]+⋯+[+−1]+[+]$$

Subtracting $[+1]+⋯+[+−1]$ from both sides of the inequality, we get the following:

$$A[i] \le A[i+k]$$

Thus, we have shown the following:

$$\frac{\sum_{j=i}^{i+k-1}A[j]}{k}\le\frac{\sum_{j=i+1}^{i+k}A[j]}{k}\iff A[i] \le A[i+k]$$

QED

References:

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.) [ProQuest Ebook Central version]. Retrieved from https://ebookcentral.proquest.com

Scheuer, M. (2019, March 24). Re: Understanding Summation Notation - Sum from j=i to i+k of A[j] - CLRS Problem 8-5 [Stack Exchange comment]. Retrieved from https://math.stackexchange.com/q/3160495