# Estimation for sum over binomial coefficients

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.

• 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... – Clement C. Mar 11 '14 at 16:44
• @ClementC. Thanks for pointing out the error. Fixed it ($n$ on LHS should have been $c$). – Timo mue Mar 11 '14 at 16:50