Is there a pattern to expression for the nested sums of the first $n$ terms of an expression? [duplicate]

Question

This question already has an answer here:

• Finite Sum of Power? 2 answers
• Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$ 15 answers

Apologies for the confusing title but I couldn't think of a better way to phrase it. What I'm talking about is this:

$$ \sum_{i=1}^n \;i = \frac{1}{2}n \left(n+1\right)$$ $$ \sum_{i=1}^n \; \frac{1}{2}i\left(i+1\right) = \frac{1}{6}n\left(n+1\right)\left(n+2\right) $$ $$ \sum_{i=1}^n \; \frac{1}{6}i\left(i+1\right)\left(i+2\right) = \frac{1}{24}n\left(n+1\right)\left(n+2\right)\left(n+3\right) $$

We see that this seems to indicate:

$$ \sum_{n_m=1}^{n}\sum_{n_{m-1}=1}^{n_m}\ldots \sum_{n_1=1}^{n_2} \; n_1 = \frac{1}{m!}\prod_{k = 0}^{m}(n+k) $$

Is this a known result? If so how would you go about proving it? I have tried a few inductive arguments but because I couldn't express the intermediate expressions nicely, I didn't really get anywhere.

Answer 1

You should have $$\sum_{i=1}^{n} 1 = n$$ $$\sum_{i=1}^{n} i = \frac{1}{2} n(n+1)$$ $$\sum_{i=1}^{n} \frac{1}{2} i(i+1) = \frac{1}{6} n(n+1)(n+2)$$ $$\sum_{i=1}^{n} \frac{1}{6} i(i+1)(i+2) = \frac{1}{24} n(n+1)(n+2)(n+3)$$

In particular, the first sum of yours was wrong and the things you were adding should depend on $i$, not on $n$.

But, to answer the question, yes! This is a known result, and actually follows quite nicely from properties of Pascal's triangle. Look at the first few diagonals of the triangle and see how they match up to your sums, and see if you can explain why there's such a relation, and why the sums here can be written in terms of binomial coefficients. Then, the hockey-stick identity proves your idea nicely.

Answer 2

From finite calculus we have that

$$\sum a^{\underline k}\delta k=\frac{a^{\underline{k+1}}}{k+1}+C$$

where $a^{\underline k}:=\prod _{j=0}^{k-1}(a-j)$ is known as a falling factorial, and $C$ is any periodic function with period $1$ (this can be a constant function, in general is taken as zero, this is an analog of an indefinite integral, in this case this is an indefinite sum).

And we have that $a^{\overline m}:=\prod_{j=0}^{m-1}(a+j)$ is known as a rising factorial, and

$$a^{\overline m}=(a+m-1)^\underline m$$

Hence you want to solve the sum

$$\begin{align}\sum_{k=\ell}^n k(k+1)\cdots(k+m)&=\sum\nolimits_\ell^{n+1}k^{\overline{m+1}}\delta k\\&=\sum\nolimits_\ell^{n+1}(k+m)^{\underline{m+1}}\delta k\\&=\frac{(k+m)^{\underline{m+2}}}{m+2}\bigg|_\ell^{n+1}\\&=\frac1{m+2}\big((n+m+1)^\underline{m+2}-(\ell+m)^\underline{m+2}\big)\\&=\frac1{m+2}\big(n^\overline{m+2}-(\ell-1)^\overline{m+2}\big)\end{align}$$

From here is easy to justify your result

$$\underbrace{\sum\sum\ldots\sum_{k=1}^n 1}_{m\text{ times}}=\frac{n^\overline {m+1}}{m!}=\frac{(n+m-1)^{\underline m}}{m!}=\binom{n+m-1}{m}$$

Answer 3

The pattern actually is $$ \sum_{n_m=1}^{n}\sum_{n_{m-1}=1}^{n_m}\ldots \sum_{n_1=1}^{n_2} \sum_{n_0=1}^{n_1} 1 = \frac{1}{(m+1)!}\prod_{k = 0}^{m}(n+k), \tag1$$ where for reasons of symmetry (and making the later proof simpler) I have written $n_1$ as $\sum_{n_0=1}^{n_1} 1.$ A slightly more convenient way to write the same thing is

$$ \sum_{1\leq n_0\leq n_1\leq n_2\leq \cdots \leq n_{m-1}\leq n_m\leq n} 1 = \binom{n+m}{m+1} \tag2$$

where $\binom{n+m}{m+1}$ is a binomial coefficient. The right-hand side of Equation $2$ equals the right-hand side of Equation $1$ by means of the following formula for a binomial coefficient, $$ \binom pq = \frac{p(p-1)(p-2)\cdots(p-q+1)}{q!}. $$

The meaning of the left-hand side of Equation $2$ is that there is one term of the sum for every possible list of numbers $n_0, n_1, n_2, \ldots, n_m$ such that $1\leq n_0\leq n_1\leq n_2\leq \cdots \leq n_m\leq n.$ Notice that $$ \sum_{1\leq n_0\leq n_1\leq n_2\leq\cdots\leq n_{m-1}\leq n_m\leq n} 1 = \sum_{n_m=1}^n \left(\sum_{1\leq n_0\leq n_1\leq n_2\leq\cdots \leq n_{m-1}\leq n_m} 1\right),$$ and if you continue to "unpack" the sums in this fashion with a sum from $1$ to $n_m,$ then $1$ to $n_{m-1},$ and so forth, you get the $m+1$ nested sums on the left side of Equation $1.$

---

This is a well-known result. See Simplification of a nested sum, Nested summations and their relation to binomial coefficients, and this answer to Binomial coefficient as a summation series proof?

There is a combinatorial proof which is a little easier to see if you rewrite the sum this way: $$ \sum_{1\leq n_0\leq n_1\leq n_2\leq\cdots\leq n_m\leq n} 1 = \sum_{0 < n_0 < n_1+1 < n_2+2 < \cdots < n_m+m < n+m+1} 1,\tag3$$ using the fact that for integers $p$ and $q,$ $p \leq q$ if and only if $p < q+1.$

Each term in the sum on the right-hand side of Equation $3$ has $m+1$ index numbers $n_0, n_1, n_2, \ldots, n_m$ selected from the integers strictly between $0$ and $n+m+1,$ that is, from the set of integers $\{1,2,3,\ldots,n+m-1,n+m\}.$ Since each possible combination of numbers selected can be selected in only one way (increasing order), the number of terms is exactly the number of ways to choose $m+1$ elements from a set of $n+m$ elements, that is, the binomial coefficient "$n+m$ choose $m+1$," notated $\binom{n+m}{m+1}.$

Answer 4

In this answer it is proved that:$$ \sum_{n_m=1}^{n}\sum_{n_{m-1}=1}^{n_m}\ldots \sum_{n_1=1}^{n_2}1=\binom{n+m-1}{m}\tag1$$

On base of the rule:$$\sum_{k=r}^n\binom{k}{r}=\binom{n+1}{r+1}\tag2$$ which can easily be deduced by induction on $n$. Induction step:$$\sum_{k=r}^n\binom{k}{r}=\sum_{k=r}^{n-1}\binom{k}{r}+\binom{n}{r}=\binom{n}{r+1}+\binom{n}{r}=\binom{n+1}{r+1}$$

Now $(2)$ can be applied to prove $(1)$ by induction on $m$.

The induction step is:

$$ \sum_{n_m=1}^{n}\sum_{n_{m-1}=1}^{n_m}\ldots \sum_{n_1=1}^{n_2} \; 1 = \sum_{n_m=1}^{n} \binom{n_{m-1}+m-2}{m-1}= \binom{n+m-1}{m}$$