Prove que, para todo número natural
, temos
Passo 1
O enunciado nos pede para provar que, para todo
, vale
O conteúdo aqui é combinatória básica: a definição de
como “número de maneiras de escolher
elementos de um total de
” e o princípio do produto para contagem de opções independentes. Vamos usar um argumento em que contamos dois jeitos o número de subconjuntos de um conjunto com
elementos.
Passo 2
Considere um conjunto
qualquer com
. Todo subconjunto de
tem algum tamanho
, com
. Sabemos da definição de coeficiente binomial que o número de subconjuntos de tamanho exatamente
é
Se somarmos sobre todas as possibilidades de
, obtemos o número total de subconjuntos de
:
Passo 3
Por outro lado, podemos contar diretamente todos os subconjuntos de
observando que, para cada elemento de
, há duas escolhas independentes: ou o elemento entra no subconjunto, ou não entra. Como há
elementos e cada um “dá” 2 opções, pelo princípio do produto temos
Passo 4
Igualando as duas contagens do número total de subconjuntos de
, concluímos
que é exatamente o que queríamos demonstrar.