Prove a theorem in combinatorics

Question

I want to show that for $k=1,...,(n-1)$ we have :

$\binom{n}{k}\leq \frac{n^n}{k^k(n-k)^{n-k}}$

I have used induction on $k$, but I have not deduced the above relation.

Answer 1

$(k+(n-k))^n \ge \binom nk k^k (n-k)^{n-k}$ because the RHS is one of the terms in the binomial theorem expansion of the LHS.

(This was question B2 on the 2004 Putnam; for some other interesting solutions, see Kedlaya's archive.)