Simplify
$$0^2 \binom{n}{0} + 1^2 \binom{n}{1} + 2^2 \binom{n}{2} + \cdots + n^2 \binom{n}{n}$$
where $n \ge 2$ and put the answer in the form of $f(n) 2^{g(n)},$ where $f(n)$ and $g(n)$ are polynomials in $n$ with integer coefficients.
My go at it: Let's say we have a group of $n$ people and they have to choose a committee which consists of at least $0$ members(a weird committee with $0$ people i would say). After having chosen the committee, we chosen a president and vice-president, but in this committee one person can take both roles. Therefore if the committee chose $k$ members, the number of ways to choose a vice and a president would be $k^2 \cdot \binom{n}{k}$ since they would first choose $k$ members and then you have $k$ possible presidents and likewise $k$ possible vices. This therefore forms the equation given in the problem.
Now we have to write an expression that also suffices this committee choosing. We can first choose people for presidency and vice presidency which gives us $n^2.$ For the remaining $n-2$ people, they can either be in the group or not be in the group so therefore the expression in the problem is equal to $\boxed{n^2 2^{n-2}}.$
However, this answer is wrong, but I can't see why it is wrong. Can anybody point out my flaw? Thanks!
Best Answer
As Mindjolt pointed out, your argument fails when the president and vice president are the same person. If you handle the case where the leaders are the same, you have $n \cdot 2^{n-1}$ ($n$ ways to choose the single leader, and the remaining $n-1$ people will either be in the group or not); if instead the leaders are different, you have $n(n-1) 2^{n-2}$. Adding them yields $(n^2 + n)2^{n-2}$.
Algebraic approach suggested by Zenix:
$$(1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k$$ Differentiate once: $$n(1+x)^{n-1} = \sum_{k=1}^n \binom{n}{k} k x^{k-1}$$ Multiply by $x$: $$nx(1+x)^{n-1} = \sum_{k=1}^n \binom{n}{k} k x^k$$ Differentiate again: $$n(1+x)^{n-1} + n(n-1) x(1+x)^{n-2} = \sum_{k=1}^n \binom{n}{k} k^2 x^{k-1}$$ Plug in $x=1$: $$n2^{n-1} + n(n-1) 2^{n-2} = \sum_{k=1}^n \binom{n}{k} k^2$$