Closed form of recurrent arithmetic series summation

Question

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

Answer 1

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}^n\binom{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}^n\binom{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}^n\binom{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)}$$

Answer 2

$$S_{n_2}=\sum_{i=1}^n\sum_{j=1}^ij=\sum_{i=1}^n\frac{i(i+1)}{2}=\frac12\sum_{i=1}^ni^2+i=\frac12\left[\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}^n\sum_{j=1}^i\sum_{k=1}^jk=\frac16\sum_{i=1}^ni(i+1)(i+2)=\frac16\sum_{i=1}^ni^3+3i^2+2i=\frac16\left[\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}+1\right]=\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)!}$$

Answer 3

We can write the last multiple sum as \begin{align*} \color{blue}{\sum_{i_1=1}^n\sum_{i_2=1}^{i_1}\sum_{i_3=1}^{i_2}i_3} &=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1}\sum_{i_3=1}^{i_2}\sum_{i_4=1}^{i_3} 1\\ &=\sum_{1\leq i_4\leq i_3\leq i_2\leq i_1\leq n}1\tag{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).

Answer 4

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 $\displaystyle\sum_{m=1}^n1 =n$, $\displaystyle\sum_{m=1}^n\sum_{l=1}^m1=n(n+1)/2={n+1\choose 2}$, $\displaystyle\sum_{m=1}^n\sum_{l=1}^m\sum_{k=1}^l1={n+2\choose 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, $\displaystyle\sum_{m=1}^n\sum_{l=1}^m\sum_{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, m\rangle$ 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 $\{1\ldots n\}$ and distinct choices in $\{1\ldots n+2\}$, and the same principle extends to any number of choices. (This wikipedia link has more details).