\binom{n}{k} é o coeficiente binomial usual, isto é, o número de maneiras de escolher k elementos dentre n.
A soma vai de k=1 até k=n (note que o termo k=0 vale 0 porque multiplica k^{2}, então podemos incluir k=0 sem mudar o resultado se for conveniente).
Passo 2
Vamos lembrar uma ferramenta muito útil: a expansão binomial. Para a função
f(x)=(1+x)^{n}
vale a identidade (teorema binomial)
f(x)=\sum_{k=0}^{n} \binom{n}{k} x^{k}.
Isto significa que os coeficientes da série de f são exatamente os \binom{n}{k}. A ideia agora é transformar essa série para obter somas que envolvem k, k(k-1) e k^{2}. Para isso vamos usar derivadas da série: derivando termo a termo sabemos que derivar x^{k} produz um fator k, e derivar de novo produz fatores envolvendo k(k-1). Vou mostrar isso passo a passo.
Passo 3
Calcule a primeira derivada de f e relacione com a soma dos termos multiplicados por k. Derivando temos
f'(x)=\frac{d}{dx}(1+x)^{n}=n(1+x)^{n-1},
e, por derivação termo a termo da soma,
f'(x)=\sum_{k=0}^{n} k \binom{n}{k} x^{\,k-1}.
Multiplicando por x obtemos
x f'(x)=\sum_{k=0}^{n} k \binom{n}{k} x^{k}.
Esta série no lado direito é exatamente a soma dos termos \,k\binom{n}{k}x^{k}\,.
Lembre que incluir k=0 não alterou o resultado porque o termo k^{2}\binom{n}{k} é zero para k=0. Portanto a soma pedida originalmente (de k=1 a n) é a mesma.
Passo 8
(Comentário didático curto e encorajador) Outra maneira rápida de ver esse resultado é pensar probabilisticamente: se K tem distribuição \mathrm{Binomial}(n,\tfrac12), então \mathbb{E}[K^{2}]=\mathrm{Var}(K)+(\mathbb{E}[K])^{2}=\tfrac{n}{4}+\tfrac{n^{2}}{4}=\tfrac{n(n+1)}{4}. Multiplicando por 2^{n} (o total de subconjuntos) dá a mesma soma. Ótimo trabalho até aqui — já está no resultado final!