A identidade de Vandermonde (ou convolução de Vandermonde) afirma que, para inteiros não negativos m, n, r,
\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}
a) Dê uma interpretação combinatória para a identidade e prove-a utilizando essa interpretação.
b) Prove a identidade algébrica mostrando que ambos os lados são iguais ao coeficiente de x^{r} em (1+x)^{m+n}.
c) Use a identidade para calcular \sum_{k=0}^{4}\binom{5}{k}\binom{3}{4-k}.
d) Explique brevemente como essa identidade corresponde à convolução de sequências e onde isso aparece em problemas de contagem.

Passo 1

O enunciado dá a identidade de Vandermonde para inteiros não negativos \,m,n,r:
\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}.
As perguntas são:
a) Dar uma interpretação combinatória e provar a identidade usando essa interpretação.
b) Provar a identidade algébrica mostrando que ambos os lados são iguais ao coeficiente de x^{r} em (1+x)^{m+n}.
c) Calcular \sum_{k=0}^{4}\binom{5}{k}\binom{3}{4-k}.
d) Explicar brevemente como a identidade corresponde à convolução de sequências e onde isso aparece em problemas de contagem.
As informações relevantes fornecidas são a fórmula acima e que m,n,r são inteiros não negativos; a soma no lado esquerdo é em k de 0 até r (valores fora do intervalo naturalmente produzem binomiais nulos).

Passo 2

Antes de provar, vale revisar o que significa \binom{a}{b} e por que aparece em contagem.
A definição concreta: \binom{a}{b} é o número de maneiras de escolher b elementos de um conjunto com a elementos, sem ordem. Em notação:
\binom{a}{b}=\frac{a!}{b!(a-b)!},
quando 0\le b\le a; se b<0 ou b>a então \binom{a}{b}=0. Aqui a! é o fatorial de a.
Exemplo rápido para fixar: \binom{5}{2}=10 conta os pares distintos escolhidos de um conjunto de 5 elementos.

Passo 3

Interpretação combinatória para a identidade (ideia central). Pense em um conjunto total com m+n elementos dividido em duas partes disjuntas: um bloco A com m elementos e um bloco B com n elementos. Queremos contar de duas maneiras o número de subconjuntos de tamanho r desse conjunto total. Essa contagem é o que a identidade relaciona.

Passo 4

Prova combinatória passo a passo.
  1. Contagem direta (lado direito): O número de maneiras de escolher um subconjunto de tamanho r dentre os m+n elementos é exatamente
\binom{m+n}{r}.
  1. Contagem por casos (lado esquerdo): Para cada subconjunto de tamanho r podemos olhar quantos elementos dele vêm do bloco A. Seja k o número de elementos escolhidos de A. Então k pode variar de 0 até r, mas também tem de obedecer k\le m e r-k\le n; valores fora desses limites dão binomiais nulos automaticamente. Para um dado k:
  • Escolher k elementos de A pode ser feito de \binom{m}{k} maneiras.
  • Escolher os restantes r-k elementos de B pode ser feito de \binom{n}{r-k} maneiras.
    Como as escolhas nos dois blocos são independentes, para aquele k totalizamos \binom{m}{k}\binom{n}{r-k} subconjuntos. Somando sobre todos os possíveis k obtemos o número total de subconjuntos de tamanho r:
\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}.
  1. Concluímos que ambas as contagens contam exatamente o mesmo conjunto (subconjuntos de tamanho r do conjunto total), logo são iguais:
\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}.
Essa é a prova combinatória. É simples, intuitiva e muito utilizada: partimos a escolha em “quantos tiro do primeiro grupo” e somamos sobre as possibilidades.

Passo 5

Agora a prova algébrica via coeficiente em polinômios. Primeiro revisamos o Teorema Binomial (lição rápida): para inteiro não negativo t,
(1+x)^{t}=\sum_{i=0}^{t}\binom{t}{i}x^{i}.
Aqui o coeficiente de x^{i} em (1+x)^{t} é \binom{t}{i}. Isso decorre da definição do binômio e da expansão combinatória.

Passo 6

Multiplicação das séries e coeficiente (parte crucial). Considere
(1+x)^{m+n}=(1+x)^{m}(1+x)^{n}.
Expandindo cada fator com o teorema binomial:
(1+x)^{m}=\sum_{k=0}^{m}\binom{m}{k}x^{k},\qquad (1+x)^{n}=\sum_{j=0}^{n}\binom{n}{j}x^{j}.
O produto é, por produto de séries (ou produto de polinômios), dado por a soma cauchy:
(1+x)^{m+n}=\sum_{r=0}^{m+n}\left(\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}\right)x^{r}.
Explicando o passo: ao multiplicar as séries, para obter o termo em x^{r} somamos todos os produtos de termos x^{k} do primeiro por x^{r-k} do segundo; os coeficientes multiplicam, daí a soma interior.
Mas também sabemos diretamente pelo teorema binomial que o coeficiente de x^{r} em (1+x)^{m+n} é \binom{m+n}{r}. Como a escrita em série é única, igualamos coeficientes:
\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}.
Isso dá a prova algébrica pedida: ambos os lados são o coeficiente de x^{r} em (1+x)^{m+n}.

Passo 7

Exemplo numérico (parte c). Vamos calcular
\sum_{k=0}^{4}\binom{5}{k}\binom{3}{4-k}.
Pela identidade de Vandermonde, com m=5, n=3 e r=4, o valor é simplesmente \binom{5+3}{4}=\binom{8}{4}. Mas vamos também expandir explicitamente para treinar:
Termos não nulos ocorrem quando 0\le k\le 5 e 0\le 4-k\le 3, isto é 1\le k\le 4 também funciona; computamos cada termo:
\begin{aligned} k=0:&\quad \binom{5}{0}\binom{3}{4}=1\cdot 0=0,\\\ k=1:&\quad \binom{5}{1}\binom{3}{3}=5\cdot 1=5,\\\ k=2:&\quad \binom{5}{2}\binom{3}{2}=10\cdot 3=30,\\\ k=3:&\quad \binom{5}{3}\binom{3}{1}=10\cdot 3=30,\\\ k=4:&\quad \binom{5}{4}\binom{3}{0}=5\cdot 1=5. \end{aligned}
Somando:
0+5+30+30+5=70.
Também \binom{8}{4}=\dfrac{8\cdot7\cdot6\cdot5}{4\cdot3\cdot2\cdot1}=70, confirma.

Passo 8

Explicação sobre convolução e onde aparece (parte d).
Definimos duas sequências (iniciando em índice k) a_k=\binom{m}{k} e b_k=\binom{n}{k}, com a convenção de que termos com índice fora do intervalo apropriado são zero. A convolução discreta dessas sequências é a sequência c_r dada por
c_r=(a*b)_r=\sum_{k}a_k b_{r-k}=\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}.
A identidade de Vandermonde diz que c_r=\binom{m+n}{r}. Ou seja, a convolução de duas sequências de coeficientes binomiais dá os coeficientes binomiais do somatório dos expoentes. Isso aparece naturalmente quando multiplicamos polinômios (ou geradores formais): o coeficiente do produto é a convolução dos coeficientes, exatamente o que usamos na prova algébrica. Em problemas de contagem, essa propriedade surge sempre que repartimos uma escolha em duas partes independentes (como no argumento combinatório): o número total de modos de obter um resultado composto é a soma (convolução) de combinações de escolhas parciais. Aparece também em probabilidades (soma de variáveis binomiais independentes), em teoria de geradores funcionais e em combinatória enumerativa em geral.

Passo 9

Recapitulando de forma motivadora: a identidade é uma ferramenta poderosa porque une uma explicação clara (contar por casos) com uma identidade algébrica elegante (coeficientes em produto de polinômios). Se estiver nervoso para a prova, lembre: normalmente é suficiente lembrar “conte direto” vs “conte por casos (quantos peguei do primeiro grupo)” ou "coeficiente de x^{r} em (1+x)^{m}(1+x)^{n}" — qualquer uma das duas vias resolve a prova rápida e seguramente.

Resposta

a) Contagem por casos: contar subconjuntos de tamanho r de um conjunto com m+n elementos dividido em dois blocos de tamanhos m e n. Para cada k escolhemos k de m e r-k de n, somando obtemos \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}.
b) Pelo Teorema Binomial, (1+x)^{m+n}=(1+x)^{m}(1+x)^{n}. Expandindo e igualando o coeficiente de x^{r} obtemos \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}.
c) \displaystyle 70.
d) A identidade é a convolução discreta dos coeficientes \binom{m}{k} e \binom{n}{k}: (a*b)_r=\sum_{k}a_k b_{r-k}. Aparece ao multiplicar polinômios (coeficientes do produto), em problemas que dividem uma escolha em duas partes, e em somas de variáveis binomiais independentes.

Exercícios relacionados