Demonstre:
(b) \binom{n}{0}+2\binom{n}{1}+2^{2}\binom{n}{2}+\ldots+2^{n}\binom{n}{n}=3^{n}, n \geq 1.

Passo 1

O que o enunciado dá e o que pede.
  • Está dado um inteiro n\ge 1.
  • Está dada a soma
\binom{n}{0}+2\binom{n}{1}+2^{2}\binom{n}{2}+\ldots+2^{n}\binom{n}{n}=\sum_{k=0}^{n}2^{k}\binom{n}{k}.
  • O pedido é demonstrar que essa soma é igual a 3^{n}, isto é, provar que
\sum_{k=0}^{n}2^{k}\binom{n}{k}=3^{n}\quad\text{para todo }n\ge 1.

Passo 2

Entendendo o que é \binom{n}{k}.
  • A notação \binom{n}{k} (lida “ n escolhe k”) representa o número de maneiras de escolher k elementos distintos de um conjunto com n elementos, sem ordem.
  • A fórmula fechada é
\binom{n}{k}=\frac{n!}{k!(n-k)!},
onde n! (fatorial) é n\cdot(n-1)\cdots1.
  • Exemplo rápido: \binom{4}{2}=\dfrac{4!}{2!2!}=\dfrac{24}{2\cdot2}=6.

Passo 3

Enunciando a ferramenta principal: o teorema binomial (expansão de uma potência de soma).
  • A fórmula geral diz que, para quaisquer números x,y e inteiro n\ge0,
(x+y)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{\,n-k}y^{\,k}.
  • Intuição combinatória dessa fórmula: ao multiplicar (x+y) por si mesmo n vezes, em cada fator escolhe-se x ou y. Se em exatamente k dos n fatores escolher y, isso pode ser feito de \binom{n}{k} maneiras, e o produto resultante é x^{\,n-k}y^{\,k}. Somando sobre todos os possíveis k obtém-se a expansão acima.
  • (Se quiser, dá para provar rigorosamente por indução usando a identidade de Pascal \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}, mas a intuição já basta aqui.)

Passo 4

Aplicando o teorema binomial ao caso concreto.
  • Tome x=1 e y=2 na fórmula do passo anterior. Então
(1+2)^{n}=\sum_{k=0}^{n}\binom{n}{k}1^{\,n-k}2^{\,k}.
  • Como 1^{\,n-k}=1 para todo k, isso simplifica para
3^{n}=\sum_{k=0}^{n}\binom{n}{k}2^{\,k}.
  • Mas essa soma à direita é exatamente a soma do enunciado; portanto obtemos a igualdade desejada:
\sum_{k=0}^{n}2^{k}\binom{n}{k}=3^{n}.

Passo 5

Versão combinatória alternativa (para fixar a ideia, é legal e costuma cair em prova).
  • Conte o número de sequências de comprimento n cujos termos são escolhidos do conjunto \{A,B,C\}. Há 3^{n} tais sequências (cada posição tem 3 escolhas, independentemente).
  • Conte de outro modo: para cada sequência, conte quantas posições contêm um símbolo em \{A,B\} (chame esse número de k). Escolha quais são as k posições: \binom{n}{k} maneiras. Nessas k posições, cada posição tem 2 escolhas ( A ou B), dando 2^{k} escolhas. Nas outras n-k posições só resta a letra C (1 escolha cada). Logo, o número de sequências com exatamente k posições em \{A,B\} é \binom{n}{k}2^{k}. Somando sobre k=0,\dots,n obtém-se
\sum_{k=0}^{n}\binom{n}{k}2^{k}=3^{n},
a mesma identidade, agora com interpretação combinatória clara.

Passo 6

Exemplo numérico para checar (calma, é só um teste para ganhar confiança).
  • Tome n=3. A soma do enunciado é
\binom{3}{0}2^{0}+\binom{3}{1}2^{1}+\binom{3}{2}2^{2}+\binom{3}{3}2^{3} =1+3\cdot2+3\cdot4+1\cdot8.
  • Calculando: 1+6+12+8=27. E 3^{3}=27. Funciona!

Resposta

3^{n}

Exercícios relacionados