# How to simplify $\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}\dots\sum_{a_{k+1}=1}^{a_k}1$

Let $$x=\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}\dots\sum_{a_{k+1}=1}^{a_k}1$$ where $n,k\in\mathbb{Z}^+$. How to simplify $x$?

I simplified it for $k=1,2,3$ and I got $n$, $\dfrac12n(n+1)$ and $\dfrac16n(n+1)(n+2)$. From this I assumed that for any $k$: $$x=\dfrac n{k+1}{\binom{n+k}{n}}$$ Problem is how to prove it. I tried using mathematical induction, but it seems that this is not an easy way.

• It would seem that you are counting the number of $k$ tuples $1\leq a_{k+1} \leq a_k \leq \dots \leq a_2 \leq a_1 \leq n$. – Myself Dec 29 '14 at 18:35
• Yes, can you explain how to simplify it? – user164524 Dec 29 '14 at 18:52
• @Mathematician171 Have you tried the cases $k=1$; $k=2$? Induction will help. – Pedro Tamaroff Dec 29 '14 at 18:54
• @Mathematician171 what Myself meant was $$\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}\dots\sum_{a_{k+1}=1}^{a_k}1 = \sum\limits_{1 \le a_{k+1} \le a_k \le \cdots\le a_1 \le n} 1$$ Basically we are counting the number of $k+1$-tuples $(a_1,a_2,\cdots,a_{k+1})$ with the property that: $$1 \le a_{k+1} \le a_k \le \cdots\le a_1 \le n$$ That is $k+1$-tuples $(b_1,\cdots,b_{k+1})$ such that: $1 \le b_{k+1} = a_{k+1} < a_k+1 < b_k = a_{k-1}+2 < \cdots < b_ 1 = a_1 + k \le n+k$ Also we know the number of ways of choosing $k+1$ distinct integers from $\{1,2,\cdots,n+k\}$ is $$\binom{n+k}{k+1}$$ – r9m Dec 29 '14 at 19:01
• Another way to do this is to notice the relation between the sum for $k$ and for $k-1$. If $x_k(p)$ is the number of $k$ tupples (your sum) satisfying $a_{k+1}\leq a_k \leq \ldots \leq a_1 \leq p$ then we have (why?) $x_k(n) = x_{k-1}(1) + x_{k-1}(2) + \ldots + x_{k-1}(n)$ The identity $\sum_{p=1}^n{p+k\choose k+1} = {n+k+1\choose k+2}$ plus can be useful to use this for an induction proof. – Winther Dec 29 '14 at 19:25

The sum is the same as the number of ways for choosing $$(k+1)$$-tuple $$(a_1,a_2,\ldots,a_{k+1})$$ such that $$1\leq a_{k+1}\leq a_{k}\leq \ldots a_1$$. The different possibilities can be broken down as follows:
• All number are distinct: This is same as choosing $$k+1$$ distinct numbers from the set $$\{1,2,\ldots,n\}$$ sorting them. Thus, this can happen in $$\binom{n}{k+1}$$ ways.
• $$l$$ repetitions are allowed: We note that repetitions happen only at consecutive locations as the tuples entries are in the descending order. Therefore, there are $$\binom{k}{l}$$ possible locations for repetition. Therefore, we first choose $$k-l$$ distinct numbers from the set $$\{1,2,\ldots,n\}$$ and $$l$$ locations for repetition, to form a valid tuple. Thus, this can happen in $$\binom{n}{k+1-l}\binom{k}{l}$$ ways.
Thus, we have \begin{align} \sum_{a_1=1}^{n}\sum_{a_2=1}^{a_1}\ldots \sum_{a_{k+1}=1}^{a_{k}}1 &= \sum_{l=0}^{k} \binom{n}{k+1-l}\binom{k}{l} \\ &=\sum_{l=0}^{k+1} \binom{n}{k+1-l}\binom{k}{l} - \binom{n}{0}\binom{k}{k+1}\\ &= \binom{n+k}{k+1}. \end{align} Here, we use Vandermonde's identity to get the last step. The result also agrees with your formula: $$$$\frac{n}{k+1}\binom{n+k}{n} = \frac{n(n+k)!}{n!k!(k+1)}=\frac{(n+k)!}{(n-1)!(k+1)!} =\binom{n+k}{k+1}.$$$$