Nested-Recursive Summation How could I simplify the following ?
$$
{\large\sum_{k_{1} = z}^{n}\sum_{k_{2} = k_{1}}^{n}\sum_{k_{3} = k_{2}}^{n} 1}\qquad \mbox{for natural numbers}\ z, n
$$
 A: We  consider at  first the special  case $z=1$  and  generalise it in a second step.

We obtain  with $z=1$:
\begin{align*}
\sum_{k_1=1}^n\sum_{k_2=k_1}^n\sum_{k_3=k_2}^n1=\sum_{\color{blue}{1\leq   k_1\leq k_2\leq k_3\leq  n}}1\tag{1}\\
\end{align*}
We observe  the number of summands given by the index range $$\color{blue}{1\leq k_1\leq k_2\leq k_3\leq n}$$ of (1) is the number of ordered tripels $(k_1,k_2,k_3)$ between $1$ and $n$ with repetition. This number is given by the binomial coefficient
  \begin{align*}
\binom{3+n-1}{3}&=\binom{n+2}{3}\\
&=\frac{1}{6}n(n+1)(n+2)\tag{2}
\end{align*}

Now we consider the generalisation $k_1=z$.

We obtain
  \begin{align*}
\color{blue}{\sum_{k_1=z}^n\sum_{k_2=k_1}^n\sum_{k_3=k_2}^n1}
&=\sum_{k_1=1}^{n-z+1}\sum_{k_2=k_1+z-1}^n\sum_{k_3=k_2}^n1\tag{3}\\
&=\sum_{k_1=1}^{n-z+1}\sum_{k_2=k_1}^{n-z+1}\sum_{k_3=k_2+z-1}^n1\tag{4}\\
&=\sum_{k_1=1}^{n-z+1}\sum_{k_2=k_1}^{n-z+1}\sum_{k_3=k_2}^{n-z+1}1\tag{5}\\
&\,\,\color{blue}{=\binom{n-z+3}{3}}\tag{6}
\end{align*}

Comment


*

*In (3) - (5) we successively shift the index $k_j$ to start as we did in (1).

*In (6) we apply (1) with $n$ substituted by $n-z+1$.
A: HINT
You have
$$
\begin{split}
S &= \sum_{k = 3}^n \sum_{j = k}^n \sum_{i = j}^n 1 \\
  &= \sum_{k = 3}^n \sum_{j = k}^n (n-j+1) \\
  &= \sum_{k = 3}^n \left(\sum_{j = k}^n (n+1) - \sum_{j = k}^n j\right) \\
  &= \sum_{k = 3}^n \left((n+1) (n-k+1)  - \sum_{j = k}^n j\right)
\end{split}
$$
Can you apply std summation formulae and finish the problem?
