Question

(50 PONTOS) Obter uma fórmula fechada para o somatório:
$~$
$\displaystyle\sum\limits_{k=0}^{n}{k^{2}\,\dbinom{n}{k}}$

Agradeço de coração a quem puder responder. :-)
$~$

Answer 1

Consegui derivando uma função. Tentei a partir das propriedades do triângulo de Pascal mas não rolou...

Queremos calcular:

∑ k².Cn,k    (∑ de k=0 até n)

Sabemos que 

(a + b)^n = ∑ Cn,k . a^(n-k) . b^k 

Considerando-se a seguinte f(x), a ideia é fazer aparecer k²:

f(x) = (1 + x)^n = ∑ Cn,k . 1^(n-k) . x^k

f(x) = (1 + x)^n = ∑ Cn,k . x^k

f '(x) = n.(1 + x)^(n-1) = ∑ Cn,k . k.x^(k-1)

x.f '(x) = n.x.(1 + x)^(n-1) = ∑ Cn,k . k.x^k

[x.f '(x)] ' = n.(1 + x)^(n-1) + (n - 1).n.x.(1 + x)^(n-2) = ∑ Cn,k . k².x^(k-1)

Logo:

∑ Cn,k . k².x^(k-1)  =  n.(1 + x)^(n-1) +  (n - 1).n.x.(1 + x)^(n-2) 


Para x = 1, temos:

∑ Cn,k . k².1^(k-1)  =  n.(1 + 1)^(n-1) + (n - 1).n.1.(1 + 1)^(n-2) 

∑ Cn,k . k² =  n.2^(n-1) + (n - 1).n.2^(n-2) 

∑ Cn,k . k² =  2.n.2^(n-2) + (n - 1).n.2^(n-2) 

∑ Cn,k . k² =  [n.2^(n-2)].(2 + n - 1)

∑ Cn,k . k² =  [n.2^(n-2)].(n + 1)
 
∑ Cn,k . k² = n.(n + 1).2^(n - 2).

Answer 2

$\displaystyle\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=0}^{n}k^{2}\dfrac{n!}{k!(n-k)!}=\sum\limits_{k=0}^{n}k^{2}\dfrac{n!}{k\cdot(k-1)!(n-k)!}$

Quando k = 0, o termo do somatório é 0, logo

$\displaystyle\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=1}^{n}k^{2}\binom{n}{k}$

Então:

$\displaystyle\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=1}^{n}k^{2}\dfrac{n!}{k(k-1)!(n-k)!}$

No somatório da direita, k ≠ 0, então

$\displaystyle\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=1}^{n}k\dfrac{n!}{(k-1)!(n-k)!}\\\\\\\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=1}^{n}k(n-k+1)\dfrac{n!}{(k-1)!(n-k+1)(n-k)!}\\\\\\\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=1}^{n}k(n-k+1)\dfrac{n!}{(k-1)!(n-k+1)!}\\\\\\\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=1}^{n}k(n-k+1)\dfrac{n!}{(k-1)!(n-[k-1])!}\\\\\\\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=1}^{n}k(n-[k-1])\binom{n}{k-1}$

Fazendo $u=k-1$, temos $k=u+1$. Além disso:

$k=1~\longrightarrow~u=0\\k=n~\longrightarrow~u=n-1$

Então:

$\displaystyle\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{u=0}^{n-1}(u+1)(n-u)\binom{n}{u}\\\\\\\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{u=0}^{n-1}(u+1)(n-u)\binom{n}{u}+(n+1)(n-n)\binom{n}{n}$

(pois esse fator somado é zero, já que n - n = 0)

$\displaystyle\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{u=0}^{n}(u+1)(n-u)\binom{n}{u}$

Como u atua apenas como contador, podemos trocá-lo por k:

$\displaystyle\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=0}^{n}(k+1)(n-k)\binom{n}{k}\\\\\\\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=0}^{n}(nk-k^{2}+n-k)\binom{n}{k}\\\\\\\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=0}^{n}([n-1]k-k^{2}+n)\binom{n}{k}\\\\\\\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=\sum\limits_{k=0}^{n}\left[(n-1)k\binom{n}{k}-k^{2}\binom{n}{k}+n\binom{n}{k}\right]$

$\displaystyle\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=(n-1)\sum\limits_{k=0}^{n}k\binom{n}{k}-\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}+n\sum\limits_{k=0}^{n}\binom{n}{k}\\\\\\2\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=(n-1)\sum\limits_{k=0}^{n}k\binom{n}{k}+n\sum\limits_{k=0}^{n}\binom{n}{k}1^{k}1^{n-k}$

Como vimos na tarefa 4972673, $\sum\limits_{k=0}^{n}k\binom{n}{k}=n\cdot2^{n-1}$

Além disso, $\sum\limits_{k=0}^{n}\binom{n}{k}1^{k}1^{n-k}=2^{k}$

Então, finalmente:

$\displaystyle2\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=(n-1)n\cdot2^{n-1}+n\cdot2^{n}\\\\\\\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=n(n-1)2^{n-2}+n\cdot2^{n-1}\\\\\\\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=n\cdot2^{n-2}\cdot[n-1+2]\\\\\\\boxed{\boxed{\sum\limits_{k=0}^{n}k^{2}\binom{n}{k}=n(n+1)2^{n-2}}}$