Problema 1 ( 6.0 pontos) Sejam ell, m, n in N. Provar que,
(3.0 pontos) se ell <= m <= n, entào
sumk=0^ellbinommkbinomnell-k=binomm+nell

Passo 1

O enunciado pede para provar que, dados ell,m,ninN com ell<= m<= n, vale a identidade
sumk=0^ellbinommkbinomnell-k ,=,binomm+nell
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 ell objetos de um total de m+n.

Passo 2

Considere dois conjuntos disjuntos A e B, com |A|=m e |B|=n. Queremos contar de duas maneiras quantas formas há de escolher um subconjunto de tamanho ell em Acup B.

Passo 3

Seja k o número de elementos escolhidos em A. Então:
1. Escolher k em A pode ser feito de binommk maneiras.
2. Dos ell totais, os ell-k restantes vêm de B, o que pode ser feito de binomnell-k maneiras.
3. Como k pode variar de 0 até ell, o total de escolhas é
sumk=0^elll[binommkbinomnell-kr]

Passo 4

Por outro lado, escolher diretamente ell elementos de Acup B, que tem m+n elementos, é feito em binomm+nell maneiras. Como estamos contando a mesma coisa de duas formas, segue-se a identidade desejada:
sumk=0^ellbinommkbinomnell-k ;=;binomm+nell

Resposta

sumk=0^ellbinommkbinomnell-k=binomm+nell

Exercícios relacionados