Sejam
. Provar que, se
, então
Passo 1
Resumo do enunciado: temos três números naturais
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 é
?
Por definição,
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 juntos e escolher
, há
Se você pegar os
jeitos de fazer isso.
Passo 5
Contagem “fatiada” (pela soma):
Vamos contar de outro jeito, quebrando por quantas pessoas vêm de A.
Vamos contar de outro jeito, quebrando por quantas pessoas vêm de A.
- Suponha que você escolha exatamente
pessoas do grupo A. - Então você precisa escolher
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