2
$\begingroup$

How would an expression that looks like this be written?

$$\underbrace{\sum_{m_1=0}^{n-1}\sum_{m_2=0}^{m_1-1}\dots\sum_{m_{n-2}=0}^{m_{n-3}-1}\sum_{m_{n-1}=0}^{m_{n-2}-1}m_{n-1}}_{n-1\sum-symbols}$$

What is the correct notation for nested sigma (summation) symbols of this nature? Is this the most efficiently this equation can be written out?

$\endgroup$
2
  • 1
    $\begingroup$ It is not really an equation. (Though there are some equals signs around, they are part of the sigma-notation, and do not make this expression into an equation.) $\endgroup$ Jul 11 '19 at 12:47
  • $\begingroup$ You're right. Thanks for telling me. $\endgroup$ Jul 11 '19 at 21:03
3
$\begingroup$

One can write more compactly $$\sum_{\substack{0\le m_1<n\\0\le m_2<m_1\\\vdots\\0\le m_{n-2}<m_{n-3}\\0\le m_{n-1}<m_{n-2}}}m_{n-1}.$$ Personally, I would first define a set $$S=\{(m_1,\dots,m_{n-1})\in\mathbb N^{n-1}:n>m_1>m_2>\dots>m_{n-2}>m_{n-1}\ge0\}$$ and then write $$\sum_{(m_1,\dots,m_{n-1})\in S}m_{n-1}.$$

$\endgroup$
3
  • $\begingroup$ Thank you for your answer, this is exactly what I was looking for. Would you mind explaining to me why you have the inequalitites underneath the first sigma symbol and explaining what the colon and inequalities in the set "S" mean or pointing me somewhere where I could find out? I'm in high school so I haven't been introduced to alot of this yet. $\endgroup$ Jul 11 '19 at 8:42
  • $\begingroup$ The notation $\sum_{a\le i\le b}$ means sum over all $i$ such that $a\le i\le b$, so it is equivalent to $\sum_{i=a}^b$. (Of course, one should ensure that it is clear to the reader that the summation variable is $i$ and not $a$ or $b$.) The advantage is that one can add more variables by stacking them in the subscript, and replace the inequalities with an arbitrary predicate $\sum_{\text{[something]}}$ which means sum over all values of the summation variable(s) such that [something] is true. $\endgroup$
    – user856
    Jul 11 '19 at 12:27
  • $\begingroup$ The definition of $S$ uses set builder notation. In this case, it means $S$ is the set of all tuples of the form $(m_1,\dots,m_{n-1})$ such that $n>m_1>\dots>m_{n-1}\ge 0$. (This is equivalent to your summation limits: $m_1$ is between $0$ and $n$, $m_2$ is between $0$ and $m_1$, and so on.) $\endgroup$
    – user856
    Jul 11 '19 at 12:31
1
$\begingroup$

We can considerably simplify this multiple sum since we obtain for $n\geq 1$:

\begin{align*} \color{blue}{\sum_{m_1=0}^{n-1}}&\color{blue}{\sum_{m_2=0}^{m_1-1}\dots\sum_{m_{n-2}=0}^{m_{n-3}-1}\sum_{m_{n-1}=0}^{m_{n-2}-1}m_{n-1}}\\ &=\sum_{m_1=0}^{n-1}\sum_{m_2=0}^{m_1-1}\dots \sum_{m_{n-2}=0}^{m_{n-3}-1}\sum_{m_{n-1}=0}^{m_{n-2}-1}\sum_{m_{n}=0}^{m_{n-1}-1}1\tag{1}\\ &=\sum_{0\leq m_{n}<m_{n-1}<\cdots<m_2<m_1\leq n-1}1\tag{2}\\ &\,\,\color{blue}{=1}\tag{3} \end{align*}

Comment:

  • In (1) we write $m_{n-1}$ as sum: $m_{n-1} =\sum_{m_n=0}^{m_{n-1}-1}1$.

  • In (2) we use another typical notation and write the index range as inequality chain.

  • In (3) we observe the index range contains exactly one $n$-tuple: $(0,1,2,\ldots,n-2,n-1)$.

$\endgroup$

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.