Questão 95. Prove que n \cdot\binom{n}{0}+(n-1) \cdot\binom{n}{1}+(n-2) \cdot\binom{n}{2}+\ldots+1 \cdot\binom{n}{1}=n \cdot 2^{n-1}.

Passo 1

O que o enunciado pede: provar a igualdade
n\cdot\binom{n}{0}+(n-1)\cdot\binom{n}{1}+(n-2)\cdot\binom{n}{2}+\ldots+1\cdot\binom{n}{n-1}=n\cdot 2^{n-1}.
Informações dadas (explícitas no enunciado):
  • Há uma soma onde o termo genérico é (n-k)\cdot\binom{n}{k} para k=0,1,\dots,n-1. (Note que para k=n o termo seria (n-n)\binom{n}{n}=0, por isso a soma pode ser estendida até k=n sem alterar o valor.)
  • O objetivo é mostrar que essa soma vale n\cdot 2^{n-1}.

Passo 2

Interpretação combinatória das peças: explicar o que \binom{n}{k} e (n-k)\binom{n}{k} contam.
  • \binom{n}{k} é o número de maneiras de escolher um subconjunto de exatamente k elementos a partir de um conjunto de n elementos. Ou seja, quantos subconjuntos de tamanho k existem.
  • Para um subconjunto S de tamanho k, o número de elementos que NÃO estão em S é n-k. Logo, se para cada subconjunto S de tamanho k quisermos também escolher um elemento x que esteja fora de S, então, para cada S temos n-k opções para x. Portanto, o número de pares (S,x) com |S|=k e x\notin S é exatamente (n-k)\binom{n}{k}.
Para fixar a ideia, um exemplo concreto: se n=3 e k=1, \binom{3}{1}=3 (os três subconjuntos unitários) e n-k=2, então (n-k)\binom{n}{k}=2\cdot 3=6. De fato, para cada subconjunto unitário existem 2 elementos fora dele, totalizando 6 pares (S,x).

Passo 3

Interpretar a soma inteira: a soma sobre k de (n-k)\binom{n}{k} conta todos os pares (S,x) onde:
  • S é um subconjunto de \{1,2,\dots,n\} (de qualquer tamanho k),
  • x é um elemento que não pertence a S.
Escrevendo isso com a soma:
\sum_{k=0}^{n}(n-k)\binom{n}{k}
é exatamente o número total de pares (S,x) com S\subseteq\{1,\dots,n\} e x\notin S. (Lembre que o termo com k=n é 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 x que ficará fora do subconjunto S. Há n escolhas possíveis para x.
  • Depois que x está escolhido, os elementos restantes são os n-1 elementos de \{1,\dots,n\}\setminus\{x\}. Para formar S (um subconjunto que não contém x) podemos escolher livremente quaisquer elementos desses n-1: cada um pode estar ou não em S. Assim, o número de escolhas de S é 2^{n-1}.
  • Pelo princípio multiplicativo, o número total de pares (S,x) contados dessa forma é
n\cdot 2^{n-1}.

Passo 5

Conclusão por igualdade das duas contagens: como ambas as contagens enumeram exatamente o mesmo conjunto de pares (S,x), elas devem dar o mesmo número. Portanto
\sum_{k=0}^{n}(n-k)\binom{n}{k}=n\cdot 2^{n-1}.
Isso é exatamente a identidade pedida (a soma do enunciado pode ser escrita até k=n sem alterar o resultado, porque o termo k=n é zero).

Passo 6

(Aula rápida alternativa — prova algébrica usando o binômio, caso queira outro método.)
  • A soma clássica é \sum_{k=0}^{n} k\binom{n}{k}=n\cdot 2^{n-1}. Isso pode ser obtido derivando (1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k em relação a x, obtendo n(1+x)^{n-1}=\sum_{k=0}^n k\binom{n}{k}x^{k-1}, e então tomando x=1.
  • Observando que (n-k)\binom{n}{k}=n\binom{n-1}{k} (identidade combinatória simples), tem-se
\sum_{k=0}^n (n-k)\binom{n}{k}=n\sum_{k=0}^n \binom{n-1}{k}=n\cdot 2^{n-1},
porque \sum_{k=0}^{n-1}\binom{n-1}{k}=2^{n-1} (soma das binomiais de linha n-1). Isso confirma algebraicamente o mesmo resultado.

Resposta

n\cdot\binom{n}{0}+(n-1)\cdot\binom{n}{1}+(n-2)\cdot\binom{n}{2}+\ldots+1\cdot\binom{n}{n-1}=n\cdot 2^{n-1}.

Exercícios relacionados