Proposição:  É válida a seguinte identidade combinatória

\dbinom{n+m}{r}=\displaystyle\sum_{j=0}^{r}\dbinom{n}{j}\dbinom{m}{r-j}

que é a chamada convolução de Vandermonde.

Pondo n=m, obtém-se

\dbinom{2n}{r}=\displaystyle\sum_{j=0}^{r}\dbinom{n}{j}\binom{n}{r-j}

e para r=n, finalmente,

\dbinom{2n}{n}=\displaystyle\sum_{j=0}^{r}\dbinom{n}{j}\dbinom{n}{n-j}=\displaystyle\sum_{j=0}^{n}\dbinom{n}{j}^{2}=\sum_{i=0}^{n}\dbinom{n}{i}^{2}.

\bigskip

Demonstração:

Existe uma demonstração meramente combinatória da convolução de Vandermonde:

Dado o conjunto C = \left\{ c_{1,}c_{2},\ldots,c_{n},c_{n+1},c_{n+2},\ldots ,c_{n+m}\right\}, considerem-se dois subconjuntos de C disjuntos, isto é, sem elementos comuns, um C_{1}=\left\{ c_{1,}c_{2},\ldots ,c_{n}\right\} com n elementos e outro com m, C_{2}=\left\{ c_{n+1,}c_{n+2},\ldots ,c_{n+m}\right\}, tais que C=C_{1}\cup C_{2}.

O segundo membro conta o número de maneiras distintas de escolher r elementos de entre os n+m de C.

Quanto ao primeiro membro, comecemos por reparar que

(a) há \dbinom{n}{j} maneiras distintas de escolher j elementos entre os n de C_{1};

(b) há \binom{m}{r-j} maneiras distintas de escolher r-j elementos  entre os m de C_{2};

(c) pelo que há \binom{n}{j}\binom{m}{r-j} maneiras distintas de seleccionar j elementos de C_{1} e simultaneamente r-j de C_{2}.

Ora, se somarmos todas estas parcelas \dbinom{n}{j}\dbinom{m}{r-j} para os possíveis valores que j pode tomar, desde j=0 até j=n, obtemos evidentemente o mesmo número \dbinom{n+m}{r}. Como mostrámos a igualdade dos dois membros da identidade da convolução de Vandermonde, concluímos a justificação. \blacksquare

Os casos particulares referidos obtêm-se imediatamente. A última identidade é também um caso particular de

Quaisquer que sejam os inteiros  k  e n tais que 0\leq k \leq n,  tem-se

\displaystyle\sum_{i=k}^{n}\dbinom{n}{i}^{2}\dbinom{i}{k}=\dbinom{n}{k}\dbinom{2n-k}{n}

que foi demonstrada aqui .