Prove que
.
Passo 1
Beleza, o enunciado pede pra provar que
Isso cai em combinatória básica e, mais precisamente, na definição de coeficiente binomial e no “conto de subconjuntos”. A gente vai precisar entender o que é
e como contar de duas maneiras o número total de subconjuntos de um conjunto de tamanho
.
Passo 2
Primeiro, lembra o que é o coeficiente binomial
:
e esse carinha conta de quantas formas diferentes você escolhe
elementos num conjunto de
. Então,
é só a soma de todas essas escolhas, pra
.
Passo 3
Agora a ideia-chave: imagine um conjunto
com
elementos (pode ser
, por exemplo).
- O número de subconjuntos de tamanho exatamente
é . - Se você quer contar todos os subconjuntos (dos que têm 0 elementos até os que têm
elementos), basta somar para até . Isso dá exatamente o lado esquerdo .
Por outro lado, dá pra contar direto: para cada um dos
elementos, você decide “está” ou “não está” no subconjunto. São 2 escolhas independentes por elemento, logo
(com
fatores) igual a
. Então o total de subconjuntos é
.