How to prove that $\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n)$ [duplicate]

Solution 1:

This is equivalent to proving $$\sum_{k=0}^n k^2 {n\choose k}=n(n+1)2^{n-2}.$$ Given $n$ people we can form a committee of $k$ people in ${n\choose k}$ ways. Once the committee is formed we can pick a committee leader and a committee planner. If we allow each person to hold both job titles there are $k$ ways for this to happen. If no person is allowed to have both job titles, then there are $k$ choices for the committee leader and $k-1$ choices for the committee planner for a total of $k(k-1)$ choices for a different committee leader and committee planner. The total number of choices for a committee leader and a committee planner is $k+k(k-1)=k^2$ . We now sum for all possible $k$ values from $0$ to $n$ to form every committee of $k$ people with a committee leader and a committee planner, that is, $\sum_{k=0}^n k^2 {n\choose k}$. We can count the same thing by first picking committee leaders and committee planners and then filling in the committee with the remaining people. If we allow each person to hold both job titles, then there are $n$ ways for this to be done. The remaining $n-1$ people can form the committee in $2^{n-1}$ ways since each person has two choices, either they are in the committee or they are not in the committee. The total number of committees where each person can hold both titles is $n2^{n-1}$. If no person is allowed to hold both job titles, then there are $n$ choices for a committee leader and $n-1$ choices for a committee planner. The remaining $n-2$ people can form the committee in $2^{n-2}$ ways since each person has two choices, either they are in the committee or they are not in the committee. The total number of ways to form a committee where no person can have both job titles is $n(n-1)2^{n-2}$. Thus the total number of ways to form the committee is $n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}$. Hence $\sum_{k=0}^n k^2 {n\choose k}=n(n+1)2^{n-2}$.

Another way to do this is to consider $$(1+x)^n=\sum_{k=0}^n {n\choose k}x^k.$$ Differentiating both sides with respect to $x$ we obtain $$n(1+x)^{n-1}=\sum_{k=1}^n k{n\choose k}x^{k-1}.$$ Multiplying both sides of the equation by $x$ and differentiating with respect to $x$ we obtain $$n(1+x)^{n-1}+nx(n-1)(1+x)^{n-2}=\sum_{k=1}^nk^2{n\choose k}x^{k-1}.$$ Letting $x=1$ and simplifying the left-hand side we see that $$n(n+1)2^{n-2}=\sum_{k=1}^n k^2{n\choose k}.$$

Solution 2:

Dilip's comment points to the standard way. Here goes an alternative way:

If you are familiar with basic probability, you should recognize a canonical Binomial distribution in $$ \frac{1}{2^n} {n \choose k}$$

which count the number the successes in $n$ trials of an experiment with prob. $=1/2$ . This Binomial can also be regarded as the sum of $n$ iid Bernoulli variables with $p=1/2$. Hence, the mean is $n p = n/2$ and the variance $n p (1-p)= n/4$

Hence the second moment is

$$ E[X^2]=\frac{1}{2^n} \sum_{k=0}^n {n \choose k} k^2 = (E[X])^2+\sigma^2_X = n^2 \frac{1}{4} + n \frac{1}{4} = 2^{-2}(n^2+n)$$

Solution 3:

One common way to deal with this is using generating function.

In this problem, the key is to generate the $k^2$ factor in the sum. Notice if you have a polynomial $P(z) = \sum_{k=0}^n a_k z^k$ in $z$, everytime you apply the operator $z\frac{d}{dz}$ to it, the $z^k$ term will pick up an extra factor $k$. More precisely, you will have

$$\left(z\frac{d}{dz}\right)^m P(z) = \sum_{k=0}^n a_k k^m z^k$$

With these in mind, one find $$\begin{align} \sum_{k=0}^n \binom{n}{k} k^2 z^k = & \sum_{k=0}^n \binom{n}{k} \left(z\frac{d}{dz}\right)^2 z^k = \left(z\frac{d}{dz}\right)^2 \sum_{k=0}^n \binom{n}{k} z^k\\ = & \left(z\frac{d}{dz}\right)^2 (1+z)^n = z\frac{d}{dz} nz(1+z)^{n-1}\\ = & z \left( n(1+z)^{n-1} + n(n-1)z(1+z)^{n-2}\right) \end{align}$$ Taking $z = 1$ on both sides, one get $$\sum_{k=0}^n \binom{n}{k} k^2 = n 2^{n-1} + n(n-1) 2^{n-2} = (n^2 + n) 2^{n-2}$$