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

Passo 1

O enunciado pede para demonstrar a identidade
\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+\ldots+n\binom{n}{n}=n 2^{n-1},\qquad n\ge 1.
Informações dadas:
  • A soma envolve termos da forma k\binom{n}{k} para k=1,2,\dots,n.
  • O objetivo é provar que essa soma é igual a n 2^{n-1} para todo inteiro n\ge 1.

Passo 2

Primeira prova (interpretação combinatória, método direto e elementar).
Vou explicar claramente o que cada símbolo conta:
  • \binom{n}{k} é o número de maneiras de escolher um subconjunto com k elementos a partir de um conjunto fixo com n elementos.
  • Então k\binom{n}{k} pode ser interpretado como: primeiro escolher um subconjunto de tamanho k ( \binom{n}{k} escolhas ) e, em seguida, escolher um elemento “especial” dentro desse subconjunto ( k escolhas ). Logo k\binom{n}{k} conta o número de pares do tipo (S,e) onde S é um subconjunto de tamanho k e e\in S é o elemento distinguido.
Agora conto o mesmo tipo de objeto de uma maneira diferente:
  • Em vez de primeiro escolher o tamanho k, escolho primeiro o elemento distinguido e. Há n escolhas possíveis para e.
  • Depois de fixar e, para formar um par (S,e) preciso escolher quais dos outros n-1 elementos entram ou não em S. Cada um dos n-1 elementos restantes tem 2 opções (entrar ou não), portanto existem 2^{\,n-1} subconjuntos S que contêm e.
  • Assim, para cada escolha de e 2^{\,n-1} pares (S,e). Como existem n escolhas para e, o total de pares é n\cdot 2^{\,n-1}.
Conclusão deste raciocínio: o número de pares (S,e) contado somando k\binom{n}{k} sobre k (porque para cada k contamos os pares com |S|=k) é igual ao número contado escolhendo primeiro e. Portanto
\sum_{k=1}^n k\binom{n}{k}=n\cdot 2^{\,n-1}.
(Isto prova a identidade de maneira combinatória e intuitiva.)

Passo 3

Segunda prova (álgebraica, usando o teorema binomial e derivação — útil para a prova caso queiram manipulação algébrica).
Primeiro lembrar o teorema binomial: para todo inteiro n\ge0,
(1+x)^n=\sum_{k=0}^n \binom{n}{k} x^k.
Aqui x é uma variável e \binom{n}{k} são os coeficientes binomiais.
Agora derivar ambos os lados em relação a x. A derivada do lado esquerdo, pela regra da cadeia, é
\frac{d}{dx}(1+x)^n = n(1+x)^{n-1}.
A derivada do lado direito, aplicado termo a termo, é
\frac{d}{dx}\sum_{k=0}^n \binom{n}{k} x^k = \sum_{k=0}^n \binom{n}{k}\cdot k x^{k-1}.
Portanto obtemos a identidade (válida para todo x)
n(1+x)^{n-1}=\sum_{k=0}^n k\binom{n}{k} x^{k-1}.
Multiplicando ambos os lados por x
n x(1+x)^{n-1}=\sum_{k=0}^n k\binom{n}{k} x^{k}.
Agora basta escolher x=1. No lado direito o termo com k=0 é 0, então
n\cdot 1\cdot (1+1)^{n-1}=\sum_{k=0}^n k\binom{n}{k}\cdot 1^{k}=\sum_{k=1}^n k\binom{n}{k}.
Como (1+1)^{n-1}=2^{\,n-1}, obtemos novamente
\sum_{k=1}^n k\binom{n}{k}=n\cdot 2^{\,n-1}.

Passo 4

Verificação com um exemplo pequeno para intuição (chega pra crer!).
  • Tomando n=3: a soma é 1\binom{3}{1}+2\binom{3}{2}+3\binom{3}{3}=1\cdot 3+2\cdot 3+3\cdot 1=3+6+3=12.
  • O lado direito é n2^{n-1}=3\cdot 2^{2}=3\cdot 4=12.
    Confere.

Resposta

\sum_{k=1}^n k\binom{n}{k}=n\,2^{\,n-1}

Exercícios relacionados