Is there any way to simplify $\sum_{i=0}^n \binom{x}{i} \binom{y}{i + 1}$?

58 Views Asked by At

All these numbers are naturals and $$n \leq x\,,\quad\left(n + 1\right) \leq y$$

2

There are 2 best solutions below

4
On

A simple sub-case ($n\geq\max(x,y-1)$) can be solved through Vandermonde's identity.

If you write your sum as $$ \sum_{i\geq 0}\binom{x}{x-i}\binom{y}{i+1} $$ you may easily recognize a convolution, equal to the coefficient of $z^{x+1}$ in the product between $(1+z)^x$ and $(1+z)^y$. And the coefficient of $z^{x+1}$ in $(1+z)^{x+y}$ is simply: $$ \binom{x+y}{x+1} = \binom{x+y}{y-1}$$

0
On

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#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}$ \begin{align} \sum_{i = 0}^{n}{x \choose i}{y \choose i + 1} & = \bracks{z^{n}}\sum_{\ell = 0}^{\infty}z^{\ell}\bracks{\sum_{i = 0}^{\ell}{x \choose i}{y \choose i + 1}} = \bracks{z^{n}}\sum_{i = 0}^{\infty}{x \choose i}{y \choose i + 1} \sum_{\ell = i}^{\infty}z^{\ell} \\[5mm] & = \bracks{z^{n}}\sum_{i = 0}^{\infty}{x \choose i}{y \choose i + 1} \sum_{\ell = 0}^{\infty}z^{\ell + i} = \bracks{z^{n}}\bracks{\pars{1 - z}^{-1}\sum_{i = 0}^{\infty}{x \choose i} {y \choose y - i - 1}z^{i}} \\[5mm] = &\ \bracks{z^{n}}\bracks{\pars{1 - z}^{-1}\sum_{i = 0}^{\infty}{x \choose i}z^{i} \bracks{w^{y - i - 1}}\pars{1 + w}^{y}} \\[5mm] = &\ \bracks{z^{n}}\braces{\pars{1 - z}^{-1}\bracks{w^{y - 1}} \bracks{\pars{1 + w}^{y}\sum_{i = 0}^{\infty}{x \choose i}\pars{zw}^{i}}} \\[5mm] = &\ \bracks{z^{n}}\braces{\vphantom{\LARGE A}\pars{1 - z}^{-1}\bracks{w^{y - 1}} \bracks{\vphantom{\Large A}\pars{1 + w}^{y}\pars{1 + zw}^{x}}} \\[5mm] = & {1 \over \pars{y - 1}!}\bracks{z^{n}}\braces{\pars{1 - z}^{-1} \left.\,\partiald[\,y - 1]{}{w}\bracks{\pars{1 + w}^{y}\pars{1 + zw}^{x}} \right\vert_{\ w\ =\ 0}} \end{align}

The 'possible answer' still like cumbersome !!!.