Sendo
. Mostre que:
Passo 1
O enunciado pede para mostrar que, para
com
, vale a identidade combinatória
O conteúdo aqui é coeficiente binomial e argumento de contagem por partição de casos.
Passo 2
Lembramos que
é o número de maneiras de escolher
elementos de um conjunto com
elementos distintos. Vamos contar essas escolhas separando em dois casos, de forma que a soma desses casos cubra todas as escolhas possíveis.
Passo 3
Caso 1: as combinações que incluem um elemento fixo (por exemplo, o elemento de índice
). Se esse elemento está presente, restam
vagas para preencher entre os outros
elementos. Logo, o número de combinações desse tipo é
Passo 4
Caso 2: as combinações que não incluem esse mesmo elemento fixo. Nesse caso, temos que escolher os
elementos apenas entre os
restantes, o que dá
Passo 5
Como todo subconjunto de tamanho
ou inclui o elemento
(Caso 1) ou não o inclui (Caso 2), o total de escolhas é a soma dos dois casos:
Mas esse total é justamente
. Assim, concluímos a identidade desejada.