1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – michaelgill1969 Mar 24 '19 at 17:06
  • 1
    $\begingroup$ @michaelgill1969: Correct. $\endgroup$ – Markus Scheuer Mar 24 '19 at 17:07
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.