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

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

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$$.
• So, this really isn't any different than, for example, the sum of A[j] from j=1 to k-1 is A[1] + A[1+1] + ... + A[k-1]. The i can represent any integer, allowing one to begin at A[2], A[3], or A[one googol]. Correct? – michaelgill1969 Mar 24 '19 at 17:06
• @michaelgill1969: Correct. – Markus Scheuer Mar 24 '19 at 17:07

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.

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