Nested-Recursive Summation

Question

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 $$

Answer 1

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$.

Answer 2

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?