Problema 1 ( 6.0 pontos) Sejam
. Provar que,
(3.0 pontos) se
, entào
(3.0 pontos) se
Passo 1
O enunciado pede para provar que, dados
com
, vale a identidade
O conteúdo aqui é combinação de coeficientes binomiais e a aplicação da chamada Vandermonde’s convolution. Vamos usar um argumento combinatório, pensando em escolher
objetos de um total de
.
Passo 2
Considere dois conjuntos disjuntos
e
, com
e
. Queremos contar de duas maneiras quantas formas há de escolher um subconjunto de tamanho
em
.
Passo 3
Seja
o número de elementos escolhidos em
. Então:
. Escolher
em
pode ser feito de
maneiras.
. Dos
totais, os
restantes vêm de
, o que pode ser feito de
maneiras.
. Como
pode variar de
até
, o total de escolhas é
Passo 4
Por outro lado, escolher diretamente
elementos de
, que tem
elementos, é feito em
maneiras. Como estamos contando a mesma coisa de duas formas, segue-se a identidade desejada: