# Limit of sum (variable in summand and limit)

Can someone help evaluate this limit: $$\lim_{n\rightarrow \infty} \sum_{k=0}^n\frac{k^k(n-k)^{n-k}}{k!(n-k)!}n!n^{-n-1/2}$$

-
What have you tried? And if this is homework, please add the homework tag. – Stefan Hansen Jan 29 '13 at 10:03

Stirling's approximation shows that the limit can be rewritten $$\lim_{n\rightarrow \infty} \sum_{k=0}^n\frac{k^k(n-k)^{n-k}}{k!(n-k)!}\sqrt{2\pi}e^{-n}$$, but I don't know if that makes it easier.

-
No, it cant be written like that based on what you know, the limit of the product of two expressions only equals the product of each individual limit, if both limits exist. – Ethan Jan 29 '13 at 11:05

Are you sure the binomial theorem works? Are you suggesting $$\sum_{k=0}^n \frac{n!}{k!(n-k)!}k^k(n-k)^{n-k} = (k+n-k)^n$$? $k$ is the dummy variable used in the sum though; it is not constant.

-
It doesn't sorry – Ethan Jan 29 '13 at 11:01

Stirling's approximation gives us that $$n!=\sqrt{2\pi n}\ n^n\,e^{-n}(1+O(1/n))\tag{1}$$ As it is simply the $j=k$ term in $$\sum_{j=0}^n\binom{n}{j}\left(\frac{k}{n}\right)^{j}\left(1-\frac{k}{n}\right)^{n-j}=1\tag{2}$$ we can deduce that $$\binom{n}{k}\left(\frac{k}{n}\right)^{k}\left(1-\frac{k}{n}\right)^{n-k}\le1\tag{3}$$ Therefore, \begin{align} &\sum_{k=0}^n\frac{k^k(n-k)^{n-k}}{k!(n-k)!}n!n^{-n-1/2}\\ &=\sum_{k< m}\binom{n}{k}\left(\frac{k}{n}\right)^{k}\left(1-\frac{k}{n}\right)^{n-k}n^{-1/2}\\ &+\sum_{k=m}^{n-m}\binom{n}{k}\left(\frac{k}{n}\right)^{k}\left(1-\frac{k}{n}\right)^{n-k}n^{-1/2}\\ &+\sum_{k>n-m}\binom{n}{k}\left(\frac{k}{n}\right)^{k}\left(1-\frac{k}{n}\right)^{n-k}n^{-1/2}\\ &=O(mn^{-1/2})+\frac1{\sqrt{2\pi}}\sum_{k=m}^{n-m}\frac1{\sqrt{k}\sqrt{n-k}}(1+O(1/m))+O(mn^{-1/2})\\ &=O(mn^{-1/2})+\frac1{\sqrt{2\pi}}\sum_{k=0}^n\frac1{\sqrt{k/n}\sqrt{1-k/n}}\frac1n(1+O(1/m))\tag{4} \end{align} We can add the tails to the last sum in $(4)$ since each of the $2m$ terms is $\le n^{-1/2}$ and absorb the difference into $O(mn^{-1/2})$.

Approximating with Riemann sums, $(4)$ becomes $$\lim_{n\to\infty}\sum_{k=0}^n\frac{k^k(n-k)^{n-k}}{k!(n-k)!}n!n^{-n-1/2} =\frac1{\sqrt{2\pi}}\int_0^1\frac{\mathrm{d}x}{\sqrt{x-x^2}}(1+O(1/m))\tag{5}$$ Since $m$ was arbitrary, we get \begin{align} \lim_{n\to\infty}\sum_{k=0}^n\frac{k^k(n-k)^{n-k}}{k!(n-k)!}n!n^{-n-1/2} &=\frac1{\sqrt{2\pi}}\int_0^1\frac{\mathrm{d}x}{\sqrt{x-x^2}}\\ &=\frac1{\sqrt{2\pi}}\int_{-1}^1\frac{\mathrm{d}x}{\sqrt{1-x^2}}\\ &=\sqrt{\frac\pi2}\tag{6} \end{align}

-