$ \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) $
How do I simplify nested summations? Also how does it work? Like a loop?
-
0huh? why did it become summation of j squared? when j and k are not equal? – 2012-11-13
2 Answers
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$