I am trying to show that a certain procedure for resource allocation is approximately efficient. For this I need to show that $$ \lim_{n\rightarrow \infty} \left(\frac{1}{e}\right)^n\sum_{c=2}^n \left[\binom{n}{c}\frac{1}{n^c}\sum_{k=1}^{\left\lfloor c/2\right\rfloor}\left[\binom{c}{k} (c-k)^k k^{(c-k)} e^{(c-k)}\right]\right] = 0. $$ Numerically, this is pretty obvious, but I would like to proove it formally. To estimate the inner sum, I found the identity $$ \frac{(a+b)^c}{a} = \sum_{k=0}^c \binom{c}{k}(a-k)^{k-1}(b+k)^{c-k} $$ on wolfram mathworld (equation (64) [here]). This looks a lot like my problem, but is missing the $e^{c-k}$ term. However, if I estimate $e^{c-k}$ by $e^c$, the entire term no longer converges.

  • 2
    $\begingroup$ The equation you copied from Wolfram is not right -- a typo or two have been inserted in the process. In particular, your RHS has no $n$ at all... $\endgroup$
    – Clement C.
    Mar 11, 2014 at 16:44
  • $\begingroup$ @ClementC. Thanks for pointing out the error. Fixed it ($n$ on LHS should have been $c$). $\endgroup$
    – Timo mue
    Mar 11, 2014 at 16:50


You must log in to answer this question.