Nested summations and their relation to binomial coefficients

Solution 1:

Suppose you want number of non-negative integer solutions of the equation $$x_1+\ldots+x_n = k+1$$ The answer is $\binom{k+n}{k+1}$ (a standard application of Stars and Bars).

Now, look at the case $k=1$ for simplicity. We construct a solution as follows: initialize each components of the vector $(x_1,\ldots, x_n)$ to zero, then to make their sum $2$, we add $1$ to one of the components at two steps one by one.

• In the first step, we have $n$ choices where to add the $1$. Suppose we added it at the $i$-th position, i.e. $x_j=0$ unless $j\neq i$, and $x_i=1$ after this step.

• At the next step, we add the second $1$ to the $j$-th position, imposing the condition $j\leq i$ to avoid having same solution twice.

We can do this in $\sum_{i=1}^n\sum_{j=1}^i1$ ways. Result using the formula must also be same, so $$\binom{n+1}{2} = \sum_{i=1}^n\sum_{j=1}^i1$$

For higher values of $k$, we just need to remember where we add the first $1$ is rightmost, and for the next steps, tail of the vector will remain empty. Then the formulas are apparent.