# Nested-Recursive Summation

How could I simplify the following?

$$\sum_{k_1 = z}^{n}\sum_{k_2 = k_1}^{n}\sum_{k_3 = k_2}^{n} 1$$ For natural numbers $$z, n$$

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

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?

• I'm not familiar with these types of problems (or any summation problems). Do you think you could finish it off for me? – user_hello1 May 31 at 19:00
• @user_hello1 look up what is $\sum_{j=k}^n j$ and expand the expression above to use this twice – gt6989b May 31 at 19:30