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

Our teacher asked this question in a homework :

Prove :

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 , 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

1. Show the base case is true:

True.

2. State the induction hypothesis :

Next, look at:

and

That is, see if 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 :

-> is

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

But what about the ?!

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:

and

So, next, let's verify:

This is obviously true for . So, multiplying the induction hypothesis by:

and then adding the result to , we will obtain , thereby completing the proof by induction.