A puzzle related to loops. For a given input $N$, how many times does the enclosed statement executes?

for $i$ in $1\ldots N$ loop 
  $\quad$for $j$ in $1\ldots i$ loop 
  $\quad$$\quad$for $k$ in $j\ldots i$ loop 
  $\quad$$\quad$$\quad$$sum = sum + i$ ; 
  $\quad$$\quad$end loop; 
  $\quad$end loop; 
  end loop; 

Can anyone figure out an easy way or a formula to do this in general. 
 A: The number of times the inside statement is executed is $S = \sum_{i=1}^N \sum_{j=1}^i \sum_{k=i}^j 1$.
\begin{eqnarray}
S &=& \sum_{i=1}^N \sum_{j=1}^i (i-j+1) \\
& = & \sum_{i=1}^N (i(i+1)-\frac{1}{2} i(i+1)) \\
& = & \frac{1}{2} \sum_{i=1}^N  (i^2 +i) \\
& = & \frac{1}{2} (\frac{1}{6}N(N+1)(2N+1)+ \frac{1}{2}N (N+1)) \\
& = & \frac{1}{6} N(N+1)(N+2)
\end{eqnarray}
A: For any value of $i$, the $j$-loop executes $i$ times. For any value of $j$, the $k$-loop executes $i-j+1$ times, and each time we add $i$ to the sum. Assuming the initial $sum$ was $0$, we have:
$$\begin{align*}sum&=\sum_{i=1}^N \sum_{j=1}^i i(i-j+1)=\sum_{i=1}^N \sum_{j=1}^i (i^2+i-ji)=\sum_{i=1}^N \left((i^2+i)i-i\frac{i(i+1)}{2}\right)=\\
&=\frac12\sum_{i=1}^N \left(2i^3+2i^2-i^3-i^2\right)=\frac12\sum_{i=1}^N\left(i^3-i^2\right)=\frac12\left(\frac{N^2(N+1)^2}{4}-\frac{N(N+1)(2N+1)}{6}\right)=\\
&=\frac{1}{24} (N-1) N (N+1) (3 N+2)\end{align*}$$
A: So you're asking for the value of
$$ S = \sum_{i=1}^N\sum_{j=1}^i(i-j+1). $$
Write $S_i$ for the inner sum. Then
$$ S_i = i^2 - \sum_{j=1}^i j + i = i^2 - \frac{i(i+1)}2 + i = \frac12 i^2 + \frac12 i.$$
Then the outer sum is
\begin{align*}
S &= \frac12\sum_{i=1}^N i^2 + \frac12\sum_{i=1}^n i\\
&= \frac{N(N+1)(2N+1)}{12} + \frac{N(N+1)}4\\
&= \frac{N(N+1)(N+2)}{6}.
\end{align*}
A: There is also a combinatorical way to find the solutiopn of you question.
Check wich values takes the tupel $(j,k,i)$ in the most inner loop?
Each tuple $(j,k,i)$ with $1 \le k \le N$ exactly once.
So   


*

*each tuple $(j,k,i)$ with $1 \le j<k<i \le N$

*each tuple $(j,j,i)$ with $1 \le j<i \le N$

*each tuple $(j,i,i)$ with $1 \le j<i \le N$

*each tuple $(j,j)$ with $1 \le j \le N$


The first number is $\binom{N}{3}$, the second and the third is $\binom{N}{2}$, the fourth is $\binom{N}{1}$. 
$$(\binom{N}{3} +  \binom{N}{2} ) + (\binom{N}{2}+ \binom{N}{1})=\binom{N+1}{3}+\binom{N+1}{2}=\binom{N+2}{3}=\frac{n(n+1)(n+2)}{6}=\binom{n+2}{3}$$
Edit
This result can be proved in a direct way:
Take the $n+2$ element set $M=\{\text{"j=k"},1,...,N,\text{"i=k"}\}$. The set contains of the $N$ numbers $1,...,N$ and the two strings $\text{"j=k"}$ and $\text{"i=k"}$. A three element subset $S$ of $M$ can be of exactly one of the following types:


*

*$S=\{j,k,i\} , 1 \le j \lt k \lt i \le N$

*$S=\{\text{"j=k"},k,i\}, 1 \le k \lt i \le N$

*$S=\{j,k,\text{"i=k"}\}, 1 \le j \lt k \le N$

*$S=\{\text{"j=k"},k,\text{"i=k"}, 1 \le k \le N$


The sets of these four list items correspond to the tuples of the corresponding items of the former list. But this four types of sets contain all the three element subsets of the set M and the number of three element subsets of $M$ is $\binom{n+2}{3}$.
