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

Question

How many summands does $\sum_{0\le i_1<i_2<...<i_{n+1}<M} a_{i_1},_{i_2},..._{i_{n+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.

Answer 1

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<i_2<\cdots<i_n<i_{n+1}<M $$ 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}} $$

Answer 2

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.