# How do I simplify nested summations? Also how does it work? Like a loop?

$$\sum^{n}_{j=1}\sum^{n}_{k=1} jk$$ How do I simplify this? Also can someone explain how this works? its gonna be like this right? or am I misunderstanding it? $$\sum^{n}_{j=1}(j+2j+3j+...+nj)$$

-
Just note that $$\sum_{j=1}^{n}\sum_{k=1}^{n}jk = \left(\sum_{j=1}^{n} j\right)\left(\sum_{k=1}^{n} k\right) = \left(\sum_{j=1}^{n} j\right)^2.$$ –  Sangchul Lee Nov 13 '12 at 10:26
huh? why did it become summation of j squared? when j and k are not equal? –  The Taxman Nov 13 '12 at 10:30

Yes, the nested summation reads $\sum^{n}_{j=1}\bigl(\sum^{n}_{k=1} jk\bigr)$. In this case you can see that all terms in the inner summation have a factor $j$ that does not depend on the summation index ($k$) in common, so you can factor that out: $\sum^{n}_{j=1}\bigl(\sum^{n}_{k=1} jk\bigr)=\sum^{n}_{j=1}\bigl(j\sum^{n}_{k=1} k\bigr)$. Now the inner summation itself does not depend on the index ($j$) of the outer summation, so it can be factored out of that, and becomes a separate summation: $\sum^{n}_{j=1}\bigl(j\sum^{n}_{k=1} k\bigr)=\bigl(\sum^{n}_{k=1} k\bigr)\bigl(\sum^{n}_{j=1}j\bigr)$. Now you can do both summations, which are not nested, separately (I trust you know how to do this); in fact they are the same summation, with a different name for the summation variable. All in all you get the square of the value of $\sum^{n}_{i=1} i$.

You won't of course always be as lucky when doing nested summations; often there is simply no simpler way to write them.

-

$j$ is constant over the inner sum, so move it out of the sum:

$\sum_{j=1}^{n} \sum_{k=1}^n jk = \sum_{j=1}^{n} \left( j \sum_{k=1}^n k\right)$

Now the whole inner sum is constant for the outer sum, move it out:

$\sum_{j=1}^{n} \left(j \sum_{k=1}^n k\right) = \left( \sum_{k=1}^n k \right) \left( \sum_{j=1}^n j \right)$

Now both sums are easy to evaluate:

$\left( \sum_{k=1}^n k \right) \left( \sum_{j=1}^n j \right) = \left( \frac{n(n+1)}{2} \right)\left( \frac{n(n+1)}{2} \right) = \left( \frac{n(n+1)}{2} \right)^2$

-