(Lema de Kaplansky) Seja
, onde
. Mostre que
número de subconjuntos de
com
elementos e que não contêm elementos consecutivos é dado por
onde
.
Passo 1
O enunciado pede para contar quantos subconjuntos de tamanho
de
não têm elementos consecutivos. O conteúdo usado será um argumento bijetivo, transformando cada subconjunto sem consecutivos num subconjunto qualquer de tamanho
em um universo reduzido, de modo que a contagem seja uma binomial.
Passo 2
Seja
um subconjunto de
sem nenhum par de elementos consecutivos. Então para todo
temos
. Definimos novos números
para
. Como o “sobra” de
afasta cada
do anterior, garantimos
Passo 3
O mapeamento
é bijetivo entre:
- Os subconjuntos de
com elementos sem consecutivos, e - Todos os subconjuntos de tamanho
de .
Logo, contar os subconjuntos originais equivale a contar todos os-subconjuntos de .
Passo 4
Sabemos que o número de subconjuntos de tamanho
de um conjunto com
elementos é
Isso vale exatamente quando
. Portanto, a resposta é essa binomial.