# proving inequality

• March 31st 2013, 01:40 PM
MaxiQ
proving inequality
so i started studying calculus and stumbled upon an inequality I'm having difficulties to prove,

for every 1<=k<=n prove
C(n,k)*1/(n^k)<=1/(2^(k-1))
so i brought it to
C(n,k)*2^k<=2*n^k
and now i tried induction and it got to newton's binomial, and then im stuck...

looks something like

C(n,k-1)*2^k+c(n,k)*2^k<=2*(1+n+n^2...kn^k-1+n^K) used c(n+1,k)=c(n,k-1)+c(n,k)
(dont know how to write epsilon so its open ^^^^^ )
while the red thingy is the assumption of the induction,
how i prove the pink part??

Hint: write $n^{-k}\binom nk=\prod_{j=0}^{k-1}\left(1-\frac kn\right)\cdot \frac 1{k!}\leqslant \frac 1{k!}.$