# Nested sums inequality chain

On this post, there appears the following expression:

\begin{align} \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_{1}

which is explained as "writing the range of summation as inequality chain."

I don't see why $$m_5,$$ for example, has to be larger than $$m_4,$$ or any of the other inequalities. Or why $$9$$ is the maximum value.

Can someone please explain with an example how this notation works?

Thank you for the comments, I see it is now corrected, but I still don't know if this works like this - with increasing limits of summation from innermost to outermost simply because we are adding $$1$$'s in this case, because when we do double integrals, the limits of integration over each variable don't necessarily follow a sequence. What is different in the case of summations?

• Hmm, it seems incorrect at first glance, doesn't it? For a given value of $m_1$ in the outermost sum, the index $m_2$ in the next sum is never greater than or equal to $m_1$ (so always $m_2<m_1$ when it appears). The same is true for successive indices. However, it is possible that the indices are renamed and they are being used in the reverse order. After all, the name is meaningless, only the assumed values matter. For example, $\sum_{m=0}^{5}a_m$ is exactly the same as $\sum_{k=0}^{5}a_k$. – MPW Jul 26 '19 at 14:07
• If you reverse the inequality chain, $$\sum_{0\leq m_{5}<m_{4}<m_3<m_2<m_1\leq 9}1$$ it makes sense (so probably a typo). – quasi Jul 26 '19 at 14:08
• Note: The author (@Markus Scheuer) of the referenced answer has now corrected the typo. – quasi Jul 26 '19 at 14:31
• @quasi . It's actually correct $with$ the typo, when you consider that the variables $m_1,..$ on the LHS do not have any relation to those on the LHS. But it's confusing when written that way if you are trying to understand it. Somewhat like writing $(\exists x\,(x<1) )\land (\exists x\,(x>2)).$ – DanielWainfleet Jul 26 '19 at 20:13
• @DanielWainfleet: I agree that it's technically correct (since the variables are dummy variables), but nevertheless, there no good reason to risk confusing the reader, so I would regard it as a style error, rather than a logical error. Note that Markus Scheuer acknowledged the unintentional choice of order, and has now corrected it. – quasi Jul 26 '19 at 20:21

## 1 Answer

It might help to view it from a programming perspective . . .

Suppose we wanted to compute $$\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$$ in a program.

Consider the following Maple program . . .

    x:=0:
for m1 from 0 to 9 do
for m2 from 0 to m1-1 do
for m3 from 0 to m2-1 do
for m4 from 0 to m3-1 do
for m5 from 0 to m4-1 do
x:=x+1
od
od
od
od
od:
x;

Let $$M$$ be the set of $$5$$-tuples $$m=(m_5,m_4,m_3,m_2,m_1)$$ of integers such that $$0 \le m_5 < m_4 < m_3 < m_2 < m_1\le 9$$ Note that whenever the statement $$x\,{:}{=}\,x+1$$ is executed, we have $$(m_5,m_4,m_3,m_2,m_1)\in M$$.

Moreover, for every $$5$$-tuple $$m\in M$$ the statement $$x\,{:}{=}\,x+1$$ is executed exactly once.

Hence the final value of $$x$$ is just the cardinality of $$M$$, which is the same as $$\\[10pt]$$ $$\sum_{m\in M} 1$$ or equivalently $$\sum_{0 \le m_5 < m_4 < m_3 < m_2 < m_1\le 9} 1$$

• Thank you for your answer. Can you please explain the code? Specifically what od does. – Antoni Parellada Jul 26 '19 at 22:01
• "od" just ends the matching do loop. – quasi Jul 26 '19 at 22:02