How to evaluate the sum $\sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^{j} n $? I am trying to figure out the time complexity of the a given Algorithm, but using summations. Can anyone help get started on the inner summation, because I haven't come across such summation yet, and we just began solving these.   
$$\sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^{j} n $$
 A: Consider the inner summation. Note that it is indexed by $k$, meaning that $k$ is variable in this summation while everything else is constant. In particular, $n$ is a constant. Therefore
$$\sum_{k=1}^j n = n\sum_{k=1}^j1 = nj.$$
In light of the previous calculation, in the second summation we would like to compute
$$\sum_{j=i}^{n+i}\sum_{k=1}^j n = \sum_{j=i}^{n+1}nj = \sum_{j=1}^{n+1}nj-\sum_{j=1}^{i-1}nj.$$
Here the variable in the summation is $j$, so again we can pull $n$ in front to get
$$\sum_{j=1}^{n+1}nj-\sum_{j=1}^{i-1}nj = n \left(\sum_{j=1}^{n+i}j-\sum_{j=1}^{i-1}j\right) = n \left(\frac{(n+i)(n+i+1)}{2} - \frac{(i-1)i}{2}\right).$$
Note that a well known formula for summing the number from 1 to m (see https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_⋯) 
Finally, the outer summation. We would now like to compute
\begin{align*}
\sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^j n  &= \sum_{i=1}^{2n}n \left(\frac{(n+i)(n+i+1)}{2} - \frac{(i-1)i}{2}\right)\\
& = \sum_{i=1}^{2n}\frac{n^3+2n^2i+n^2+2ni}{2}.
\end{align*}
In this summation, the variable is $i$ so we can factor out multiplicative factors of $n$. After breaking up the long fraction, this gives us
\begin{align*}
&=\sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^j n\\
&=\frac{n^3}{2}\left(\sum_{i=1}^{2n}1\right)+n^2\left(\sum_{i=1}^{2n}i\right)+\frac{n^2}{2}\left(\sum_{i=1}^{2n}1\right)+n\left(\sum_{i=1}^{2n}i\right)\\
& = \frac{n^3}{2}\left(2n\right)+n^2\left(\frac{2n(2n+1)}{2}\right)+\frac{n^2}{2}\left(2n\right)+n\left(\frac{2n(2n+1)}{2}\right),
\end{align*}
where I used the same formula to sum the number 1 to 2n, and I used this other well known formula
$$\sum_{i=1}^n i^2 = \frac{i(i+1)(2i+1)}{6}.$$
for summing the numbers $1^2, 2^2,..., (2n)^2$ (see https://proofwiki.org/wiki/Sum_of_Sequence_of_Squares
). 
So I'm sure you'll want to reduce this, but the summation is above.  
A: If you just want
time complexity,
a $O(n^k)$ for some $k$
might be good enough.
The following uses
the trivial bound
(for $n > 1$)
$\sum_{i = 1}^n i^k
\lt \sum_{i = 1}^n n^k
= n^{k+1}
$.
$\begin{array}\\
\sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^{j} n
&=\sum_{i=1}^{2n}\sum_{j=i}^{n+i}jn\\
&=\sum_{i=1}^{2n}n\sum_{j=i}^{n+i}j\\
&<\sum_{i=1}^{2n}n(n+i)^2\\
&<\sum_{i=1}^{2n}n(n^2+2ni+i^2)\\
&=\sum_{i=1}^{2n}n^3+\sum_{i=1}^{2n}2n^2i+n\sum_{i=1}^{2n}i^2\\
&=2n^4+2n^2\sum_{i=1}^{2n}i+n\sum_{i=1}^{2n}i^2\\
&<2n^4+2n^2(2n)^2+n(2n)^3\\
&=(2+4+8)n^4\\
&=14n^4\\
\end{array}
$
So the total is
$O(n^4)$.
A: $$\begin{align}
\sum_{i=1}^{2n}\sum_{j=i}^{n+i}\sum_{k=1}^j n
&=n\sum_{i=1}^{2n}\sum_{j=i}^{n+i}j\\
&=n\sum_{i=1}^{2n}\sum_{r=0}^n (r+i)
&&(r=j-i)\\
&=n\left[\sum_{i=1}^{2n}\sum_{r=0}^n r+\sum_{r=0}^n \sum_{i=1}^{2n}i\right]\\
&=n\left[2n\cdot \frac {n(n+1)}2+(n+1)\cdot \frac {(2n)(2n+1)}2\right]\\
&=\color{red}{n^2 (n+1)(3n+1)=\mathcal{O}(n^4)}
\end{align}$$
