Demonstre:
(b)
.
(b)
Passo 1
O que o enunciado dá e o que pede.
- Está dado um inteiro
. - Está dada a soma
- O pedido é demonstrar que essa soma é igual a
, isto é, provar que
Passo 2
Entendendo o que é
.
- A notação
(lida “ escolhe ”) representa o número de maneiras de escolher elementos distintos de um conjunto com elementos, sem ordem. - A fórmula fechada é
onde
(fatorial) é
.
- Exemplo rápido:
.
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
e inteiro ,
- Intuição combinatória dessa fórmula: ao multiplicar
por si mesmo vezes, em cada fator escolhe-se ou . Se em exatamente dos fatores escolher , isso pode ser feito de maneiras, e o produto resultante é . Somando sobre todos os possíveis obtém-se a expansão acima. - (Se quiser, dá para provar rigorosamente por indução usando a identidade de Pascal
, mas a intuição já basta aqui.)
Passo 4
Aplicando o teorema binomial ao caso concreto.
- Tome
e na fórmula do passo anterior. Então
- Como
para todo , isso simplifica para
- Mas essa soma à direita é exatamente a soma do enunciado; portanto obtemos a igualdade desejada:
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
cujos termos são escolhidos do conjunto . Há 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
(chame esse número de ). Escolha quais são as posições: maneiras. Nessas posições, cada posição tem 2 escolhas ( ou ), dando escolhas. Nas outras posições só resta a letra (1 escolha cada). Logo, o número de sequências com exatamente posições em é . Somando sobre obtém-se
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
. A soma do enunciado é
- Calculando:
. E . Funciona!