Show that $\sum_{k=1}^n \binom{n}{k}k^2=n^2\cdot \:2^{n-2}+n\cdot \:2^{n-2}$.

Let $n$ be a positive integer. Show that $\sum_{k=1}^n \binom{n}{k}k^2=n^2\cdot \:2^{n-2}+n\cdot \:2^{n-2}$.

I have that $$(1+x)^n = \sum_{k=0}^n {n \choose k} x^k$$ and I'm wondering if I can use this to prove the result. However this sum starts with the index $k=0$ and not with $k=1$. Also I have the $x^k$ term instead of $k^2$. Is there a way I can modify this result?

Solution 1:

Combinatorial Argument

Note that the LHS represents the number of ways to select a committee of $k$ people, and then select a president and vice president, which can be the same person.

We can also count the number of ways to do this by first selecting the president and vice president.

If these two are the same person, then there are $n$ ways to choose it and $2^{n-1}$ ways to choose the rest of the committee

If these two are distinct, then there are $n(n-1)$ ways to choose them and $2^{n-2}$ ways to choose the rest of the committee.

Hence, the total number of ways is $$n\cdot2^{n-1}+(n^2-n)\cdot 2^{n-2}$$ $$2n\cdot2^{n-2}+(n^2-n)\cdot 2^{n-2}$$ $$(n^2+n)\cdot 2^{n-2}$$ $$n^2\cdot 2^{n-2}+n\cdot 2^{n-2}$$

Algebraic method

As hellofriends hinted in the comments, you can use $$f(x)=(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k$$ and take the derivative to get $$f'(x)=n(1+x)^{n-1}=\sum_{k=0}^n \binom{n}{k}k x^{k-1}$$ Now multiply by $x$ and take the derivative again, $$\left[xf'(x)\right]'=n(1+x)^{n-1}+n(n-1)x(1+x)^{n-2}=\sum_{k=0}^n \binom{n}{k}k^2 x^{k-1}$$ Now substitute $x=1$ to get $$n(2)^{n-1}+n(n-1)(2)^{n-2}=\sum_{k=0}^n \binom{n}{k}k^2$$ $$n(n+1)(2)^{n-2}=\sum_{k=0}^n \binom{n}{k}k^2$$