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

Printable View

January 9th 2013, 12:56 AM
NZAU1984

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

Our teacher asked this question in a homework :

Prove : $\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 $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.
January 9th 2013, 01:20 AM
MarkFL

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

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

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

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

$1\ge1$

True.

2. State the induction hypothesis $P_k$ :

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

Next, look at:

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

and

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

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

What do you find?
January 9th 2013, 03:36 PM
NZAU1984

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 :
-> $(2k)!$ is $> (k!)^2$
-> the left "big parenthesis" is > the right "big parenthesis"

But what about the $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.
January 9th 2013, 03:40 PM
MarkFL

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. ;)
January 9th 2013, 06:18 PM
MarkFL

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

You should verify that:

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

and

$\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:

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

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

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

$4k+2\ge0$

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

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

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