Intereting Posts

Composition of Analytic Functions
Second pair of matching birthdays
Prove that $xy \leq\frac{x^p}{p} + \frac{y^q}{q}$
the sum of $1-\frac{1}{5}+\frac{1}{9}-\frac{1}{13}+…$
An example of a group such that $G \cong G \times G$
Simplicial Complexes, Triangulation general question.
principal value as distribution, written as integral over singularity
Proving that the join of a path-connected space with an arbitrary space is simply-connected
Using Fermat's Little Theorem, find the least positive residue of $3^{999999999}\mod 7$
How to prove an identity (Trigonometry Angles–Pi/13)
On finite 2-groups that whose center is not cyclic
Examples of compact sets that are infinite dimensional and not bounded
Rationalizing expressions
How to define the $0^0$?
$\mathbb{Z}_m \times \mathbb Z_n$ is cyclic if and only if $\gcd(m,n)=1$

I am trying to show that $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$. I found that using stirling’s approximation, I can get:

$$

\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=

\lim_{n\to \infty}{\frac{(2n)!}{n!^2*2^{2n}}}=

\lim_{n\to \infty}{\frac{(\frac{2n}{e})^{2n}\sqrt{2\pi (2n)}}{((\frac{n}{e})^n\sqrt{2\pi n})^2*2^{2n}}}

=\lim_{n\to \infty}{\frac{2\sqrt{\pi n}}{2\pi n}}

=0

$$

But this seems inelegant where there should be a more elegant, combinatorial proof. Is there an easier way?

- How to prove: $\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$
- Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$ (Dixon's identity)
- Proving the combinatorial identity ${n \choose k} = {n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k}$
- Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$
- Intuitive ways to get formula of binomial-like sum
- Prime dividing the binomial coefficients

- Expected value when die is rolled $N$ times
- Combinations of 6 students among 20, at least one male
- How many ways can $b$ balls be distributed in $c$ containers with no more than $n$ balls in any given container?
- Algorithms for mutually orthogonal latin squares - a correct one?
- Please help me compute this$ \sum_m\binom{n}{m}\sum_k\frac{\binom{a+bk}{m}\binom{k-n-1}{k}}{a+bk+1}$
- Lights out game on hexagonal grid
- Choice Problem: choose 5 days in a month, consecutive days are forbidden
- number of strictly increasing sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$?
- How many turns can a chess game take at maximum?
- In a group of 6 people either we have 3 mutual friends or 3 mutual enemies. In a room of n people?

Not a combinatorial approach, but a fun way of doing it is showing that $$\frac{\binom{2n}{n}}{4^n}=\frac{1}{2\pi}\int_0^{2\pi} \cos^{2n} x\; dx$$

Basically, writing $\cos x = \frac12\left(e^{ix}+e^{-ix}\right)$. So $\cos^{2n} x$ has constant term $\binom{2n}{n}/4^n$.

Since $\cos^{2n} x\to 0$ for almost all $x$, it is pretty easy to show that the above integral tends to zero as $n\to\infty$.

Specifically, on the intervals $(\varepsilon,\pi-\varepsilon)\cup(\pi+\varepsilon,2\pi-\varepsilon)$, $\cos^{2n}x\to 0$ uniformly.

Here’s a non-combinatorial argument that avoids Stirling’s approximation.

$$\begin{align*}

p_n\triangleq\frac{\binom{2n}n}{4^n}&=\frac{(2n)!}{(2^nn!)^2}\\\\

&=\frac{(2n)!(2n-1)!!^2}{(2n)!^2}\\\\

&=\frac{(2n-1)!!^2}{(2n)!}\\\\

&=\prod_{k=1}^n\frac{2k-1}{2k}\\\\

&=\prod_{k=1}^n\left(1-\frac1{2k}\right)\;,

\end{align*}$$

so

$$\ln p_n=\sum_{k=1}^n\left(-\sum_{m\ge 1}\frac1{m(2k)^m}\right)\le-\sum_{k=1}^n\frac1{2k}=-\frac12H_n\;,$$

where $H_n$ is the $n$-th harmonic number. The harmonic series diverges, so $\lim_{n\to\infty}\ln p_n=-\infty$, and therefore $\lim_{n\to\infty}p_n=0$.

Note: The double factorial $(2n-1)!!$ is the product of the odd positive integers not exceeding $2n-1$:

$$(2n-1)!!=\prod_{k=1}^n(2k-1)=\frac{(2n)!}{2^nn!}\;.$$

Another was is to use the generating function of the central binomial coefficients, that is $$\frac{1}{\sqrt{1-x}}=\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}}x^{n}.$$ We will make use of the fact that $x_{n}=\binom{2n}{n}\frac{1}{4^{n}}$ is a monotically decreasing sequence to make sure there are no oscillations. It is monotonic since $$x_{n+1}=\binom{2n}{n}\frac{1}{4^{n}}\frac{(2n+2)(2n+1)}{4\left(n+1\right)^{2}}=x_{n}\left(1-\frac{1}{2n+2}\right).$$ Taking the indefinite integral of both sides of the generating function, we have that for $|x|<1,$ $$2-2\sqrt{1-x}=\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}}\frac{x^{n+1}}{n+1}.$$ Now, the left hand side converges as $x\rightarrow1$ from the left, and so, since the series has strictly positive coefficients, the right hand side must converge as well. This implies that $$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}}\frac{1}{n+1}$$ is a convergent series, and since the coefficients $\binom{2n}{n}\frac{1}{4^{n}}$ are monotonically decreasing, the divergence of the harmonic series implies that we must have $$\binom{2n}{n}\frac{1}{4^{n}}\rightarrow0.$$

**Added Details:** Based on the comments, I thought I would give a precise proof of why the series must converge, without appealing to Littlewood’s Tauberian theorem. The proof only requires that the coefficients of the power series, $a_n$, are nonnegative. Let $a_n\geq0$, $s_m=\sum_{n=0}^m a_n$ be the partial sums, and suppose that $\sum_{n=0}^{\infty}a_{n}x^{n}\leq C$ for all $x\in(0,1),$ for some positive constant $C$. Then for $x\in(0,1),$ $$s_{m}=\sum_{n=0}^{m}a_{n}\left(1-x^{n}\right)+\sum_{n=0}^{m}a_{n}x^{n}$$ $$\leq(1-x)\sum_{n=0}^{m}a_{n}\left(1+x+\cdots+x^{n-1}\right)+C$$

$$\leq(1-x)\sum_{n=0}^{m}na_{n}+C.$$ Taking $x$ sufficiently close to $1$, we can make $(1-x)\sum_{n=0}^{m}na_{n}\leq 1$, and so it follows that $s_{m}\leq C+1.$ This means that $s_m$ is monotonically increasing and bounded, its limit, $\sum_{n=0}^\infty a_n$ must converge. In particular, our series $$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{4^{n}(n+1)},$$ is convergent.

Here is what I think “a combinatorial approach:” Note that $\binom{2n}{n}$ is the number of $n$ element subsets of a $2n$ element set. Consider the quantities $\binom{2n}{n+i},\,i=1,\ldots,k$ for some small $k$ (relative to $n$). We have the relationship $\binom{2n}{n+1} = \frac{n}{n+1}\binom{2n}{n}$, and in general, $\binom{2n}{n+k} = \frac{n-k+1}{n+k}\binom{2n}{n+k-1}$. Now for any $k$, we can choose $n$ so large that $\frac{n-k+1}{n+k}$ is at least $1-\frac{1}{2k}$. This gives us the estimate $\binom{2n}{n+k} \geq (1-\frac{1}{2k})\binom{2n}{n+k-1} \geq \cdots \geq (1-\frac{1}{2k})^k\binom{2n}{n} \geq \frac{1}{2}\binom{2n}{n}$. Therefore, for any $i\in\{1,\ldots,k\}$ and when $n$ is large enough, the number of $n+i$ element subsets of a $2n$ element set is at least $\frac{1}{2}\binom{2n}{n}$. Hence, $\frac{k}{2}\binom{2n}{n} \leq 4^n$. Now, let $k\rightarrow\infty$.

Speaking of combinatorial proofs,

$$

\sum_{k=0}^n\frac{\binom{2k}{k}}{2^{2k}}\frac{\binom{2(n-k)}{n-k}}{2^{2(n-k)}}=1.

$$

The key step of a combinatorial proof is that $p_k=\binom{2k}k2^{-2k}$ is the probability that random path with $2k$ steps $(1,1)$ and $(1,-1)$ doesn’t touch $x$-axis after the start. So now we see that sequence $p_k$ is monotonic.

But then the first identity obviously implies $p_k\to0$ (if $\forall k\;p_k\gt\epsilon$, $1=\sum p_kp_{N-k}\gt N\epsilon\gt1$)

- Characteristic subgroups $\phi(H) \subseteq H$
- Function which preserves closed-boundedness and path-connectedness continuous?
- The kernel of $R \to A \otimes_R B$ is nil
- How do I prove that 15462227 and 15462229 relatively prime?
- Closed form for the summation $\sum_{k=1}^n\frac{1}{r^{k^2}}$
- Exponent of $GL(n,q)$.
- Is there a continuous non constant map $\mathbb{R}^2 \to \mathbb{S}^1$?
- Transpose Present Value of an Ordinary Annuity Formula for Interest Rate
- On irreducible factors of $x^{2^n}+x+1$ in $\mathbb Z_2$
- understanding of the “tensor product of vector spaces”
- Combinations of 5 integers from 1 to 100 such that differences between the sorted integers of each combination is at least 5 but not more than 10?
- A nontrivial p-group has nontrivial center
- Prove that $N(\gamma) = 1$ if, and only if, $\gamma$ is a unit in the ring $\mathbb{Z}$
- Field that contains $(\mathbb{Z}/p^n\mathbb{Z})^*$
- Jeep problem variant: cross the desert with as much fuel as possible