O2 Seja A=\{1,2, \ldots, n\}, onde n \in \mathbb{N}.
(a) Dado k \in A, mostre que o número de subconjuntos de A nos quais k é o maior elemento é 2^{\mathrm{k}-1}.
(b) Aplique o item (a) para mostrar que
\sum_{i=0}^{n-1} 2^{i}=2^{n}-1

Passo 1

O enunciado define o conjunto A=\{1,2,\dots,n\} e pede duas coisas:
  1. (a) Para cada k\in A, contar quantos subconjuntos S\subseteq A têm k como maior elemento.
  2. (b) Usar esse resultado para demonstrar a soma
\sum_{i=0}^{n-1}2^{i}=2^{n}-1.
O conteúdo principal é contagem de subconjuntos e particionamento segundo o maior elemento.

Passo 2

Queremos contar todos os subconjuntos S\subseteq A tais que \max(S)=k. Para que \max(S)=k seja verdade, é necessário e suficiente que:
  1. k\in S.
  2. Todos os demais elementos de S estejam entre 1 e k-1.
    Logo, cada escolha de S com \max(S)=k corresponde a escolher arbitrariamente um subconjunto de \{1,2,\dots,k-1\} e depois unir esse subconjunto a \{k\}. O número de subconjuntos de \{1,2,\dots,k-1\} é 2^{k-1}. Portanto, para cada k, há
2^{k-1}
subconjuntos de A cujo maior elemento é k. Isso prova o item (a).

Passo 3

Agora, todo subconjunto não-vazio de A possui um maior elemento bem definido, que pode variar de 1 até n. Assim, os subconjuntos não-vazios de A se repartem em classes mutuamente disjuntas, uma para cada k, e a classe de k tem exatamente 2^{k-1} elementos. Logo, o número total de subconjuntos não-vazios de A é
\sum_{k=1}^{n}2^{k-1}.

Passo 4

Por outro lado, sabemos que o número de todos os subconjuntos de A (incluindo o vazio) é 2^{n}. Somente um deles é o conjunto vazio, então o número de subconjuntos não-vazios é
2^{n}-1.
Igualando essas duas contagens, obtemos
\sum_{k=1}^{n}2^{k-1}=2^{n}-1.
Fazendo a mudança de índice i=k-1, a soma no lado esquerdo torna-se
\sum_{i=0}^{n-1}2^{i},
e assim chegamos à fórmula desejada.

Resposta

\sum_{i=0}^{n-1}2^{i}=2^{n}-1.

Exercícios relacionados