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


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


$$ {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? :/

  • $\begingroup$ Apply upper negation to each of the three binomial coefficients, and recognize it as Vandermonde's convolution. $\endgroup$ – 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

  • $\begingroup$ Great! thank you very much! $\endgroup$ – 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.


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

  • $\begingroup$ 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? $\endgroup$ – Darío A. Gutiérrez Jul 23 '16 at 8:29
  • $\begingroup$ @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. $\endgroup$ – Markus Scheuer Jul 23 '16 at 12:58

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

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}

  • $\begingroup$ 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} $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – darij grinberg Jul 23 '16 at 2:47
  • $\begingroup$ 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. $\endgroup$ – Batominovski Jul 23 '16 at 2:50
  • $\begingroup$ 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. $\endgroup$ – Batominovski Jul 23 '16 at 2:57
  • $\begingroup$ 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). $\endgroup$ – darij grinberg Jul 23 '16 at 12:21
  • $\begingroup$ @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. $\endgroup$ – Batominovski Jul 23 '16 at 12:25

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.