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?

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$$

  • Do not see.. 2nd equation with $a=b=1$ is exaclty cardinality of powerset, and 1st one does work. But I still dont see idea behind. – Timo Junolainen Jan 28 '16 at 17:33
  • @TimoJunolainen let $m->n-2, r->r-2, a=1, b=1$, $ m->n-1, r->r-1, a=1, b=1$ respectively on the rhs of the last formula, you will find what u get, and take its sum. – Larry Eppes Feb 1 '16 at 13:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.