4
$\begingroup$

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?

$\endgroup$

2 Answers 2

6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 28, 2016 at 17:33
  • $\begingroup$ @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. $\endgroup$ Feb 1, 2016 at 13:41
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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