# Closed form of recurrent arithmetic series summation

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

• You won't be able to solve this just by using the initial equation. – Peter Foreman Apr 17 at 17:19
• Go step by step: $\sum_{i=1}^n \sum_{j=1}^i j=\sum_{i=1}^n \frac{i(i+1)}{2}=\frac12\cdot \color{red}{\sum_{i=1}^n i^2}+\frac12 \cdot \sum_{i=1}^n i$. The red colored part cannot be solved with the first formula. – callculus Apr 17 at 17:21
• Use the formulae for the sum of $k^2$ and $k^3$ – George Dewhirst Apr 17 at 17:34
• Hint: $n={n \choose 1}$, $n(n+1)/2={n+1\choose 2}$. Now have a look at the hockey-stick identity. – Jean-Claude Arbaut Apr 17 at 17:51
• @Jean-ClaudeArbaut Do you mind if I write an answer using this now? – Peter Foreman Apr 17 at 17:53

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)}$$

• $\sum_{j=1}^n\left(\frac16n^3+\frac12n^2+\frac13n\right)$: The summands do not depend on the index $j$. – callculus Apr 17 at 17:51
• @callculus Yes, sorry I've corrected it. – Peter Foreman Apr 17 at 17:52

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).

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).

$$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)!}$$

• What is wrong with this answer? – Henry Lee Apr 17 at 18:34
• I don´t know. Hopefully the downvoter leaves a comment. – callculus Apr 17 at 18:37
• Appart from the notation $S_{n_a}$, looks good. Note also that the last expression is ${n+a\choose a+1}$. – Jean-Claude Arbaut Apr 17 at 18:40