combinatorial inequality

**kkoutsothodoros** · August 26th, 2010, 12:07 PM

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.

**Archie Meade** · August 26th, 2010, 01:15 PM

Originally Posted by kkoutsothodoros

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.

You could prove it via Proof By Induction...

P(k)

$\displaystyle\ 1+\binom{2n}{1}+\binom{2n}{2}+....+\binom{2n}{k}\ \le\ (2n)^k\ ?$

P(k+1)

$\displaystyle\ 1+\binom{2n}{1}+\binom{2n}{2}+....+\binom{2n}{k}+\ binom{2n}{k+1}\ \le\ (2n)^{k+1}\ ?$

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

Proof

$\displaystyle\ (2n)^k+\binom{2n}{k+1}\ \le\ 2n(2n)^k\ ?$

$\displaystyle\binom{2n}{k+1}\ \le\ (2n-1)(2n)^k$

$\displaystyle\frac{[2n]!}{[2n-(k+1)]![k+1]!}\ \le\ (2n-1)(2n)(2n)(2n)....$

$\displaystyle\frac{(2n)(2n-1)(2n-2)....}{(k+1)!}\ \le\ (2n-1)(2n)(2n)(2n)....$

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.

**kkoutsothodoros** · August 26th, 2010, 01:39 PM

thanks!

**Archie Meade** · August 26th, 2010, 02:03 PM

The proof is then complete when you examine the base case for k=2, assuming k is an integer.

$\displaystyle\ 1+\binom{2n}{1}+\binom{2n}{2}\ \le\ (2n)^2\ ?$

$\displaystyle\ 1+2n+\frac{2n(2n-1)}{2}\ \le\ 4n^2\ ?$

$\displaystyle\ 1+2n+n(2n-1)\ \le\ 4n^2\ ?$

$1+2n+2n^2-n\ \le\ 4n^2\ ?$

$2n^2+n+1\ \le\ 4n^2\ ?$

$n+1\ \le\ 2n^2\ ?$

$n(2n-1)\ \ge\ 1\ ?$

$\text{\footnotesize\ True for \;\;}n\ \ge\ 1$

Math Help Forum: combinatorial inequality

LinkBack

Thread Tools

Display

combinatorial inequality

Similar Math Help Forum Discussions

Binomial Inequality - Combinatorial Proof?

Another combinatorial proof

combinatorial sum

Combinatorial Analysis

Combinatorial proof