# Proving that ${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k}$

How can I prove that $${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k}$$

I tried the following:

We use the falling factorial power: $$y^{\underline k}=\underbrace{y(y-1)(y-2)\ldots(y-k+1)}_{k\text{ factors}},$$ so that $\binom{y}k=\frac{y^{\underline k}}{k!} .$

Then

$${x +y+n- 1 \choose n} = \frac{(x +y+n- 1)!}{n! ((x +y+n- 1) - n)!} = \frac{1}{n!}. (x +y+n \color{#f00}{-1})^{\underline n}$$

And

$${x+n-k-1 \choose n-k}{y+k-1 \choose k}$$ $$\frac{1}{(n-k)!}.(x+n-k-1)^{\underline{n-k}}.\frac{1}{k!}.(y+k-1)^{\underline{k}}$$ $$\frac{1}{k!.(n-k)!}.(x+n-k-1)^{\underline{n-k}}.(y+k-1)^{\underline{k}}$$ $$\sum_{k=0}^n{n \choose k}(x+n-k-1)^{\underline{n-k}}.(y+k-1)^{\underline{k}}$$

According to the Binomial-coefficients:

$$((x+n-k-1) + (y+k-1))^{\underline{n}}$$ $$(x+y+n\color{#f00}{- 2})^{\underline{n}}$$

What is wrong ? und How can I continue? :/

• Apply upper negation to each of the three binomial coefficients, and recognize it as Vandermonde's convolution. – darij grinberg Jul 23 '16 at 2:44

Using Negative Binomial Coefficients and Vandermonde's Identity, we get \begin{align} \sum_{k=0}^n\binom{x+n-k-1}{n-k}\binom{y+k-1}{k} &=\sum_{k=0}^n(-1)^{n-k}\binom{-x}{n-k}(-1)^k\binom{-y}{k}\tag{1}\\ &=(-1)^n\sum_{k=0}^n\binom{-x}{n-k}\binom{-y}{k}\tag{2}\\ &=(-1)^n\binom{-x-y}{n}\tag{3}\\ &=\binom{n+x+y-1}{n}\tag{4} \end{align} Explanation:
$(1)$: Negative Binomial Coefficient conversion
$(2)$: algebra
$(3)$: Vandermonde's Identity
$(4)$: Negative Binomial Coefficient conversion

• Great! thank you very much! – Darío A. Gutiérrez Jul 23 '16 at 8:20

Hint: The binomial formula with the Cauchy product \begin{align*} (x+y)^n=\sum_{k=0}^n\binom{n}{k}x^ky^{n-k} \end{align*} does not use falling factorials $x^{\underline{k}}$ resp. $y^{\underline{n-k}}$.

Here is a step by step answer similar to that by @MarkoRiedel. It's convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g. \begin{align*} \binom{n}{k}=[z^k](1+z)^n \end{align*}

We obtain

\begin{align*} \sum_{k=0}^{n}&\binom{x-1+n-k}{n-k}\binom{y-1+k}{k}\\ &=\sum_{k=0}^{\infty}\binom{x-1+n-k}{n-k}\binom{-y}{k}(-1)^k\tag{1}\\ &=\sum_{k=0}^\infty [t^{n-k}](1+t)^{x-1+n-k}[z^k](1+z)^{-y}(-1)^k\tag{2}\\ &=[t^n](1+t)^{x-1+n}\sum_{k=0}^\infty(-1)^kt^k(1+t)^{-k}[z^k](1+z)^{-y}\tag{3}\\ &=[t^n](1+t)^{x-1+n}\sum_{k=0}^\infty\left(-\frac{t}{1+t}\right)^k[z^k](1+z)^{-y}\\ &=[t^n](1+t)^{x-1+n}\left(1-\frac{t}{1+t}\right)^{-y}\tag{4}\\ &=[t^n](1+t)^{x+y-1+n}\tag{5}\\ &=\binom{x+y-1+n}{n} \end{align*} and the claim follows.

Comment:

• In (1) we use the binomial identity $\binom{-p}{q}(-1)^q=\binom{p+q-1}{q}$ and we extend the upper limit of the series to $\infty$ without changing anything since we are adding zeros only.

• In (2) we apply the coefficient of operator twice.

• In (3) we do some rearrangements by using the linearity of the coefficient of operator and we also use the rule \begin{align*} [z^{p-q}]A(z)=[z^p]z^{q}A(z) \end{align*}

• In (4) we apply the substitution rule \begin{align*} A(t)=\sum_{k=0}^\infty a_kt^k=\sum_{k=0}^\infty t^k[z^k]A(z)\\ \end{align*} with $z=-\frac{t}{1+t}$.

• In (5) we do some simplifications.

• In (6) we select the coefficient from $t^n$.

We have $$\sum_{k=0}^n {y-1+k\choose k} {x-1+n-k\choose n-k} = \sum_{k=0}^n [z^{k}] \frac{1}{(1-z)^y} [z^{n-k}] \frac{1}{(1-z)^x} \\ = [z^n] \frac{1}{(1-z)^y} \frac{1}{(1-z)^x} = [z^n] \frac{1}{(1-z)^{x+y}} ={x+y-1+n\choose n}.$$

• I do not understand the following calculation: $${y-1+k\choose k} {x-1+n-k\choose n-k} = [z^{k}] \frac{1}{(1-z)^y} [z^{n-k}] \frac{1}{(1-z)^x}$$ Can you give me more information? – Darío A. Gutiérrez Jul 23 '16 at 8:29
• @DarioGutierrez: $[z^k]$ is the coefficient of operator used to denote the coefficient of $z^k$ in a series $A(z)=\sum_{n=0}^\infty a_nz^n$. You might find this answer helpful which is somewhat more verbose. – Markus Scheuer Jul 23 '16 at 12:58


Hereafter, I'll use the identities: $$\left\lbrace\begin{array}{rcl} \ds{a \choose b} & \ds{=} & \ds{{-a + b - 1 \choose b}\pars{-1}^{b} \,,\quad b \in \mathbb{Z}} \\[5mm] \ds{a \choose b} & \ds{=} & \ds{\oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{a} \over z^{b + 1}} \,{\dd z \over 2\pi\ic}\,,\quad b \in \mathbb{Z}} \\[5mm] \ds{\pars{1 + z}^{a}} & \ds{=} & \ds{\sum_{b = 0}^{\infty}{a \choose b}z^{b}\,, \quad\verts{z} < 1} \end{array}\right.$$

\begin{align} &\color{#f00}{\sum_{k = 0}^{n}{x + n - k - 1 \choose n - k} {y + k - 1 \choose k}} = \sum_{k = 0}^{\infty}\bracks{{-x \choose n - k}\pars{-1}^{n - k}} \bracks{{-y \choose k}\pars{-1}^{k}} \\[5mm] = & \pars{-1}^{n}\sum_{k = 0}^{n}{-y \choose k}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-x} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic} = \pars{-1}^{n}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-x} \over z^{n + 1}}\sum_{k = 0}^{\infty}{-y \choose k}z^{k}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{-1}^{n}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-x - y} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} = \pars{-1}^{n}{-x - y \choose n} = \pars{-1}^{n}{x + y + n - 1 \choose n}\pars{-1}^{n} \\[5mm] = &\ \color{#f00}{{x + y + n - 1 \choose n}} \end{align}

• What methods you use for demonstrations? Can yo explain me the following calculation? \begin{align} &\sum_{k = 0}^{\infty}\bracks{{-x \choose n - k}\pars{-1}^{n - k}} \bracks{{-y \choose k}\pars{-1}^{k}} = & \pars{-1}^{n}\sum_{k = 0}^{n}{-y \choose k}\color{#f00}{\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-x} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic}} \end{align} – Darío A. Gutiérrez Jul 23 '16 at 18:53

The multiset numbers $(\!\tbinom{m}{r}\!)=\binom{m+r-1}{r}$ count the multisets of cardinality $r$ with elements drawn from a set of size $m$. Using the multiset numbers, the identity becomes:

$$\left(\!\tbinom{x+y}{n}\!\right)=\sum_{k=0}^n \left(\!\tbinom{x}{n-k}\!\right) \left(\!\tbinom{y}{k}\!\right)$$

This has more or less the same combinatorial interpretation as the Vandermonde convolution identity for binomial coefficients. Any $n$-multiset built from the union of two sets of sizes $x$ and $y$ is uniquely a union of an $(n-k)$-multiset built from the set of size $x$ and a $k$-multiset built from the set of size $y$ for some $0\le k\le n$.

Geometric Solution: Assume that the based field is $\mathbb{K}$, which is of characteristic $0$. Prove that the equality holds when $x$ and $y$ are integers (for example, via combinatorial arguments). Now, $\mathbb{Z}^2$ (as well as $\mathbb{N}^2$) is a Zariski-dense subset of $\mathbb{K}^2$. Therefore, the equality holds for all $(x,y)\in\mathbb{K}^2$, noting that both sides are polynomials.

• Proving it (or, equivalently, the Vandermonde identity) bijectively for arbitrary integers is easier said than done. There are six possible cases (depending on the signs of $x$ and $y$ and $x+y$, for Vandermonde), and I suspect each of them requires a different bijective proof. – darij grinberg Jul 23 '16 at 2:47
• That is why I also mentioned that $\mathbb{N}^2$ is also dense. If one doesn't want to deal with signs, then one only needs to handle the case where $x$ and $y$ are nonnegative integers. – Batominovski Jul 23 '16 at 2:50
• In fact, I'm the only one here who explicitly mentions how to deal with non-integral $x$ and $y$. The answer that comes closest in terms of dealing with non-integral inputs is robjohn♦'s, but it doesn't show why Vandermonde's Identity is true for non-integral inputs. – Batominovski Jul 23 '16 at 2:57
• I'd say the validity of Vandermonde's identity for arbitrary $x$ and $y$ is rather well-known (it's even on the Wikipedia page, just buried far down). – darij grinberg Jul 23 '16 at 12:21
• @darijgrinberg The same can be said about many questions on MSE. Hence, we shouldn't give out sketches of the proofs of well known facts, according to your logic. – Batominovski Jul 23 '16 at 12:25