2
$\begingroup$

my name is Rafał and I decided to create this thread because of my inability to find a solution. I have been fighting with this inequality for 1.5 week and I have a hope that you will give me any hint (no solution but clue). So I need to prove it to prove something bigger. I'm talking about inequality:

$${2n\choose n} \ge {n \choose {\left\lfloor \frac{n}{2} \right\rfloor}}$$

In my opinion it's obvious, but formally i need to prove it.

1)So I wrote a simple program in C++ for n from 1 to 11 and everything was allright (bigger n implicited problem with memory). It was very clear to see that ${2n\choose n}$ was growing faster.

2)I was trying to use definition of binomial coefficients and by using mathematical induction proved this inequality but there were such a big problems with ${\left\lfloor \frac{n}{2} \right\rfloor}$. (Yes, I used ${\frac{n}{2}-1 \le \left\lfloor \frac{n}{2} \right\rfloor} \le \frac{n}{2} \le \frac{n}{2}+1$ but it wasn't helpful)

3) I have tried to define a sequence like this: $a_n = \frac{{2n\choose n}}{{n \choose {\left\lfloor \frac{n}{2} \right\rfloor}}}$. My idea was to show that the sequence is increasing for every n ($\frac{a_{n+1}}{a_n} \ge 1$). When it'll be true this sequence must be bounded below by $a_1=1$ and it'll be the end of proof.

But every of my methods were incorect or maybe i had a problem with transformations. I have next idea to use Stirling approximation but I have completely no idea if it will be corect. Any Hint?

$\endgroup$
1
$\begingroup$

Intuitively (and combinatorially), ${n \choose r}$ is the number of ways of forming strings of length $n$ over the alphabet $\{0,1\}$ where $r$ of the letters are $0$.

Every string counted by ${n \choose \lfloor{\frac{n}{2}}\rfloor }$ can be extended to a string counted by ${2n \choose n}$. Moreover, there are multiple ways of doing it. So the inequality follows.

$\endgroup$
0
$\begingroup$

Setting $n=2m$, the inequation can be rewritten as$$(4m)!m!^2\ge(2m)!^3.$$

Let us expand for $m=3$:

$$12.11.10.9.8.7.6.5.4.3.2.1.(3.2.1)^2\ge(6.5.4.3.2.1)^3.$$ We first simplify by $(2m)!$: $$12.11.10.9.8.7.(3.2.1)^2\ge(6.5.4.3.2.1)^2.$$ Next by $m!^2$: $$12.11.10.9.8.7\ge(6.5.4)^2.$$ And by $(2m)!/m!$: $$2.11.2.9.2.7\ge6.5.4.$$ Every remaining factor in the RHS has a corresponding larger factor in the LHS.

This generalizes to other $m$ and the same work needs to be repeated for odd $n=2m+1$.


Again for $m=3$:

$$14.13.12.11.10.9.8.7.6.5.4.3.2.1.(3.2.1)^2\ge(7.6.5.4.3.2.1)^3.$$ We first simplify by $(2m+1)!$: $$14.13.12.11.10.9.8.(3.2.1)^2\ge(7.6.5.4.3.2.1)^2.$$ Next by $m!^2$: $$14.13.12.11.10.9.8\ge(7.6.5.4)^2.$$ And by $(2m+1)!/m!$: $$2.13.2.11.2.9.2\ge7.6.5.4.$$

$\endgroup$
0
$\begingroup$

$$ \binom{2n}{n} = \sum_{k=0}^n \binom{n}{k}^2 \ge \binom{n}{\lfloor\frac n2\rfloor}^2 \ge \binom{n}{\lfloor\frac n2\rfloor} $$ The first equality is proved in this question, for example.

The related inequalities $$ \binom{2n}{n} < 2^n\binom{n}{n/2} < 2\binom{2n}{n} $$ are in this question.

Also, this question shows $(\frac nk)^k \le \binom nk$; thus $$ \binom{2n}{n} \ge \left(\frac{2n}{n}\right)^n = 2^n \ge \binom n{\lfloor n/2\rfloor} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.