Questão 95. Prove que
.
Passo 1
O que o enunciado pede: provar a igualdade
Informações dadas (explícitas no enunciado):
- Há uma soma onde o termo genérico é
para . (Note que para o termo seria , por isso a soma pode ser estendida até sem alterar o valor.) - O objetivo é mostrar que essa soma vale
.
Passo 2
Interpretação combinatória das peças: explicar o que
e
contam.
-
é o número de maneiras de escolher um subconjunto de exatamente elementos a partir de um conjunto de elementos. Ou seja, quantos subconjuntos de tamanho existem. - Para um subconjunto
de tamanho , o número de elementos que NÃO estão em é . Logo, se para cada subconjunto de tamanho quisermos também escolher um elemento que esteja fora de , então, para cada temos opções para . Portanto, o número de pares com e é exatamente .
Para fixar a ideia, um exemplo concreto: se
e
,
(os três subconjuntos unitários) e
, então
. De fato, para cada subconjunto unitário existem 2 elementos fora dele, totalizando 6 pares
.
Passo 3
Interpretar a soma inteira: a soma sobre
de
conta todos os pares
onde:
-
é um subconjunto de (de qualquer tamanho ), -
é um elemento que não pertence a .
Escrevendo isso com a soma:
é exatamente o número total de pares
com
e
. (Lembre que o termo com
é zero, então a soma é equivalente àquela do enunciado.)
Passo 4
Contagem alternativa do mesmo conjunto de pares, escolhendo na ordem diferente (contagem dupla).
- Primeiro escolha o elemento
que ficará fora do subconjunto . Há escolhas possíveis para . - Depois que
está escolhido, os elementos restantes são os elementos de . Para formar (um subconjunto que não contém ) podemos escolher livremente quaisquer elementos desses : cada um pode estar ou não em . Assim, o número de escolhas de é . - Pelo princípio multiplicativo, o número total de pares
contados dessa forma é
Passo 5
Conclusão por igualdade das duas contagens: como ambas as contagens enumeram exatamente o mesmo conjunto de pares
, elas devem dar o mesmo número. Portanto
Isso é exatamente a identidade pedida (a soma do enunciado pode ser escrita até
sem alterar o resultado, porque o termo
é zero).
Passo 6
(Aula rápida alternativa — prova algébrica usando o binômio, caso queira outro método.)
- A soma clássica é
. Isso pode ser obtido derivando em relação a , obtendo , e então tomando . - Observando que
(identidade combinatória simples), tem-se
porque
(soma das binomiais de linha
). Isso confirma algebraicamente o mesmo resultado.