sum recurrence formula I have the following recurrence formula:
$\sum_{l=1}^{N}\sum_{m=1}^{l}...\sum_{k=1}^j\sum_{i=1}^k i$ that I would like to simplify.
I know that $\sum_{i=1}^k i=\frac{k(k+1)}{2}$ so I could use Faulhaber's formula:
$\sum_{i=1}^Ni^\alpha=\frac{1}{1+\alpha}\sum_{j=0}^\alpha(-1)^j
\begin{pmatrix} 
\alpha + 1 \\
j
\end{pmatrix}
B_jn^{\alpha+1-j}$
to simplify sum by sum, but I am looking for something easier if it exists, any idea?
 A: Here is the formula you are looking for:
$$\sum_{n_{k-1}=1}^{n_k} \sum_{n_{k-2}=1}^{n_{k-1}} ... \sum_{n_0=1}^{n_1} 1=\frac{1}{k!}\prod_{i=0}^{k-1} (n_k+i)=\frac{(n_k+k-1)!}{k!(n_k-1)!}=\binom{n_k+k-1}{k}$$
Assume that this statement is true for some $n_k$. Then we must prove that its truth for some $n_k$ implies its truth for $n_{k+1}$, or that if the above is true, then
$$\sum_{n_k=1}^{n_{k+1}} \sum_{n_{k-1}=1}^{n_k} ... \sum_{n_0=1}^{n_1} 1=\frac{1}{(k+1)!}\prod_{i=0}^{k} (n_{k+1}+i)$$
Must also be true. This may at first seem like a scary problem to attack until we remember that we assumed that
$$\sum_{n_{k-1}=1}^{n_k} \sum_{n_{k-2}=1}^{n_{k-1}} ... \sum_{n_0=1}^{n_1} 1=\frac{1}{k!}\prod_{i=0}^{k-1} (n_k+i)$$
was true, allowing us to substitute and instead have the task of proving
$$\sum_{n_k=1}^{n_{k+1}} \frac{1}{k!}\prod_{i=0}^{k-1} (n_k+i)=\frac{1}{(k+1)!}\prod_{i=0}^{k} (n_{k+1}+i)$$
Which is less intimidating. First one must notice that the quantity
$$\prod_{i=0}^{k-1} (n_k+i)$$
is equal to
$$\frac{(n_k+k-1)!}{(n_k-1)!}$$
and we can substitute this into our equation to get
$$\sum_{n_k=1}^{n_{k+1}} \frac{1}{k!}\frac{(n_k+k-1)!}{(n_k-1)!}=\frac{1}{(k+1)!}\frac{(n_{k+1}+k)!}{(n_{k+1}-1)!}$$
We can now notice that 
$$\frac{1}{k!}\frac{(n_k+k-1)!}{(n_k-1)!}$$
is the same as
$$_{n_k+k-1}C_{n_k-1}$$
and so now we have
$$\sum_{n_k=1}^{n_{k+1}} {_{n_k+k-1}C_{n_k-1}}=\frac{1}{(k+1)!}\frac{(n_{k+1}+k)!}{(n_{k+1}-1)!}$$
Now we can attack the sum
$$\sum_{n_k=1}^{n_{k+1}} {_{n_k+k-1}C_{n_k-1}}$$
Which expands out to form
$$_kC_0+_{k+1}C_1+_{k+2}C_2+...+_{n_{k+1}+k-1}C_{n_{k+1}-1}$$
Now we can use the identity of the combinations formula
$$_nC_r=_{n+1}C_r-_nC_{r-1}$$
to expand out our infinite sum:
$$_kC_0+(_{k+2}C_1-_{k+1}C_0)+(_{k+3}C_2-_{k+2}C_3)+...+(_{n_{k+1}+k}C_{n_{k+1}-1}-_{n_{k+1}+k-1}C_{n_{k+1}-2})$$
We can see now that this is a telescoping sum that condenses down to
$$_kC_0-_{k+1}C_0+_{n_{k+1}+k}C_{n_{k+1}-1}$$
$$=1-1+_{n_{k+1}+k}C_{n_{k+1}-1}$$
$$=_{n_{k+1}+k}C_{n_{k+1}-1}$$
When we substitute this into our equation, we get this:
$$_{n_{k+1}+k}C_{n_{k+1}-1}=\frac{1}{(k+1)!}\frac{(n_{k+1}+k)!}{(n_{k+1}-1)!}$$
$$\frac{(n_{k+1}+k)!}{(k+1)!(n_{k+1}-1)!}=\frac{(n_{k+1}+k)!}{(k+1)!(n_{k+1}-1)!}$$
Which is a truth statement. This proves that if our statement is true for some $k$, then is must be true for $k+1$, and since it is true for $k=1$, it is true for all natural numbers $k$. QED.
