# 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 at 10:03

## 3 Answers

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

-

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 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 at 11:01
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 8, "mathjax_display_tex": 9, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9318613409996033, "perplexity_flag": "head"}