Exercício 35. Use indução para demonstrar que para todo n \in \mathbb{N} :
\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^{n}

Passo 1

O enunciado pede para demonstrar que, para todo n \in \mathbb{N},
\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^{n}.
Informações e definições relevantes que o enunciado nos dá (essas são as “peças” que vamos usar):
  • Para n e k inteiros com 0\le k\le n, o coeficiente binomial é definido por
\binom{n}{k}=\frac{n!}{k!(n-k)!},
onde n! denota o fatorial de n.
  • A soma à esquerda é a soma de todos os coeficientes binomiais de ordem n, ou seja, \displaystyle\sum_{k=0}^{n}\binom{n}{k}.
  • O objetivo é provar que essa soma é igual a 2^{n} para todo n natural.

Passo 2

Começamos pela base da indução. Verificar o caso n=0.
  • Calcular o lado esquerdo: quando n=0 só existe \binom{0}{0}. Pela definição de fatorial,
\binom{0}{0}=\frac{0!}{0!0!}=1.
  • Calcular o lado direito: 2^{0}=1.
    Portanto, para n=0 temos
\binom{0}{0}=1=2^{0},
ou seja, a propriedade é verdadeira para n=0. (Se preferir, pode verificar também n=1: \binom{1}{0}+\binom{1}{1}=1+1=2=2^{1}, só para ganhar confiança.)

Passo 3

Enunciamos a hipótese de indução. Suponha que, para um certo n\in\mathbb{N}, vale
\sum_{k=0}^{n}\binom{n}{k}=2^{n}.
O objetivo agora é provar que, sob essa hipótese, a propriedade vale para n+1; isto é, provar que
\sum_{k=0}^{n+1}\binom{n+1}{k}=2^{\,n+1}.

Passo 4

Vamos usar a identidade de Pascal, que é essencial aqui. A identidade de Pascal diz que, para 1\le k\le n,
\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}.
Explicação e prova rápida (álgebra): partindo da definição por fatoriais,
\binom{n+1}{k}=\frac{(n+1)!}{k!(n+1-k)!}.
Multiplicando e dividindo convenientemente, obtemos
\binom{n}{k-1}+\binom{n}{k} =\frac{n!}{(k-1)!(n+1-k)!}+\frac{n!}{k!(n-k)!}.
Colocando em denominador comum k!(n+1-k)! e simplificando chega-se exatamente a \dfrac{(n+1)!}{k!(n+1-k)!}, que é \binom{n+1}{k}. (Intuição combinatória: escolher k de n+1 itens é escolher se um item especial está ou não na seleção, levando às duas parcelas da soma.)

Passo 5

Agora somamos todos os coeficientes para n+1 e aplicamos a identidade de Pascal com cuidado nos índices. Começamos escrevendo explicitamente as extremidades:
\sum_{k=0}^{n+1}\binom{n+1}{k} =\binom{n+1}{0}+\sum_{k=1}^{n}\binom{n+1}{k}+\binom{n+1}{n+1}.
Sabemos que \binom{n+1}{0}=\binom{n+1}{n+1}=1. Para os termos interiores, aplicamos Pascal:
\sum_{k=1}^{n}\binom{n+1}{k} =\sum_{k=1}^{n}\bigl(\binom{n}{k-1}+\binom{n}{k}\bigr).
Separando a soma em duas somas:
\sum_{k=1}^{n}\binom{n}{k-1}+\sum_{k=1}^{n}\binom{n}{k}.
Fazemos uma mudança de índice na primeira soma: colocando j=k-1, quando k=1 temos j=0 e quando k=n temos j=n-1. Assim
\sum_{k=1}^{n}\binom{n}{k-1}=\sum_{j=0}^{n-1}\binom{n}{j}.
A segunda soma já é
\sum_{k=1}^{n}\binom{n}{k}=\sum_{j=1}^{n}\binom{n}{j}.
Somando as duas e incluindo as extremidades \binom{n+1}{0} e \binom{n+1}{n+1} que valem 1 cada, obtemos
\sum_{k=0}^{n+1}\binom{n+1}{k} =1+\Bigl(\sum_{j=0}^{n-1}\binom{n}{j}+\sum_{j=1}^{n}\binom{n}{j}\Bigr)+1.
Agora note que, ao juntar as somas internas, cada termo \binom{n}{j} para j=1,\dots,n-1 aparece duas vezes, enquanto \binom{n}{0} e \binom{n}{n} aparecem uma vez em cada soma de borda; no total isso equivale a somar duas vezes toda a soma \sum_{j=0}^{n}\binom{n}{j}. Em termos algébricos faz-se a combinação:
\sum_{j=0}^{n-1}\binom{n}{j}+\sum_{j=1}^{n}\binom{n}{j} =\sum_{j=0}^{n}\binom{n}{j}+\sum_{j=0}^{n}\binom{n}{j}-\binom{n}{0}-\binom{n}{n} =2\sum_{j=0}^{n}\binom{n}{j}-2.
Substituindo na expressão total:
\sum_{k=0}^{n+1}\binom{n+1}{k} =1+\bigl(2\sum_{j=0}^{n}\binom{n}{j}-2\bigr)+1 =2\sum_{j=0}^{n}\binom{n}{j}.
Portanto, usando a hipótese de indução \displaystyle\sum_{j=0}^{n}\binom{n}{j}=2^{n}, obtemos
\sum_{k=0}^{n+1}\binom{n+1}{k}=2\cdot 2^{n}=2^{\,n+1}.

Passo 6

Concluímos o passo indutivo: mostramos que se a fórmula vale para n então vale para n+1. Juntando com a base n=0, pela indução matemática a igualdade
\sum_{k=0}^{n}\binom{n}{k}=2^{n}
vale para todo n\in\mathbb{N}. (Breve comentário final: uma interpretação combinatória alternativa e rápida — que dá intuição — é que o lado esquerdo conta, por tamanhos, todas as subconjuntos de um conjunto com n elementos, e o lado direito 2^{n} é o número total de subconjuntos.)

Resposta

\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^{n}

Exercícios relacionados