# Proof Question regarding product sum and series

The question is let $\{m_1, m_2, m_3, \dots \}$ be a sequence of numbers where $m_k\geq 0$ for every $k \geq 1$.

Let $$M_n = \sum_{k=1}^n m_k$$ when $n \geq 1$ is an integer.

Show that if $$\prod_{k=1}^{n-1}{(M_k+1)\choose(M_k)}= \frac{(m_1+m_2+\cdots+m_n)!}{(m_1!m_2!\cdots m_n!)}$$

When I try I get an expansion that is for example the first term and I choose a random letter in this case 2 for $m_1$ the number $2!+1\over 2!(2+1-2)!$.

Is this the correct way to expand this series?

Thanks in advance. Let me know if anything should be clarified.

• Is it ${(M_k + 1) \choose (M_k)}$ as you wrote or ${(M_{k+1}) \choose (M_k)}$? And what should be read after "Show that if''? Right now, your sentence does not make much sense. – laurent Jul 10 '15 at 9:13

## 2 Answers

A straight proof

So, let us fix some integer $k$.

What is the difference between $M_{k+1}$ and $M_k$? Unsurprisingly, it is $m_{k+1}$.

Now what is the value of ${M_{k+1} \choose M_k}$? Thanks to our first remark, we may write it as ${M_k + m_{k+1} \choose M_k}$. Therefore we may write,

$${M_{k+1} \choose M_k} = \frac{(M_k + m_{k+1})!}{M_k!m_{k+1}!} = \frac{(M_k + 1)(M_k + 2) \cdots (M_{k+1} - 1)M_{k+1}}{m_{k+1}!}.$$

Put all these terms together and you'll be fine!

More specifically,

$$(m_1 + m_2 + \cdots + m_n)! = 1 \cdot 2 \cdot \cdots \cdot m_1 \cdot (m_1+1) \cdot \cdots (m_1 + m_2) \cdots (m_1 + m_2 + m_3) \cdots (m_1 + m_2 + \cdots + m_n)$$

Since $M_k = \sum_{i=1}^k m_i$, this huge product can be seen as

$$\prod_{k=0}^n \left[(M_k+1)(M_k+2) \cdots (M_{k+1}-1)M_{k+1}\right]$$

• I really dont understand, how do you get the terms together? I suppose it is very simple. – addde Jul 10 '15 at 13:32

A proof with double counting argument

The term on the right is the number of ways of partitioning a set of size $M_n$ into $n$ sets of sizes $m_1,m_2, \ldots, m_n$.

You may see this process as picking $m_n$ elements among the set of size $M_n$ which is possible in ${ M_n \choose m_n} = {M_n \choose M_{n-1}}$ ways. And then you need to pick $m_{n-1}$ elements among the $M_{n-1}$ remaining elements. Multiplying all these terms, you obtain the left side of your equation.

Since we counted twice the same quantity, both terms should be equal.

Aigner and Zeigler wrote a nice chapter [1, Chapter 25] about double counting in their celebrated book "Proofs from the Book"

[1] Martin Aigner and Günter M. Ziegler, Proofs from the Book (4th edition), Springer, 2010.