Limit of sum (variable in summand and limit)

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.