Solving equations of nested sums.

Question

I'm new to summation signs and I've been dealing a lot with questions containing nested summation signs. I understand how summation works using sigma signs, I just have no clue how to solve this equation to give you a number.

$$ \sum_{m_1=0}^{9}\sum_{m_2=0}^{m_1-1}\sum_{m_3=0}^{m_2-1}\sum_{m_4=0}^{m_3-1}m_4=x $$ I know the answer to this question is $x=252$ from Desmos (It's the only calculator I have that does summation like this) but I don't know what steps have to be taken to give $x=252$.

Answer 1

You do not want to solve an equation but you want to evaluate an expression.

I understand how summation works using sigma signs, I just have no clue how to solve this

Then I think you don't understand how summation works. The meaning of

$$\sum_{m_1=0}^9 F(m_1)$$ is $$F(1)+F(2)+\cdots+F(9)$$

Simplification

But before we start we simplify

$$\sum_{m_1=0}^{9}\sum_{m_2=0}^{m_1-1}\sum_{m_3=0}^{m_2-1}\sum_{m_4=0}^{m_3-1}m_4$$ we can ignore summand that are $0$ $$=\sum_{m_1=4}^{9}\sum_{m_2=3}^{m_1-1}\sum_{m_3=2}^{m_2-1}\sum_{m_4=1}^{m_3-1}m_4$$ we transform the index variables so that they start with $1$ $$=\sum_{m_1=1}^{6}\sum_{m_2=1}^{m_1}\sum_{m_3=1}^{m_2}\sum_{m_4=1}^{m_3}m_4\tag{1}$$ Further sum-identities can be found here

Expanding the sums

Now we can expand the left sum symbol: $$(1)=\sum_{m_2=1}^{1}\sum_{m_3=1}^{m_2}\sum_{m_4=1}^{m_3}m_4+\\ \sum_{m_2=1}^{2}\sum_{m_3=1}^{m_2}\sum_{m_4=1}^{m_3}m_4+\\ \sum_{m_2=1}^{3}\sum_{m_3=1}^{m_2}\sum_{m_4=1}^{m_3}m_4+\\ \sum_{m_2=1}^{4}\sum_{m_3=1}^{m_2}\sum_{m_4=1}^{m_3}m_4+\\ \sum_{m_2=1}^{5}\sum_{m_3=1}^{m_2}\sum_{m_4=1}^{m_3}m_4+\\ \sum_{m_2=1}^{6}\sum_{m_3=1}^{m_2}\sum_{m_4=1}^{m_3}m_4=$$

$$ \begin{eqnarray} \sum_{m_3=1}^{1}\sum_{m_4=1}^{m_3}m_4+&\\ \sum_{m_3=1}^{1}\sum_{m_4=1}^{m_3}m_4+&\sum_{m_3=1}^{2}\sum_{m_4=1}^{m_3}m_4+&\\ \sum_{m_3=1}^{1}\sum_{m_4=1}^{m_3}m_4+&\sum_{m_3=1}^{2}\sum_{m_4=1}^{m_3}m_4+&\sum_{m_3=1}^{3}\sum_{m_4=1}^{m_3}m_4+\\ \sum_{m_3=1}^{1}\sum_{m_4=1}^{m_3}m_4+&\sum_{m_3=1}^{2}\sum_{m_4=1}^{m_3}m_4+&\sum_{m_3=1}^{3}\sum_{m_4=1}^{m_3}m_4+\sum_{m_3=1}^{4}\sum_{m_4=1}^{m_3}m_4+\\ \sum_{m_3=1}^{1}\sum_{m_4=1}^{m_3}m_4+&\sum_{m_3=1}^{2}\sum_{m_4=1}^{m_3}m_4+&\sum_{m_3=1}^{3}\sum_{m_4=1}^{m_3}m_4+\sum_{m_3=1}^{4}\sum_{m_4=1}^{m_3}m_4+\sum_{m_3=1}^{5}\sum_{m_4=1}^{m_3}m_4+\\ \sum_{m_3=1}^{1}\sum_{m_4=1}^{m_3}m_4+&\sum_{m_3=1}^{2}\sum_{m_4=1}^{m_3}m_4+&\sum_{m_3=1}^{3}\sum_{m_4=1}^{m_3}m_4+\sum_{m_3=1}^{4}\sum_{m_4=1}^{m_3}m_4+\sum_{m_3=1}^{5}\sum_{m_4=1}^{m_3}m_4+\sum_{m_3=1}^{6}\sum_{m_4=1}^{m_3}m_4=\\ \end{eqnarray} $$ $$ =6\sum_{m_3=1}^{1}\sum_{m_4=1}^{m_3}m_4+\\ 5\sum_{m_3=1}^{2}\sum_{m_4=1}^{m_3}m_4+\\ 4\sum_{m_3=1}^{3}\sum_{m_4=1}^{m_3}m_4+\\ 3\sum_{m_3=1}^{4}\sum_{m_4=1}^{m_3}m_4+\\ 2\sum_{m_3=1}^{5}\sum_{m_4=1}^{m_3}m_4+\\ 1\sum_{m_3=1}^{6}\sum_{m_4=1}^{m_3}m_4=\\ (6+5+4+3+2+1)\sum_{m_4=1}^{1}m_4+\\ (5+4+3+2+1)\sum_{m_4=1}^{2}m_4+\\ (4+3+2+1)\sum_{m_4=1}^{3}m_4+\\ (3+2+1)\sum_{m_4=1}^{4}m_4+\\ (2+1)\sum_{m_4=1}^{5}m_4+\\ (1)\sum_{m_4=1}^{6}m_4=\\ 21\sum_{m_4=1}^{1}m_4+\\ 15\sum_{m_4=1}^{2}m_4+\\ 10\sum_{m_4=1}^{3}m_4+\\ 6\sum_{m_4=1}^{4}m_4+\\ 3\sum_{m_4=1}^{5}m_4+\\ 1\sum_{m_4=1}^{6}m_4=\\ 21\cdot 1+\\ 15 \cdot 3+\\ 10 \cdot 6 +\\ 6 \cdot 10 +\\ 3 \cdot 15 +\\ 1\cdot 21 = 252 $$ You can sum up this this way but I am searching for a simpler way. But nevertheless this is a way to calculate the expression and I think if you do so you may gain some insight.

Applying the formulas for the sum of powers

Another way is using the formulas for the sum of powers (and CAS system as I did) one will find:

$$\sum_{m_4=0}^{m_3-1}m_4 = \frac{m_3^2-m_3}{2}$$

$$\sum_{m_3=0}^{m_2-1}\sum_{m_4=0}^{m_3-1}m_4 = \sum_{m_3=0}^{m_2-1} \frac{m_3^2-m_3}{2} = \frac{m_2^3-3m_2^2+2m_2}{6}$$

$$\sum_{m_2=0}^{m_1-1}\sum_{m_3=0}^{m_2-1}\sum_{m_4=0}^{m_3-1}m_4=\sum_{m_2=0}^{m_1-1} \frac{m_2^3-3m_2^2+2m_2}{6}=\frac{m_1^4-6m_1^3+11m_1^2+6m_1}{24}$$

$$\sum_{m_1=0}^{m_0-1}\sum_{m_2=0}^{m_1-1}\sum_{m_3=0}^{m_2-1}\sum_{m_4=0}^{m_3-1}m_4=\sum_{m_1=0}^{m_0-1}\frac{m_1^4-6m_1^3+11m_1^2+6m_1}{24}=\frac{m_0^5-5m_0^4+5m_0^3+5m_01 2-6m_0}{120}$$ and substitute $m_0$ by $10$.

An Efficient Algorithm

Simpler is it to evaluate the sums $(1)$ numerically as in the following schema

S|   1   2   3   4   5   6   7   8   9  10
-|-----------------------------------------
1|   1   2   3   4   5   6   7   8   9  10
2|   1   3   6  10  15  21  28  36  45  55
3|   1   4  10  20  35  56  84 120 165 220
4|   1   5  15  35  70 126 210 ...
5|   1   6  21  56 126 252 ...

$$S_{1,n}=n$$ This is the innermost term $m_4$ of $(1)$. $$S_{2,n}=\sum_{m_4=1}^nm_4=S_{2,n-1}+S_{1,n}$$

This is the second innermost term of $(1)$.

$$S_{3,n}=\sum_{m_3=1}^n\sum_{m_4=1}^{m_3}m_4=S_{3,n-1}+S_{2,n}$$ and similar for the remaining lines of the matrix $S$. This is a calculation similar to Pascal's Triangle. $S_{5,6}$ contains the solution.

Note that the algoithm can easily be adopted for to calculate a sum

$$\sum_{m_1=1}^{6}\sum_{m_2=1}^{m_1}\sum_{m_3=1}^{m_2}\sum_{m_4=1}^{m_3}f(m_4)$$ The first line of the matrix contains the values $$f(1), f(2), f(3), \ldots$$ instead of $$1,2,3\ldots$$

A Combinatorial Problem

But the fastest way is to do it as described by Marcus Scheuer https://math.stackexchange.com/a/3301453/11206

Answer 2

In general, I would start from the innermost summation, i.e, $\sum_{m_4=0}^{m_3-1}m_4$, do its summation to get a result in terms of $m_3$, then use its result for the next outermost summation (i.e., determine a sum in terms of $m_2$), etc., until you have done all of the summations. However, you also need to be careful with the limits. For example, the innermost one goes from $m_4 = 0$ to $m_4 = m_3 - 1$, but the next outer one starts at $m_3 = 0$ with which the innermost lower bound is $m_4 = 0$ but its upper bound is $m_4 = 0 - 1 = -1 \lt 0$, so there is actually no summation for $m_3 = 0$ in that next outer summation. You therefore need to ensure in your evaluations that you account for this. Note this issue also applies to the next $2$ summations.

Answer 3

We can simplify this multiple sum by writing $m_4$ as sum: $m_4=\sum_{m_5=0}^{m_4-1}1$. We obtain

\begin{align*} \color{blue}{\sum_{m_1=0}^9}\color{blue}{\sum_{m_2=0}^{m_1-1}\sum_{m_{3}=0}^{m_{2}-1}\sum_{m_{4}=0}^{m_{3}-1}m_{4}} &=\sum_{m_1=0}^{9}\sum_{m_2=0}^{m_1-1}\sum_{m_{3}=0}^{m_{2}-1}\sum_{m_{4}=0}^{m_{3}-1}\sum_{m_{5}=0}^{m_{4}-1}1\\ &=\sum_{0\leq m_5<m_4<m_3<m_2<m_1\leq 9}1\tag{1}\\ &=\binom{10}{5}\tag{2}\\ &\,\,\color{blue}{=252} \end{align*}

Comment:

• In (1) we use another typical index notation, namely writing the range of summation as inequality chain.

• In (2) we observe the index range contains all ordered $5$-tuples from $\{0,1,2,\ldots,8,9\}$. The number of ordered $5$-tuples is given by the binomial coefficient $\binom{10}{5}$.

Answer 4

You can profitably use these conversion $$ \eqalign{ & \sum\limits_{m_{\,4} = 0}^{m_{\,3} - 1} {m_{\,4} } = \sum\limits_{m_{\,4} = 0}^{m_{\,3} - 1} {\left( \matrix{ m_{\,4} \cr 1 \cr} \right)} = \sum\limits_{\left( {0\, \le } \right)\,m_{\,4} \,\left( { \le \,m_{\,3} - 1} \right)\,} {\left( \matrix{ m_{\,3} - 1 - m_{\,4} \cr m_{\,3} - 1 - m_{\,4} \cr} \right)\left( \matrix{ m_{\,4} \cr m_{\,4} - 1 \cr} \right)} = \cr & = \left( \matrix{ m_{\,3} \cr m_{\,3} - 2 \cr} \right) \cr} $$ where:
- in the 2nd step we have transformed the sum bounds to become implicit in the first binomial; - in the 3rd step we have used the "double convolution " formula for binomials.

You can then continue to do the same for the outer sums.