Cfxtrjtrk

Knowing that $$sum_{i=1}^n i = frac{n(n+1)}{2}$$
how can I get closed form formula for
$$sum_{i=1}^n sum_{j=1}^i j$$
or
$$sum_{i=1}^n sum_{j=1}^i sum_{k=1}^j k$$
or any x times neasted summation like above

Let $f_k(n)$ be the closed form of the summation nested $k$ times. We know that
$$f_1(n)=frac12n(n+1)=binom{n+1}{2}$$
$$f_k(n)=sum_{j=1}^n f_{k-1}(j)$$
So for the next function $f_2(n)$ we have
$$f_2(n)=sum_{j=1}^nbinom{j+1}{2}=sum_{j=2}^{n+1}binom{j}{2}=binom{n+2}{3}$$
By using the Hockey-stick identity (credits to Jean-Claude Arbaut).
Similarly for the next function $f_3(n)$ we have
$$f_3(n)=sum_{j=1}^nbinom{j+2}{3}=sum_{j=3}^{n+2}binom{j}{3}=binom{n+3}{4}$$
So one could conjecture that
$$f_k(n)=binom{n+k}{k+1}$$
which can be easily proven by induction as follows
$$f_k(n)=sum_{j=1}^nbinom{j+k-1}{k}=sum_{j=k}^{n+k-1}binom{j}{k}=binom{n+k}{k+1}$$
Hence we have that
$$boxed{f_k(n)=binom{n+k}{k+1}=frac1{(k+1)!}n(n+1)(n+2)dots(n+k-1)(n+k)}$$

We can write the last multiple sum as
begin{align*}
color{blue}{sum_{i_1=1}^nsum_{i_2=1}^{i_1}sum_{i_3=1}^{i_2}i_3}
&=sum_{i_1=1}^nsum_{i_2=1}^{i_1}sum_{i_3=1}^{i_2}sum_{i_4=1}^{i_3} 1\
&=sum_{1leq i_4leq i_3leq i_2leq i_1leq n}1tag{1}\
&,,color{blue}{=binom{n+3}{4}}tag{2}
end{align*}
In (1) we observe the index range is the number of ordered $4$-tuples with repetition from a set with $n$ elements resulting in (2).

Here's a combinatorial way of thinking about it: first of all, note that we can go one level deeper and represent the innermost piece ($j$, or $k$, etc.) in your formulae as $sum_{h=1}^j1$; this means that the formula start to look like $displaystylesum_{m=1}^n1 =n$, $displaystylesum_{m=1}^nsum_{l=1}^m1=n(n+1)/2={n+1choose 2}$, $displaystylesum_{m=1}^nsum_{l=1}^msum_{k=1}^l1={n+2choose 3}$, etc. Now, let's look at what the left hand side is counting. In the first case, we're just counting the number of ways to choose an $m$ between $1$ and $n$ (inclusive); this is, self-evidently, just $n$. In the second, we're choosing a number $m$ between $1$ and $n$ inclusive, again, but then choosing an $l$ between $1$ and $m$; this is exactly the number of ways of choosing two numbers between $1$ and $n$, where we don't care about the order — that is, choosing $2$ and $5$ is exactly the same as choosing $5$ and $2$. Similarly, $displaystylesum_{m=1}^nsum_{l=1}^msum_{k=1}^l1$ counts the number of ways of choosing three numbers between $1$ and $n$, without regard to order; this is because we can sort the numbers we've chosen (since we don't care about order), and then note that the largest can be anywhere between $1$ and $n$, but then the next largest can only be between $1$ and the largest, etc.

Now, the difference between this and regular combinations is that in a regular combination every chosen number must be distinct; but if we have an ordered list $langle k, l, mrangle$ of the (not necessarily distinct) numbers we've chosen between $1$ and $n$ then we can turn this into an ordered list of not necessarily distinct numbers between $1$ and $n+2$: let $k'=k$, $l'=l+1$, $m'=m+2$. You should be able to convince yourself that this is a one-to-one correspondence between not-necessarily-distinct choices in ${1ldots n}$ and distinct choices in ${1ldots n+2}$, and the same principle extends to any number of choices. (This wikipedia link has more details).

$$S_{n_2}=sum_{i=1}^nsum_{j=1}^ij=sum_{i=1}^nfrac{i(i+1)}{2}=frac12sum_{i=1}^ni^2+i=frac12left[frac{n(n+1)(2n+1)}{6}+frac{n(n+1)}{2}right]=frac{n(n+1)(n+2)}{6}$$
and now:
$$S_{n_3}=sum_{i=1}^nsum_{j=1}^isum_{k=1}^jk=frac16sum_{i=1}^ni(i+1)(i+2)=frac16sum_{i=1}^ni^3+3i^2+2i=frac16left[frac{n^2(n+1)^2}{4}+frac{n(n+1)(2n+1)}{2}+n(n+1)right]=frac{n(n+1)}{6}left[frac{n(n+1)}{4}+frac{(2n+1)}{2}+1right]=frac{n(n+1)(n+2)(n+3)}{24}$$
and we can see a pattern here. For a series $S_{n_a}$ with $a$ nested summations the following is true:
$$S_{n_a}=frac{1}{(a+1)!}prod_{b=0}^a(n+b)=frac{(n+a)!}{(n-1)!(a+1)!}$$