Use the Pascal Identity to prove given equality.

139 Views Asked by At

Proof that given equality by using Pascal Identity

$$\binom{n}{n_1,n_2,...,n_m}=\sum_{i=1}^{m} \binom{n-1}{n_1,...,n_{i-1},n_{i+1},...,n_m}$$ where $n_1+n_2+...+n_m=n$ and $m, n_1, n_2, ... ,n_m$ are positive integers.

I proved it by using Combinatorial proof, but I'm wondering if there is chance to prove this by using Pascal Identity. how can I approach this? I thought about we have to start from the left side. Thanks for any help.

1

There are 1 best solutions below

0
On

You have asked for a proof of the identity $$\binom{n}{n_1,n_2,\ldots,n_m}=\sum_{i=1}^{m} \binom{n-1}{n_1,\ldots,n_{i-1},n_{i+1},\ldots,n_m}$$ where $n_1+n_2+\cdots +n_m=n$ and $m,n_1,n_2,\ldots, n_m$ are positive integers. As written, this does not make sense because a multinomial coefficient $$\binom{x}{x_1,x_2,\ldots, x_k}$$ must satisfy $$x=x_1+x_2+\cdots +x_k,$$ whereas if this were true for all your summands, then it would be the case that $$n-1=(n_1+n_2+\cdots + n_m-n_i)$$ for each $i\in[m],$ and that would imply that $$n_1=n_2=\cdots =n_m,$$ which is not necessarily true. So I'm not sure how you found a combinatorial proof of this identity. It does not even work if we blindly interpret your multinomial coefficients to mean $$\binom{n}{n_1,n_2,\ldots,n_m}=\frac{n!}{n_1!n_2!\cdots n_m!}$$ because then we would get \begin{align*} \sum_{i=1}^{m} \binom{n-1}{n_1,\ldots,n_{i-1},n_{i+1},\ldots,n_m} &= \frac{(n-1)!}{n_1!n_2!\cdots n_m!}\cdot (n_1!+n_2!+\cdots +n_m!)\\ &= \binom{n}{n_1,n_2,\ldots, n_m}\cdot \frac{n_1!+n_2!+\cdots +n_m!}{n}. \end{align*} If that were to equal $\displaystyle \binom{n}{n_1,n_2,\ldots, n_m},$ then we would have $$n_1!+n_2!+\cdots +n_m!=n.$$ But we are given that $n_1+n_2+\cdots +n_m=n,$ so this is not always true.

There is a different identity that is true and perhaps you meant that instead. It is a generalization of Pascal's identity:

If $n$ and $m$ are positive integers and $n_1,n_2,\ldots, n_m$ are positive integers such that $n_1+n_2+\cdots +n_m = n,$ then $$\binom{n-1}{n_1-1,n_2,\ldots, n_m}+\binom{n-1}{n_1,n_2-1,\ldots, n_m}+\cdots +\binom{n-1}{n_1,n_2,\ldots, n_m-1}=\binom{n}{n_1,n_2,\ldots, n_m}.$$ The proof is straightforward using the formula for multinomial coefficients in terms of factorials; it's just a matter of factoring out common factors. The proof is provided in the link above.