Use indução para demonstrar que para todo n \in \mathbb{N} :
\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^{n}
Mostre a aplicação da regra da adição na relação de Stifel.

Passo 1

O enunciado pede para provar, por indução em n, que para todo n\in\mathbb{N} vale
\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^{n}.
Informações/condições dadas que vamos usar:
  • Os termos \binom{n}{k} são os coeficientes binomiais (devem ser entendidos e manipulados).
  • Devemos usar indução matemática: verificar um caso base e mostrar que, se a propriedade vale para n, então vale para n+1.
  • O enunciado pede ainda para mostrar a aplicação da regra da adição na relação de Stifel (ou seja, usar a identidade de Stifel \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k} de forma explícita).

Passo 2

Primeiro, entenda o que é \binom{n}{k}. Definição e significado:
  • Definição algébrica: para inteiros n\ge 0 e 0\le k\le n,
\binom{n}{k}=\dfrac{n!}{k!(n-k)!},
onde m! (fatorial) é m!=m\cdot(m-1)\cdots 2\cdot1 e por convenção 0!=1.
  • Interpretação combinatória: \binom{n}{k} é o número de maneiras de escolher k elementos dentre n sem ordem (combinações).
    Exemplo rápido: \binom{4}{1}=4 e \binom{4}{2}=6.

Passo 3

Apresentar e provar a relação de Stifel (regra da adição):
  • A relação de Stifel é
\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},
válida para n\ge 1 e 1\le k\le n-1. Vou mostrar duas ideias (combinatória e algébrica) — escolha a que preferir na prova de indução.
Combinatória (intuição da regra da adição):
  • Considere escolher k elementos dentre n marcados. Pegue um elemento especial x.
  • Todas as escolhas de k elementos se dividem em duas classes disjuntas:
    1. As escolhas que incluem x. Para essas, além de x escolhe-se k-1 entre os n-1 restantes: total \binom{n-1}{k-1}.
    2. As escolhas que não incluem x. Para essas, escolhe-se k entre os n-1 restantes: total \binom{n-1}{k}.
  • Como as duas classes cobrem todas as escolhas e são disjuntas, o total é a soma, obtendo a identidade.
Algebricamente:
  • Partindo da definição em fatoriais,
\binom{n-1}{k-1}+\binom{n-1}{k} =\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-1-k)!}.
Colocando sob um denominador comum e simplificando obtém-se \dfrac{n!}{k!(n-k)!}=\binom{n}{k}. (Esse cálculo é direto se necessário.)
Essa identidade é a “regra da adição” aplicada aos coeficientes binomiais: um coeficiente na linha n é soma de dois coeficientes da linha n-1.

Passo 4

Início da prova por indução. Primeiro o caso base:
  • Caso base: n=0.
\binom{0}{0}=1
e 2^{0}=1. Logo a igualdade vale para n=0.

Passo 5

Hipótese de indução:
  • Suponha que para um n\ge 0 arbitrário a igualdade seja verdadeira, ou seja,
\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^{n}.
Essa é a hipótese de indução que usaremos para passar de n para n+1.

Passo 6

Passo indutivo: provar que a igualdade vale para n+1. Começamos escrevendo a soma que queremos avaliar:
\binom{n+1}{0}+\binom{n+1}{1}+\cdots+\binom{n+1}{n}+\binom{n+1}{n+1}.
Aplicamos a relação de Stifel (a “regra da adição”) aos termos interiores \binom{n+1}{k} para 1\le k\le n. Para esses k temos
\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}.
Substituindo na soma inteira obtemos
\begin{aligned} &\binom{n+1}{0}+\sum_{k=1}^{n}\binom{n+1}{k}+\binom{n+1}{n+1}\\[4pt] &= \binom{n+1}{0}+\sum_{k=1}^{n}\bigl(\binom{n}{k-1}+\binom{n}{k}\bigr)+\binom{n+1}{n+1}. \end{aligned}
Agora observe que \binom{n+1}{0}=1=\binom{n}{0} e \binom{n+1}{n+1}=1=\binom{n}{n}. Desenvolvendo a soma do meio e agrupando os termos:
\begin{aligned} &\binom{n+1}{0}+\sum_{k=1}^{n}\binom{n}{k-1}+\sum_{k=1}^{n}\binom{n}{k}+\binom{n+1}{n+1}\\[4pt] &= \underbrace{\binom{n}{0}}_{=\binom{n+1}{0}} + \bigl(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n-1}\bigr) + \bigl(\binom{n}{1}+\cdots+\binom{n}{n}\bigr) + \underbrace{\binom{n}{n}}_{=\binom{n+1}{n+1}}. \end{aligned}
Repare que a primeira soma \sum_{k=1}^{n}\binom{n}{k-1} é, com mudança de índice j=k-1, exatamente \sum_{j=0}^{n-1}\binom{n}{j}; e a segunda soma \sum_{k=1}^{n}\binom{n}{k} é \sum_{j=1}^{n}\binom{n}{j}. Assim, juntando tudo de maneira clara:
\begin{aligned} &\binom{n+1}{0}+\sum_{k=1}^{n}\bigl(\binom{n}{k-1}+\binom{n}{k}\bigr)+\binom{n+1}{n+1}\\[4pt] &= \bigl(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}\bigr) + \bigl(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}\bigr). \end{aligned}
Ou seja, a soma dos coeficientes na linha n+1 se transformou em duas cópias da soma dos coeficientes na linha n. Usando a hipótese de indução \sum_{j=0}^{n}\binom{n}{j}=2^{n}, obtemos
\sum_{k=0}^{n+1}\binom{n+1}{k}=2^{n}+2^{n}=2\cdot 2^{n}=2^{n+1}.
Assim a propriedade vale para n+1.]

Passo 7

Conclusão da indução:
  • Como a igualdade vale para n=0 (caso base) e mostramos que, sempre que vale para um n, vale para n+1, segue por princípio da indução matemática que a igualdade vale para todo n\in\mathbb{N}.
  • Comentário final sobre a “aplicação da regra da adição na relação de Stifel”: a identidade de Stifel foi aplicada explicitamente na transformação de cada \binom{n+1}{k} (com 1\le k\le n) em \binom{n}{k-1}+\binom{n}{k}, o que permitiu reescrever a soma na forma de duas somas iguais sobre a linha n.

Resposta

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

Exercícios relacionados