Binomials and Proof by Induction

[math222]

Homework Statement

Prove (n choose k) ≤ ((en)/k)^k by induction on k.

Homework Equations

I can't of anything that's awfully relevant besides the general steps of induction.

The Attempt at a Solution

So I found it true for the k=1 case which was easy enough. Then assumed true the k case. And now have to prove the k+1 case.

So after working on the problem for awhile, I arrived at
((n-k)/(k+1)) * (n choose k) ≤ ((en)/k)^k * ((n-k)/(k+1))

but from here I'm stuck and not sure how to deconstruct the (n choose k) into something workable, let alone construct (n choose k+1). any help would be greatly appreciated.

 

[Sourabh N]

I'm not sure I understand the notation. What is "en"?

 

[math222]

the Euler number, e=2.718 or something i think. so en is e*n

 

[Ray Vickson]

Homework Statement

Prove (n choose k) ≤ ((en)/k)^k by induction on k.

Homework Equations

I can't of anything that's awfully relevant besides the general steps of induction.

The Attempt at a Solution

So I found it true for the k=1 case which was easy enough. Then assumed true the k case. And now have to prove the k+1 case.

So after working on the problem for awhile, I arrived at
((n-k)/(k+1)) * (n choose k) ≤ ((en)/k)^k * ((n-k)/(k+1))

but from here I'm stuck and not sure how to deconstruct the (n choose k) into something workable, let alone construct (n choose k+1). any help would be greatly appreciated.

It might be helpful to note that
$${n \choose k} = \frac{n (n-1) \cdots (n-k+1)}{k!}<br /> = \frac{n^k (1 - \frac{1}{n})(1 - \frac{2}{n}) \cdots (1 - \frac{k-1}{n})}{k!},$$ and you can further bound the numerator and denominator.

RGV

 

[HallsofIvy]

the Euler number, e=2.718 or something i think. so en is e*n

Then you mean e^n. "en" and "e*n" would be e times n.

 

[math222]

no i mean e times n. hence en or e*n.

 

[math222]

i under the bound for the numerator, but i don't understand how to bound the denominator?