Proving $\binom{2n}{n} \geq \frac{2^{2n}}{n+1}$ combinatorially

Question

On trying to answer this question, with duplicate here, I was wondering if there is a combinatorial interpretation of the expression.

I tried something like $$n\binom{2n}{n} \geq 2^{2n}-\binom{2n}{n}=|A_n|$$ where $A_n=\{x\in \{0,1\}^{2n}:\text{number of 1's}\neq \text{number of 0's}\}$ and I could not find a meaningful injection from $A_n$ to $[n]\times \binom{[2n]}{n}$

One of the things I try was noticing that at some point the symbol with more appearances passes $n$ from left to right (i.e., there exists $k$ such that $\max \{|x_1\cdots x_k|_0,|x_1\cdots x_k|_1\}>n$, and so I would swap all of the symbols but is not injective.

I guess the opposite problem (i.e., finding a surjection) helps but seems harder. Also, the difference is not in the OEIS.

Answer 1

In Two bijections for the area of Dyck paths, E. Pergola and Area of Catalan paths, W. Woan one can read that if $D$ is a Dyck path and $a(D)$ is the area under the path, then $$A_n=\sum _{D\text{ Dyck path length 2n}}a(D)=\frac{1}{2}\left (4^n-\binom{2n+1}{n}\right ).$$ check the oeis of the sequence $2A_n$.

But by giving full area to all Dyck paths, one can bound this by $\frac{n^2}{2}\times C_n=\frac{n^2}{2(n+1)}\binom{2n}{n}$ so $$2A_n=2^{2n}-\binom{2n+1}{n}\leq \frac{n^2}{n+1}\binom{2n}{n},$$ so $$2^{2n}\leq \binom{2n}{n}\left (\frac{n^2}{n+1}+\frac{2n+1}{n+1}\right )=\binom{2n}{n}(n+1).$$

Answer 2

For each $k\in \{0,1,\dots,n\}$, let $$ a_k=\binom{2n}{n+k}+\binom{2n}{k-1} $$ Note that $a_0=\binom{2n}{n}$, and $a_0+a_1+\dots+a_n=4^n$. As long as we can show $a_0$ is the largest of $a_0,a_1,\dots,a_n$, we can conclude $a_0\ge 4^n/(n+1)$. Therefore, we just need to show $$ \binom{2n}n\ge \binom{2n}{n+k}+\binom{2n}{k-1} $$ Since $a_k=a_{n+1-k}$, it suffices to prove this when $k\le (n+1)/2$.

Using the reflection principle, we know that $$ \binom{2n}n-\binom{2n}{n+k}=\#\{\text{lattice paths $(0,0)\to (n,n)$ which stay above $y=x-k$}\}\tag{A} $$ On the other hand, $$ \binom{2n}{k-1}=\#\{\text{lattice paths $(0,0)\to (k-1,2n-k+1)$}\}\tag{B} $$ Given a path in $(\mathrm B)$, it must intersect the line $y=n-k+1+x$ (this is where use use the fact that $k\le (n+1)/2$). To get an injection from $(\mathrm B)\to (\mathrm A)$, reflect the path in $(\mathrm B)$ through the line $y=n-k+1+x$, at the last point it hits that line. The result is a path in $$ \{\text{lattice paths $(0,0)\to (n,n)$ which hit the line $y=n-k+1+x$}\}\tag{C} $$ We have an injection $(\mathrm B)\to (\mathrm C)$, so we need to argue why $(\mathrm C)\subseteq (\mathrm A)$. This is true because the lines $y=x-k$ and $y=x+(n-k+1)$ are too far apart for a lattice path from $(0,0)$ to $(n,n)$ to hit both lines.