4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You won't be able to solve this just by using the initial equation. $\endgroup$ – Peter Foreman Apr 17 at 17:19
  • $\begingroup$ 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. $\endgroup$ – callculus Apr 17 at 17:21
  • $\begingroup$ Use the formulae for the sum of $k^2$ and $k^3$ $\endgroup$ – George Dewhirst Apr 17 at 17:34
  • 1
    $\begingroup$ Hint: $n={n \choose 1}$, $n(n+1)/2={n+1\choose 2}$. Now have a look at the hockey-stick identity. $\endgroup$ – Jean-Claude Arbaut Apr 17 at 17:51
  • $\begingroup$ @Jean-ClaudeArbaut Do you mind if I write an answer using this now? $\endgroup$ – Peter Foreman Apr 17 at 17:53
4
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.