# How many summands does $\sum_{0\le i_1<i_2<…<i_{n+1}<M} a_{i_1},_{i_2},…_{i_{n+1}}$ have?

How many summands does $$\sum_{0\le i_1 have?

I found this problem and was confused about the notation. I don't understand how you're supposed to interpret the sum or how to approach a solution. I assumed it could be analogous to something like $$\sum_{n=0}^M$$, but I have no idea if it's even close to the answer.

## 2 Answers

Using the notation $$\sum$$ with a relation underneath means you take any possible choice for the summand where the relation is fulfilled, and you add them together. For instance, for the standard summation notation, we have $$\sum_{i=0}^nb_i=\sum_{0\leq i\leq n}b_i$$ In your case, it means you take all possible $$a_{i_1,i_2,\ldots,i_{n+1}}$$ which satisfy $$0\leq i_1 and you add them together. For instance, if $$n=2$$ and $$M=4$$, that means you add together $$a_{0,1,2}+a_{0,1,3}+a_{0,2,3}+a_{1,2,3}$$ In total, there are $$n+1$$ indices, and $$M$$ valid numbers to choose from. They have to be in increasing order, so choosing which numbers appear as indices is the same as choosing the indices. This means there are $$\binom{M}{n+1}$$ summands.

Also, if you'd like, your sum may be written out as $$\sum_{i_1=0}^{M-n-1}\sum_{i_2=i_1+1}^{M-n}\cdots\sum_{i_n=i_{n-1}+1}^{M-2}\sum_{i_{n+1}=i_n+1}^{M-1}a_{i_1,i_2,\ldots,i_n,i_{n+1}}$$

• It's $M$ valids, not $M-1$... – Parcly Taxel Aug 12 '19 at 5:12
• @PatclyTaxel You're right. At some point $0\leq i_1$ became $0<i_1$. It's fixed now. – Arthur Aug 12 '19 at 5:18

The $$i_k$$ are all ordered and distinct (because of the strict inequalities) and may assume values from a set of $$M$$ ($$0$$ to $$M-1$$ inclusive). It follows that once you choose $$n+1$$ distinct values out of the set of $$M$$ for the $$i_k$$, the $$i_k$$ are completely determined. Thus there are $$\binom M{n+1}$$ summands.