Prove que:
Passo 1
Estamos querendo provar a identidade para coeficientes binomiais
O que vamos usar é a interpretação combinatória:
conta o número de maneiras de escolher
elementos de um conjunto com
elementos.
Passo 2
Escolhemos um elemento especial do conjunto de tamanho
; vamos chamá-lo de “
”. Vamos separar todas as escolhas de
elementos em dois casos disjuntos:
- As escolhas que não incluem
.
O número de maneiras de escolherelementos dentre os sem usar é o mesmo que escolher de um conjunto de tamanho . Logo esse caso contribui com
Passo 3
- As escolhas que incluem
.
Sejá está incluído, precisamos escolher mais elementos dentre os outros . O número de maneiras de fazer isso é
Passo 4
Como esses dois casos (incluir
e não incluir
) são mutuamente exclusivos e cobrem todas as possibilidades de escolha de
elementos, somamos as quantidades:
Resposta
A identidade está provada: