2
$\begingroup$

I'm having trouble when the indexes are related in a double summation. For example, this problem: $\sum^n_{i = 1} \sum^n_{j = i+1} j - i + 2$

How could I sum this and what's a general approach to this type of double/triple summations?

$\endgroup$
  • 1
    $\begingroup$ You have to be very careful with what the limits are, and how you're summing them up. Draw a picture showing you the region that you're interested in, which makes it easier to understand the new limits to use. $\endgroup$ – Calvin Lin May 26 '13 at 0:04
  • 1
    $\begingroup$ I think attempting to draw the region will only make things more complicated. Just break up the sums and shift the indexes of each sum up and down accordingly. $\endgroup$ – Ethan May 26 '13 at 0:13
1
$\begingroup$

$$\sum^n_{i = 1} \sum^n_{j = i+1} j - i + 2= \sum^n_{i = 1} \sum^{n-i}_{j =1} j + 2=\sum^n_{i = 1}\frac{(n-i)^2+(n-i)}{2}+2(n-i)$$ $$=\sum_{i=1}^{n-1}\frac{i^2+i}{2}+2i=\sum_{i=1}^{n-1}\frac{i^2+5i}{2}=\frac{1}{2}\sum_{i=1}^{n-1}i^2+\frac{5}{2}\sum_{i=1}^{n-1}i=\frac{n(n-1)(n+7)}{6}$$

$\endgroup$
1
$\begingroup$

It depends greatly on what you know. I might be inclined to let $k=j-i$ and evaluate it like this:

$$\begin{align*} \sum_{i=1}^n\sum_{j=i+1}^n(j-i+2)&=\sum_{i=1}^n\sum_{k=1}^{n-i}(k+2)\\\\ &=\sum_{i=1}^n\left(\sum_{k=1}^{n-i}k+2(n-i)\right)\\\\ &=\sum_{i=1}^n\frac12(n-i)(n-i+1)+2\sum_{i=1}^n(n-i)\\\\ &=\sum_{i=1}^n\left(\binom{n-i+1}2+2(n-i)\right)\\\ &=\sum_{i=0}^{n-1}\left(\binom{i+1}2+2i\right)\\\\ &=\binom{n+1}3+2\binom{n}2\\\\ &=\binom{n}3+3\binom{n}2\;. \end{align*}$$

Of course, you need to know some binomial coefficient identities in order to do that.

Or you could go at it straight up. First,

$$\sum_{i=1}^n\sum_{j=i+1}^n(j-i+2)=\sum_{i=1}^n\left(\sum_{j=i+1}^nj-\sum_{j=i+1}^n(i-2)\right)\;.$$

Now $\sum_{j=i+1}^nj$ is just the sum of an arithmetic progression, so it’s $\frac12(n+i+1)$. And $\sum_{j=i+1}^n(i-2)=(n-i)(i-2)$, since it’s the sum of $n-i$ identical terms. The double sum then reduces to a single sum over $i$ of a quadratic in $i$, which is straightfoward to evaluate if you know that $\sum_{i=1}^ni^2=\frac16n(n+1)(2n+1)$.

$\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.