How do I compute this triple summation? $$\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1} i + j + k$$
The question is looking for a $\Theta(g(n))$ function to represent this summation, but I am uncertain how to go about computing triple summations. 
P.S. This is not homework. It was actually an exam question for a class that I missed today.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
 A: Hint.
\begin{align}
\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1}( i + j + k) &=
\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1}i+
\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1}j+
\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1}k \\ &=
\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} ij+\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} j^2+
\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \frac{j(j-1)}{2} \\ &=
\sum_{i=0}^{n-1} \frac{i^2(i-1)}{2}+\sum_{i=0}^{n-1}  \frac{i(i-1)(2i-1)}{6}+
\sum_{i=0}^{n-1}  \frac{i(i-1)(i-2)}{6} \\ &=
\sum_{i=0}^{n-1} \frac{i^2(i-1)}{2}+\sum_{i=0}^{n-1}  \frac{i(i-1)(3i-3)}{6}
=\sum_{i=0}^{n-1}\frac{i(i-1)(2i-1)}{2}.
\end{align}
Can you continue after this?
A: Split it into this:
$$
S = \sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1} i + j + k = 
\sum_{i=0}^{n-1} \left( i + \left(\sum_{j=0}^{i-1} \left(j + \sum_{k=0}^{j-1} k\right) \right)  \right)
$$
The innermost sum is $j(j-1)/2$; add $j$ to that to get $j(j+1)/2$. Factor out the $1/2$ and get
$$
S = \frac{1}{2} \sum_{i=0}^{n-1} \left( i + \left(\sum_{j=0}^{i-1} j^2 + j \right)  \right)
$$
Now apply the summation rule for $j^2$ and for $j$ in the same way, and then the summation rules for $i^3, i^2,$ and $i$, and you'll get an answer. 
A: (New Solution)
This solution is much neater than the earlier solution (see below). 
$$\begin{align}
S
&=\sum_{i=0}^{n-1}\sum_{j=0}^{i-1}\sum_{k=0}^{j-1}i+j+k=\color{lightgrey}{\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}\sum_{k=0}^{j-1}i+j+k}\tag{1}\\
&=\sum_{r=0}^{n-1}\sum_{s=n-i\\\;=r+1}^{n-1}\sum_{t=n-j\\\;=s+1}^{n-1}3(n-1)-(r+s+t)
&&\scriptsize{r=n-1-i\\s=n-1-j\\ t=n-1-k}\\
&=\sum_{t=2}^{n-1}\sum_{s=1}^{n-1}\sum_{r=0}^{n-1}3(n-1)-(t+s+r)
&&\scriptsize 0\le r<s<t\le n-1\\
&=\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}\sum_{k=1}^{j-1}3(n-1)-(i+j+k)\tag{2}\\
&=\frac 32(n-1)\sum_{i=2}^{n-1}\sum_{j=2}^{n-1}\sum_{k=0}^{n-1}1
&&\frac {(1)+(2)}2\\
&=\frac 32(n-1)\sum_{i=2}^{n-1}\sum_{j=2}^{n-1}\binom j1\\
&=\frac 32(n-1)\sum_{i=2}^{n-1}\binom i2\\
&=\color{red}{\frac 32(n-1)\binom n3}\\
&=\color{red}{\frac {n(n-1)^2(n-2)}4}\\
&=\color{red}{\binom {n-1}2\binom n2}
\end{align}$$

(Earlier solution below)
This solution arrives at the solution in the form of the product of two sums of integers. 
$$\begin{align}
\sum_{i=0}^{n-1}\sum_{j=0}^{i-1}\sum_{k=0}^{j-1}(i+j+k)
&=\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}\sum_{k=0}^{j-1}(i+j+k)\\
&=\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}\sum_{s=1}^{j}(i+2j-s)
&&(s=j-k)\\
&=\sum_{i=2}^{n-1}\sum_{s=1}^{i-1}\sum_{j=s}^{i-1}(i+2j-s)
&&(1\le s\le j\le i-1)\\
&\color{lightgrey}{=\sum_{i=2}^{n-1}\sum_{s=1}^{i-1}(i-s)(i-s)+2\cdot \frac {i-s}2(s+\overline{i-1})}
&&\color{lightgrey}{\text{(number of steps=$i-s$)}}\\
&=\sum_{i=2}^{n-1}\sum_{s=1}^{i-1}(i-s)(i+\overline{i-1})\\
&=\sum_{i=2}^{n-1}\sum_{r=1}^{i-1}r(i+\overline{i-1})
&&(r=i-s)\\
&=\sum_{r=1}^{n-2}r\sum_{i=r+1}^{n-1}(i+\overline{i-1})
&&(1\le r<i\le n-1)\\
&=\sum_{r=1}^{n-2}r\sum_{i=r+1}^{n-1}i+\sum_{r=1}^{n-2}r\sum_{i=r+1}^{n-1}(i-1)\\
&=\sum_{r=1}^{n-2}r\sum_{i=r+1}^{n-1}i+\sum_{r=1}^{n-2}r\sum_{i=r}^{n-2}i\\
&=\sum_{r=1}^{n-2}r\sum_{i=r+1}^{n-1}i+\sum_{i=1}^{n-2}i\sum_{r=1}^{i}r
&&(1\leq r\le i\le n-2)\\
&=\sum_{i=1}^{n-2}i\sum_{r=i+1}^{n-1}r+\sum_{i=1}^{n-2}i\sum_{r=1}^{i}r\\
&=\sum_{i=1}^{n-2}i\left(\sum_{r=1}^i r+\sum_{r=i+1}^{n-1}r\right)\\
&=\sum_{i=1}^{n-2}i\sum_{r=1}^{n-1}r\\
&=\color{red}{\binom {n-1}2\binom n2}\\
&=\color{red}{\frac 14n(n-1)^2(n-2)}
\end{align}$$
A: This represents three loops nested together. And a simple loop has order $\Theta(n)$. And also in general $\Theta(f\circ g)=\Theta(f)\Theta(g)$. And if you have a loop that depends arithmetically on an outer loop, then the order of the inner loop is the same as the outer loop. Thus in your case you have that the time complexity is $\Theta(n^3)$.
