Calculate $\lim_{n \to \infty}\binom{2n}{n}$ without using L'Hôpital's rule.

Question

Questions:

(1) Calculate

$$\lim_{n \to \infty}\binom{2n}{n}$$

(2) Calculate

$$\lim_{n \to \infty}\binom{2n}{n} 2^{-n}$$

without using L'Hôpital's rule.

Attempted answers:

(1)

Here I start by using the definition of a binomial:

$$\lim_{n \to \infty}\binom{2n}{n} = \lim_{n \to \infty} \frac{(2n)!}{n!(2n-n)!} = \lim_{n \to \infty} \frac{(2n)!}{n!n!} = \lim_{n \to \infty} \frac{2n \cdot (2n-1) \cdot (2n-2) \cdot ... \cdot (n + 1) \cdot n!}{n! \cdot n!}$$

Canceling one n! gives:

$$\lim_{n \to \infty} \frac{2n \cdot (2n-1) \cdot (2n-2) \cdot ... \cdot (n + 1)}{n!}$$

Here I argue that, surely, the numerator grows faster than the denominator and so the result must be that the limit grows towards $\infty$. Is this sufficiently mathematically rigorous?

(2)

My first attempt looked at the binomial theorem in an effort to get the expression to look something like the general form:

$$(a+b)^{n} = \sum_{k=0}^{n} a^{k} b^{n-k}$$

but it does not quite seem to match, since $k$ would have to be $0$ so that $a$ becomes $= 1$ does not interfere, but then $n-k$ would be $n$ instead.

My second attempt was to do what I did in (1), but then multiply it by $2^{-n}$:

$$\lim_{n \to \infty} \frac{2n \cdot (2n-1) \cdot (2n-2) \cdot ... \cdot (n + 1)}{n!} \cdot \frac{1}{2^{n}}$$

Now we can cancel one of the $2$s in the $2^{n}$ for every second factor in the numerator since they (i.e. 2n, 2n-2) are divisible by 2. But there are n factors in the numerator, so at most $\frac{n}{2}$ factors can be canceled.

Issues:

(a) is my answer to (1) sufficiently mathematically rigorous? Is it really "obvious" that the numerator grows faster or are there additional arguments that should be provided for the argument to be convincing?

(b) what are some more productive approaches to question (2)?

Answer 1

For part (1), letting $a_n:=\binom{2n}n,$ you should be able to show that $$\frac{a_{n+1}}{a_n}=\frac{(2n+2)(2n+1)}{(n+1)^2}=\frac{2(2n+1)}{n+1}=3+\frac{n-1}{n+1}\ge3.$$ Put another way, $a_{n+1}\ge3a_n$ for all $n,$ which should allow you to conclude readily that $a_n\ge 3^n$ for all $n$, at which point you're pretty much done.

As for (2), I would delay cancellation, working from $$\frac{(2n)!}{2^nn!n!}$$ instead. You can transform the numerator into the product of the first $n$ odd positive integers, and the denominator into $n!,$ then proceed from there in a similar fashion to part (1).

Added: More straightforwardly, part (1) allows you to conclude that $$\binom{2n}n\cdot2^{-n}\ge\left(\frac32\right)^n$$ for all $n,$ whence (2) is easy.

Answer 2

For a) I would suggest the following:

$$ \prod_{j=1}^{n} (1+\frac{j}{n}) = e^{\log \prod_{j=1}^{n} (1+\frac{j}{n})} = e^{\sum_{j=1}^{n} \log(1+\frac{j}{n})} \sim e^{\sum_{j=1}^{n} \frac{j}{n}} = e^{\frac{1}{2} \cdot (n+1)} \to_n \infty $$

Answer 3

I would not accept your solution to (1); $x^2+x$ grows faster than $x^2$, but the ratio approaches 1.
It is easier to prove $(2)$ first: The fraction equals $$\frac{2n}{2n}\frac{2n-1}{2n-2}\frac{2n-2}{2n-4}...\frac{n+1}{2}$$ Can you show that fraction grows without limit?

Answer 4

An elementary way to do the first limit: note $$\begin{align*} \binom{n-1}{k-1} + \binom{n-1}{k} &= \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-1)!} \\ &= \frac{(n-1)!}{(k-1)!(n-k-1)!} \left( \frac{1}{n-k} + \frac{1}{k} \right) \\ &= \frac{(n-1)!}{(k-1)!(n-k-1)!} \cdot \frac{n}{k(n-k)} \\ &= \frac{n!}{k!(n-k)!} = \binom{n}{k}. \end{align*}$$ Consequently, $$\binom{2n}{n} = \binom{2n-1}{n-1} + \binom{2n-1}{n} \ge \binom{2n-1}{n-1}.$$ Repeating this process, we find $$\binom{2n}{n} \ge \binom{2n-2}{n-2} \ge \ldots \ge \binom{2n-n+1}{1} = n+1,$$ hence the limit is unbounded as $n \to \infty$. It's not by any means a tight series of inequalities, but it gets you there.

Answer 5

Since $$4^n = \sum_{i=0}^{2n} \binom{2n}{i} \le 2n \binom{2n}{n}$$ We have $$\binom{2n}{n} \cdot 2^{-n} \ge \frac{2^{n-1}}{n}$$ The rest is easy. Stirling's Approximation should also give you a overkill solution.