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*}


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



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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.