Prove binomial equation

Question

I have problem with proving following equation:

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

Thanks for any help!

Answer 1

HINT: Use the identity $\binom{n}kk=\binom{n-1}{k-1}n$ a couple of times. I’ll get you started:

$$\begin{align*} \sum_k\binom{n}kk^2&=n\sum_k\binom{n-1}{k-1}k\\ &=n\sum_k\binom{n-1}k(k+1)\\ &=n\sum_k\binom{n-1}kk+n\sum_k\binom{n-1}k \end{align*}$$

Now repeat the process to simplify the first summation, and evaluate the last one as it is.

I’ve added a combinatorial argument in the spoiler-protected block below.

We have a pool of $n$ people. From this pool we’re going to choose a committee, and from the committee we’re going to choose a treasurer and a secretary. The committee can be of any size, and the treasurer and secretary can be the same person. If the committee has $k$ members, there are $\binom{n}k$ ways to choose it, and there are then $k^2$ ways to choose a treasurer and a secretary, so there are $\binom{n}kk^2$ ways to complete the selection. Summing over all possible values of $k$, we get $\sum_k\binom{n}kk^2$ ways to form the committee and choose the two officers. Alternatively, we can first choose the treasurer; that choice can be made in $n$ ways. We then choose a secretary. There are $n-1$ ways to choose a secretary who is not the treasurer, and if we make one of those choices, there are $n-2$ people left from whom to choose the rest of the committee, if any; there are $2^{n-2}$ ways to make that choice, so this accounts altogether for $n(n-1)2^{n-2}$ committees with officers. There is one way to choose the secretary to be identical to the treasurer, and in that case there are $2^{n-1}$ ways to fill out the rest of the committee; this gives us another $n2^{n-1}$ committees with officers. Putting the two together, we have a total of $n(n-1)2^{n-2}+n2^{n-1}$ committees with officers, which simplifies easily to $n(n+1)2^{n-2}$.

Answer 2

Let $f(x)=(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k$. Derive and multiply by $x$ to get $xf'(x)=\sum_{k=1}^n \binom{n}{k}kx^k$. Derive again and get $(xf'(x))'=\sum_{k=1}^n \binom{n}{k}k^2x^{k-1}\mid_{x=1}=\sum_{k=1}^n \binom{n}{k}k^2$. $$(xf'(x))'=f'(x)+xf''(x)=n(1+x)^{n-1}+xn(n-1)(1+x)^{n-2}\mid_{x=1}=n2^{n-1}+n(n-1)2^{n-2}=n\cdot 2\cdot 2^{n-2}+n(n-1)2^{n-2}=n(n+1)2^{n-2}$$