# generalization of multisets

Prove that for any $$c,d \in \mathbb{R}$$ and $$k\in\mathbb{N}, \left({c+d\choose k}\right) = \sum_{j=0}^k \left({c\choose j}\right) \left({d\choose k-j}\right).$$

I know how to show that $${a+b\choose k} = \sum_{j=0}^k {a\choose j}{b\choose k-j}$$ for $$a,b\in \mathbb{R}$$ using an algebraic proof, but I'm not sure how to show the multiset version of this. I know that $$\left({n\choose k}\right) = {n+k-1\choose k}$$. But if we insisted that $$c,d\in\mathbb{N},$$ I think I might be able to come up with a combinatorial proof. Let $$S$$ denote the set of $$j$$-multisets (i.e. of size $$j$$) of $$[1,\cdots, c+d]$$. Let $$C_j$$ denote the set of multisets of size $$j$$ from $$[1,\cdots, c]$$ and $$D_{k-j}$$ denote the set of multisets of size $$k-j$$ from $$[c+1,\cdots, c+d]$$. Let $$E_j$$ denote the set of $$k$$-multisets from $$[1,\cdots, c+d]$$ with $$j$$ elements from $$[1,\cdots, c].$$ Observe that each $$E_j$$ is disjoint, and $$S = \cup_{j=0}^k E_j\Rightarrow |S| = \sum_{j=0}^k |E_j|\tag{1}.$$ Also, it is not difficult to define a bijection $$f : E_j \to C_j \times D_{k-j}.$$ Since $$|C_j| = \left({c\choose j}\right)$$ and $$|D_{k-j}| = \left({d\choose k-j}\right)$$ and $$|E_j| = |C_j||D_{k-j}|$$, substituting these results into $$(1)$$ gives the desired equality. But of course, this only works for $$c,d\in \mathbb{N}.$$

For fixed $$k\in\Bbb N$$ the expression

$$p(c,d)=\left(\!\!\binom{c+d}k\!\!\right)-\sum_{j=0}^k\left(\!\!\binom{c}j\!\!\right)\left(\!\!\binom{d}{k-j}\!\!\right)$$

is a polynomial in $$c$$ and $$d$$. If we fix $$c\in\Bbb N$$, it becomes a polynomial in $$d$$. Either this polynomial is identically $$0$$, or it has only finitely many zeroes. Since it is $$0$$ for each $$d\in\Bbb N$$, it must be identically $$0$$. Thus, $$p(n,d)=0$$ for each $$n\in\Bbb N$$ and $$d\in\Bbb R$$. But we can now hold $$d$$ fixed and view $$p(c,d)$$ as a polynomial in $$c$$, and by the same argument that polynomial must be identically $$0$$. Thus, $$p(c,d)=0$$ for all $$c,d\in\Bbb R$$.

• Why must it be the case that the polynomial is identically $0$ (which I believe means it's always $0$) or it has only finitely many zeroes? Also, why is it zero for each $d \in \mathbb{N}$?
– user747916
Aug 17, 2020 at 22:25
• @user3472: That’s a basic fact about polynomials: a real polynomial in one variable of degree $n$ has at most $n$ zeroes unless it’s the constant zero polynomial. Your combinatorial argument shows that $p(c,d)=0$ for $c,d\in\Bbb N$. Aug 17, 2020 at 22:27
• @user3472: You’re welcome. Aug 17, 2020 at 23:08
• @user3472: For a fixed $d\in\Bbb R$ we have a polynomial $f(x)=p(x,d)$ in one variable. We know that $f(x)=0$ for each $x\in\Bbb N$, so it has infinitely many zeroes, so it must be the constant zero polynomial. It’s exactly the same argument that I used before. Aug 18, 2020 at 2:13
• Okay, now I fully understand.
– user747916
Aug 18, 2020 at 2:16

$$\newcommand{\bbx}{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}{\mathcal{#1}} \newcommand{\mrm}{\mathrm{#1}} \newcommand{\pars}{\left(\,{#1}\,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}{\left\vert\,{#1}\,\right\vert}$$ $$\ds{\bbox[5px,#ffd]{\mbox{Prove that for any}\ c,d \in \mathbb{R}\ \mbox{and}\ k\in\mathbb{N}, \left(\!{c + d \choose k}\!\right) = \sum_{j = 0}^{k}\left(\!{c\choose j}\!\right) \left(\!{d\choose k - j}\!\right)}:\ {\Large ?}}$$.

\begin{align} &\bbox[#ffd,5px]{\sum_{j = 0}^{k}\left(\!{c\choose j}\!\right) \left(\!{d\choose k-j}\!\right)} = \sum_{j = 0}^{k}{c^{\,\large\overline{j}} \over j!} {d^{\,\overline{k - j}} \over \pars{k - j}!} \\[5mm] = &\ {\pars{c + d + k - 1}! \over \pars{c - 1}!\pars{d - 1}!}\,{1 \over k!} \sum_{j = 0}^{k}{k! \over j!\pars{k - j}!} {\Gamma\pars{c + j}\Gamma\pars{d + k - j} \over \Gamma\pars{c + d + k}} \\[5mm] = &\ {\pars{c + d + k - 1}! \over \pars{c - 1}!\pars{d - 1}!}\,{1 \over k!} \sum_{j = 0}^{k}{k \choose j}\int_{0}^{1}t^{c + j - 1} \pars{1 - t}^{d + k - j - 1}\,\dd t \\[5mm] = &\ {\pars{c + d + k - 1}! \over \pars{c - 1}!\pars{d - 1}!}\,{1 \over k!}\int_{0}^{1}t^{c - 1}\pars{1 - t}^{d + k - 1} \sum_{j = 0}^{k}{k \choose j}\pars{t \over 1 - t}^{j}\,\dd t \\[5mm] = &\ {\pars{c + d + k - 1}! \over \pars{c - 1}!\pars{d - 1}!}\,{1 \over k!} \int_{0}^{1}t^{c - 1}\pars{1 - t}^{d + k - 1}\, \pars{1 + {t \over 1 - t}}^{k}\,\dd t \\[5mm] = &\ {\pars{c + d + k - 1}! \over \pars{c - 1}!\pars{d - 1}!}\,{1 \over k!} \int_{0}^{1}t^{c - 1}\pars{1 - t}^{d - 1}\,\dd t \\[5mm] = &\ \require{cancel} {\pars{c + d + k - 1}! \over \cancel{\pars{c - 1}!\pars{d - 1}!}} \,{1 \over k!} \bracks{\cancel{\pars{c - 1}!\pars{d - 1}!} \over \pars{c + d - 1}!} = {c + d + k - 1 \choose k} \\[5mm] = &\ \bbx{\large\left(\!{c + d \choose k}\!\right)} \\ & \end{align}