Finding general formula of $\sum_{i=0}^n i^2 \binom{n}{i}$

Question

Lets define formula: $$f(n)=\sum_{i=0}^n i^2 \binom{n}{i}$$

What would be genral formula of that?

I first went to discover $$f(n)=\sum_{i=0}^n \binom{n}{i}=2^n$$ (cardinality of power set), and $$f(n)=\sum_{i=0}^n i^2=\frac{2n^3+3n^2+n}{6}$$ then multiplied those together, realising that I am way off.

Then I tried to deduce general presentation of $f(n)$, finding difference of $f(1),f(2),f(3)\cdots$, differences of differences, etc etc, trying to figure what degree of polynomial can represent it, however even after $100$ iterations difference of difference of difference do not converge to some constant, so figuring out polynomial is not working (seems to be that its not polynomial then but some form of $c^n$ function, where $c$ is constant and $n$ is argument of function).

Any idea?

Answer 1

HINT:

$$r^2\cdot\binom nr=r(r-1)\cdot\binom nr+r \cdot\binom nr=n(n-1)\cdot\binom{n-2}{r-2}+n\cdot\binom{n-1}{r-1}$$

Now set $a=b=1$ in the following identity $$\sum_{r=0}^m(a+b)^m=\sum_{r=0}^m\binom mr a^{m-r}b^r$$

Answer 2

$$f(n)=\sum_{i=0}^n i^2 \binom{n}{i}$$

So, what we are basically doing is that, first we are choosing,say, $i$ persons from a group of $n$ persons and then among the choosen ones,we are selecting,say, a secretary and a manager(secretary and maneger can be the same person) . As you can see,this can be done in $\binom{n}{i}.i^2$ ways.

Now,$f(n)$ is sum of all the ways the above thing can be done(including the case that we don't choose any of the person at all).

To calculate $f(n)$ , suppose the secretary and the manager is the same person. So first we choose the secretary from the total of $n$ persons and then choose remaining ones in $2^{n-1}$ ways. Also, if the secretary and the manager is two different person then this can be done by $$n×(n-1)×2^{n-2}$$ ways. And we have only one case left to count,which is the case where we choose no one.But note that the sum doesn't get affected when $i=0$

So,$$f(n)=n2^{n-1} + n(n-1)2^{n-2} $$