Sejam ell, m, n in N. Provar que, se m <= ell <= n, então
sumk=0^mbinommkbinomnell-k=binomm+nell

Passo 1

Resumo do enunciado: temos três números naturais sumk=0^mbinommkbinomnell-k ;=;binomm+nell tais que e queremos provar a identidade
Conteúdo da matéria: coeficiente binomial e contagem combinatória (Vandermonde). Para resolver, vamos usar a interpretação de como “número de jeitos de escolher objetos dentre ”.

Passo 2

Antes de tudo, o que é binomab = a!b!(a-b)! ?
Por definição,
e, na prática, isso conta quantas formas distintas há de escolher elementos de um conjunto com elementos.

Passo 3

Agora, a ideia principal (prova combinatória): imagine que você tem dois grupos de pessoas,
  • Grupo A com pessoas,
  • Grupo B com pessoas.
Você quer escolher, no total, pessoas desses .

Passo 4

Contagem direta:
Se você pegar os binomm+nell juntos e escolher , há
jeitos de fazer isso.

Passo 5

Contagem “fatiada” (pela soma):
Vamos contar de outro jeito, quebrando por quantas pessoas vêm de A.
  • Suponha que você escolha exatamente binommktimesbinomnell-k pessoas do grupo A.
  • Então você precisa escolher sumk=0^mbinommkbinomnell-k pessoas do grupo B.
Para um dado , o número de formas é
Como pode variar de a , somamos todos esses casos:

Passo 6

Esses dois modos de contar o mesmo problema têm de dar o mesmo resultado. Logo, juntando as duas contagens, obtemos
sumk=0^mbinommkbinomnell-k ;=; binomm+nell

Resposta

boxedsumk=0^mbinommkbinomnell-k ;=;binomm+nell

Exercícios relacionados