Prove that 2n choose n is greater than or equal to ...

Our teacher asked this question in a homework :

Prove : $\displaystyle \binom{2n}{n} \ge \frac{4^{n}}{2n+1}$

I found these pages which gave me some clues :

number theory - prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer - Mathematics

Prove that 2n choose n is less than or equal to 4^n? - Yahoo! Answers

However, I can't figure that out ! According to the 2nd page, if the right member was only $\displaystyle 4^n$, then the left member would be less than or equal to the right member.

I just don't know what to do.

You help would be appreciated.

Thanks.

Re: Prove that 2n choose n is greater than or equal to ...

I would use induction here. I will assume $\displaystyle n\in\mathbb{N}_0$

1. Show the base case $\displaystyle P_0$ is true:

$\displaystyle {2\cdot0 \choose 0}\ge\frac{4^0}{2\cdot0+1}$

$\displaystyle 1\ge1$

True.

2. State the induction hypothesis $\displaystyle P_k$:

$\displaystyle {2k \choose k}\ge\frac{4^k}{2k+1}$

Next, look at:

$\displaystyle {2(k+1) \choose k+1}-{2k \choose k}$

and

$\displaystyle \frac{4^{k+1}}{2(k+1)+1}-\frac{4^k}{2k+1}$

That is, see if $\displaystyle P_{k+1}-P_k$ gives you a true inequality.

What do you find?

1 Attachment(s)

Re: Prove that 2n choose n is greater than or equal to ...

The PDF file is what I got... but I'm not too sure how to compare left with right...

**I PROBABLY MADE ALGEBRAIC ERRORS !**

I know that :

-> $\displaystyle (2k)!$ is $\displaystyle > (k!)^2$

-> the left "big parenthesis" is > the right "big parenthesis"

But what about the $\displaystyle 4^k$ ?!

I'm surely this is much simpler than I think, but my brain's kind of burnt right now !

Thanks !

The PDF is in French, but I wrote English translation in red.

Re: Prove that 2n choose n is greater than or equal to ...

That is essentially the same technique I have in mind, but I can get you there much more simply. Unfortunately, I don't have the time at the moment. I will be glad to elaborate more in a few hours. If you compute the differences I suggest, it should all become clear. ;)

Re: Prove that 2n choose n is greater than or equal to ...

You should verify that:

$\displaystyle {2(k+1) \choose k+1}-{2k \choose k}=\frac{3k+1}{k+1}{2k \choose k}$

and

$\displaystyle \frac{4^{k+1}}{2(k+1)+1}-\frac{4^k}{2k+1}=\frac{6k+1}{2k+3}\cdot\frac{4^k}{ 2k+1}$

So, next, let's verify:

$\displaystyle \frac{3k+1}{k+1}\ge\frac{6k+1}{2k+3}$

$\displaystyle (3k+1)(2k+3)\ge(6k+1)(k+1)$

$\displaystyle 6k^2+11k+3\ge6k^2+7k+1$

$\displaystyle 4k+2\ge0$

This is obviously true for $\displaystyle k\in\mathbb{N}_0$. So, multiplying the induction hypothesis $\displaystyle P_k$ by:

$\displaystyle \frac{3k+1}{k+1}\ge\frac{6k+1}{2k+3}$

and then adding the result to $\displaystyle P_k$, we will obtain $\displaystyle P_{k+1}$, thereby completing the proof by induction.