2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}} $$

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

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.

$\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.