O2 Seja
, onde
.
(a) Dado
, mostre que o número de subconjuntos de
nos quais
é o maior elemento é
.
(b) Aplique o item (a) para mostrar que
(a) Dado
(b) Aplique o item (a) para mostrar que
Passo 1
O enunciado define o conjunto
e pede duas coisas:
- (a) Para cada
, contar quantos subconjuntos têm como maior elemento. - (b) Usar esse resultado para demonstrar a soma
O conteúdo principal é contagem de subconjuntos e particionamento segundo o maior elemento.
Passo 2
Queremos contar todos os subconjuntos
tais que
. Para que
seja verdade, é necessário e suficiente que:
-
. - Todos os demais elementos de
estejam entre e .
Logo, cada escolha decom corresponde a escolher arbitrariamente um subconjunto de e depois unir esse subconjunto a . O número de subconjuntos de é . Portanto, para cada , há
subconjuntos de
cujo maior elemento é
. Isso prova o item (a).
Passo 3
Agora, todo subconjunto não-vazio de
possui um maior elemento bem definido, que pode variar de
até
. Assim, os subconjuntos não-vazios de
se repartem em classes mutuamente disjuntas, uma para cada
, e a classe de
tem exatamente
elementos. Logo, o número total de subconjuntos não-vazios de
é
Passo 4
Por outro lado, sabemos que o número de todos os subconjuntos de
(incluindo o vazio) é
. Somente um deles é o conjunto vazio, então o número de subconjuntos não-vazios é
Igualando essas duas contagens, obtemos
Fazendo a mudança de índice
, a soma no lado esquerdo torna-se
e assim chegamos à fórmula desejada.