Evaluating a limit with combinations

Question

I was having trouble evaluating the follwing limit: $\lim_{n\to\infty}\frac{4^n-C(2n+1,n)}{2^n}.$ By simply plugging in values I know the limit should equal infinity but my showing this rigorously was difficult. First I expanded out and got, \begin{align*} \lim_{n\to\infty}\frac{4^n-\frac{(2n+1)!}{n!(n+1)!}}{2^n}. \end{align*} Next I tried approached it two ways:

First I tried taking the limit of the difference portion which is: \begin{align*} \lim_{n\to\infty} \frac{4^n}{2^n}-\lim_{n\to\infty}\frac{\frac{(2n+1)!}{n!(n+1)!}}{2^n} \end{align*} but this was trouble some since I ended up with an $\infty-\infty$ situation.

Secondly, I tried using L'Hôpital's rule which gives: \begin{align*} \lim_{n\to\infty} \frac{\frac{d}{dn}\bigg(4^n-\frac{(2n+1)!}{n!(n+1)!}\bigg)}{\frac{d}{dn}2^n}. \end{align*} This turned out to be trouble some since I ended up with \begin{align*} \lim_{n\to\infty} \frac{4^nlog(4)-\frac{d}{dn}\big(\frac{(2n+1)!}{n!(n+1)!}\big)}{2^nlog(2)}. \end{align*} solving for $\frac{d}{dn}\big(\frac{(2n+1)!}{n!(n+1)!}\big)$ lead me down the rabbit hole of gamma functions and digamma functions which lead no where for me.

Any advice on how I should approach evaluating the following limit? I feel as though I am missing something and I am not clever enough to continue down the rabbit hole of the second approach to find any results. Thanks!

Answer 1

You can use the asymptotics of $T_n:=4^{-n}\binom{2n}{n}\color{blue}{\asymp\frac{1}{\sqrt{\pi n}}}$, or get an inequality elementarily: $$T_n^2=\left(\frac12\cdot\frac34\cdots\frac{2n-1}{2n}\right)^2\leqslant\frac12\cdot\frac34\cdots\frac{2n-1}{2n}\times\frac{2}{3}\cdot\frac45\cdots\frac{2n}{2n+1}=\frac{1}{2n+1},$$ so that $\binom{2n+1}{n}=\frac{2n+1}{n+1}\binom{2n}{n}\leqslant 4^n\frac{\sqrt{2n+1}}{n+1}$, which is sufficient for your needs.

Answer 2

When I see factorials, I automatically think about logarithms and Stirling approximation $$a_n=\frac{(2n+1)!}{n!(n+1)!}\implies \log(a_n)=\log((2n+1)!)-\log(n!)-\log((n+1)!)$$

Apply three times Stirling approximation and continue with Taylor to get $$\log(a_n)=n \log (4)+\left(\log (2)-\frac{1}{2} \log (\pi n)\right)-\frac{5}{8 n}+O\left(\frac{1}{n^2}\right)$$ $$a_n=e^{\log(a_n)}\sim\frac{2^{2 n+1}}{\sqrt{\pi n} }e^{-\frac{5}{8 n}}=4^n\frac{2}{\sqrt{\pi n} }e^{-\frac{5}{8 n}}$$ $$\frac{4^n-\frac{(2n+1)!}{n!(n+1)!}}{2^n} \sim 2^n \left(1-\frac{2 e^{-\frac{5}{8 n}}}{\sqrt{\pi n } }\right)$$

Use it for $n=5$; the exact value is $\frac{281}{16}=17.5625$ while the approximation gives $32-\frac{64}{\sqrt[8]{e} \sqrt{5 \pi }}\approx 17.7494$.