Two inequalities with binomial coefficients I have two inequalities that I can't prove:


*

*$\displaystyle{n\choose i+k}\le {n\choose i}{n-i\choose k}$

*$\displaystyle{n\choose k} \le \frac{n^n}{k^k(n-k)^{n-k}}$


What is the best way to prove them? Induction (it associates with simple problems, but sometimes I find it difficult to use, what is worrying), or maybe combinatorial interpretation?
 A: For the first one, if you write out all the binomial coefficients and cancel identical factors on both sides, you're left with
$$\frac1{(i+k)!}\le\frac1{i!}\frac1{k!}\;,$$
which is clearly true.
For the second one, you can use Stirling's approximation in the form
$$\sqrt{2\pi}\ n^{n+1/2}\mathrm e^{-n} \le n! \le \mathrm e\ n^{n+1/2}\mathrm e^{-n}\;,$$
which for $k(n-k)\gt0$ yields
$$
\begin{align}
\binom nk
&=\frac{n!}{k!(n-k)!}
\\
&\le
\frac{\mathrm e\ n^{n+1/2}\mathrm e^{-n}}{\sqrt{2\pi}\ k^{k+1/2}\mathrm e^{-k}\sqrt{2\pi}\ (n-k)^{n-k+1/2}\mathrm e^{-(n-k)}}
\\
&=
\frac{\mathrm e}{2\pi}\sqrt{\frac{n}{k(n-k)}}\frac{n^n}{k^k(n-k)^{n-k}}
\\
&\le
\frac{n^n}{k^k(n-k)^{n-k}}\;.
\end{align}
$$
For $k(n-k)=0$, equality holds in your inequality if we interpret $0^0$ as $1$.
A: *

*Let $S_j^n:=\{A\subset [n],|A|=j\}$. Let $S'\subset S_k^{n-i}\times S_i^n$ which consists of pairs of disjoint subsets. The map 
$$\varphi\colon S'\to S_{i+k}^n,\varphi(A,B)=A\cup B$$
is onto, hence $|S'|\geq |S_{i+k}^n|=\binom n{i+k}$. Since $S'\subset S_k^{n-i}\times S_i^n$, its cardinal is smaller than the cardinal of the product, which gives the result. 

*We have to show that 
$$k^k(n-k)^{n-k}\binom nk\leq n^n.$$
The LHS is the number of maps from $[n]$ to $[n]$ such that there exists a susbet of $k$ element which is stable and its complement is also stable, and the RHS is the total number of maps from $[n]$ to $[n]$. 
A: The first, after writing down the factorials and some canceling becomes $$(i+k)! \geq i!k!$$  
The second works with induction. Show that the inequality is true with $n = k$ and then show that $$\binom{n+1}{k} = \binom{n}{k} * \frac{n+1}{n+1-k} \leq \frac{n^n}{k^k(n-k)^{n-k}} * \frac{n+1}{n+1-k} \leq \frac{(n+1)^{n+1}}{k^k(n+1-k)^{n+1-k}}$$
