Hi. I am trying to prove the following:

1 + C(2n, 1) + C(2n, 2) + ... + C(2n, k) <= (2n)^k for n >= k > 1.

I would appreciate any suggestions you all may have.

Thanks.

Printable View

- August 26th 2010, 12:07 PMkkoutsothodoroscombinatorial inequality
Hi. I am trying to prove the following:

1 + C(2n, 1) + C(2n, 2) + ... + C(2n, k) <= (2n)^k for n >= k > 1.

I would appreciate any suggestions you all may have.

Thanks. - August 26th 2010, 01:15 PMArchie Meade
You could prove it via Proof By Induction...

**P(k)**

**P(k+1)**

Try to prove that P(k+1) will be valid if P(k) is valid.

**Proof**

There are k+1 terms in the numerator of the LHS and k+1 terms on the RHS, since there are k occurances of 2n.

It's easy to see that the inequality holds. - August 26th 2010, 01:39 PMkkoutsothodoros
thanks!

- August 26th 2010, 02:03 PMArchie Meade
The proof is then complete when you examine the base case for k=2, assuming k is an integer.