Prove, usando um argumento combinatório, que
para
.
Passo 1
O enunciado pede para provar, por contagem combinatória, que
para
.
O conteúdo aqui é a interpretação de coeficientes binomiais como número de formas de escolher subconjuntos de certos tamanhos numa coleção de elementos. Vamos contar de duas maneiras o mesmo objeto combinatório: um par
tal que
O conteúdo aqui é a interpretação de coeficientes binomiais como número de formas de escolher subconjuntos de certos tamanhos numa coleção de
Passo 2
Contagem pelo lado esquerdo. Primeiro escolhemos um subconjunto
de tamanho
em
de
maneiras. Em seguida, dentro de
, escolhemos um subconjunto
de tamanho
de
maneiras. Assim o número total de pares
é
Passo 3
Contagem pelo lado direito. Primeiro escolhemos o subconjunto
de tamanho
em
de
maneiras. Sobram
elementos em
; desses, escolhemos
para completar
a
elementos. Esse segundo passo é feito de
maneiras. Logo o total de pares
também é
Passo 4
Como ambos os lados contam exatamente o mesmo conjunto de pares
, concluímos que