(Inicialmente publicada nesta entrada.)
Proposição: É válida a seguinte identidade combinatória
que é a chamada convolução de Vandermonde.
Pondo , obtém-se
e para finalmente,
.
Demonstração:
Existe uma demonstração meramente combinatória da convolução de Vandermonde:
Dado o conjunto
, considerem-se dois subconjuntos de
disjuntos, isto é, sem elementos comuns, um
com
elementos e outro com
,
, tais que
O segundo membro conta o número de maneiras distintas de escolher elementos de entre os
de
.
Quanto ao primeiro membro, comecemos por reparar que
(a) há maneiras distintas de escolher
elementos entre os
de
(b) há maneiras distintas de escolher
elementos entre os
de
(c) pelo que há maneiras distintas de seleccionar
elementos de
e simultaneamente
de
.
Ora, se somarmos todas estas parcelas para os possíveis valores que
pode tomar, desde
até
, obtemos evidentemente o mesmo número
. Como mostrámos a igualdade dos dois membros da identidade da convolução de Vandermonde, concluímos a justificação.
Os casos particulares referidos obtêm-se imediatamente. A última identidade é também um caso particular de
Proposição: Quaisquer que sejam os inteiros e
tais que
, tem-se
que foi demonstrada aqui e que repito.
Demonstração:
Comecemos por reparar que poderíamos ter escolhido para limite inferior do somatório , em vez de
, porque para
,
, por convenção usual.
O segundo membro (lado direito) conta o número de maneiras diferentes de escolher elementos dum conjunto, tal como
com
elementos e, ao mesmo tempo,
elementos doutro conjunto, por exemplo
com
elementos.
Quanto ao primeiro membro, considerem-se dois subconjuntos de disjuntos (sem elementos comuns), um
com
elementos, e outro
com
elementos, tais que
Escolhamos agora elementos de
pertencendo
deles a
e
a
com
.
(a) Há maneiras diferentes de escolher
elementos entre os
de
;
(b) há maneiras diferentes de escolher
elementos entre os
de
;
(c) daqui decorre que, para um dado , há
maneiras distintas de seleccionar esses
elementos de
. Assim, cada parcela,
conta o número de maneiras diferentes de escolher
elementos de
(dos quais
) e, simultaneamente,
de
Somando, para todos os possíveis valores de
, estas parcelas, obtemos o número total
A primeira igualdade é justificada por
e a segunda pela observação inicial.
É claro que as duas contagens, a directa representada pelo produto do segundo membro e a indirecta, pela soma do primeiro (lado esquerdo) hão-de ser iguais, o que mostra
,
como pretendíamos.
Nota: o leitor poderá ver várias demonstrações algébricas e analíticas no blogue Fatos Matemáticos do Prof. Paulo Sérgio, na entrada Algumas Demonstrações da Convolução de Vandermonde-Euler.