Prove que, para todo número natural n, temos
\sum_{r=0}^{n}\binom{n}{r}=2^{n}

Passo 1

O enunciado nos pede para provar que, para todo n\in\mathbb{N}, vale
\sum_{r=0}^{n}\binom{n}{r}=2^{n}.
O conteúdo aqui é combinatória básica: a definição de \binom{n}{r} como “número de maneiras de escolher r elementos de um total de n” 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 n elementos.

Passo 2

Considere um conjunto A qualquer com \lvert A\rvert = n. Todo subconjunto de A tem algum tamanho r, com 0\le r\le n. Sabemos da definição de coeficiente binomial que o número de subconjuntos de tamanho exatamente r é
\binom{n}{r}.
Se somarmos sobre todas as possibilidades de r, obtemos o número total de subconjuntos de A:
\text{(total de subconjuntos)} \;=\;\sum_{r=0}^{n}\binom{n}{r}.

Passo 3

Por outro lado, podemos contar diretamente todos os subconjuntos de A observando que, para cada elemento de A, há duas escolhas independentes: ou o elemento entra no subconjunto, ou não entra. Como há n elementos e cada um “dá” 2 opções, pelo princípio do produto temos
\text{(total de subconjuntos)} \;=\;2 \times 2 \times \cdots \times 2 \;(n\text{ vezes}) \;=\;2^{n}.

Passo 4

Igualando as duas contagens do número total de subconjuntos de A, concluímos
\sum_{r=0}^{n}\binom{n}{r} \;=\; 2^{n},
que é exatamente o que queríamos demonstrar.

Resposta

\sum_{r=0}^{n}\binom{n}{r}=2^{n}.

Exercícios relacionados