Proving a tricky set of inequalities with double induction

Question

Here's what I need to prove:

$$\frac{n^k}{k^k} \le {n \choose k} \le \frac{n^k}{k!} $$

I figure this calls for a proof by induction. I feel like I have to do a proof by induction on both n and k. I started with a base case where both are 0. But the induction part is where I get stuck.

I started with assuming the statement held true for $n-1$ and I've so far reasoned that $${n \choose k}-{n-1 \choose k-1} \le \frac{(n-1)^k}{k!} \le \frac{n^k}{k!}$$ with pascal's identity, but I'm really stuck on how to get to the final inequality. With induction on k I'm completley lost!!

Answer 1

$$\binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!}\le\frac{n^k}{k!}$$

$$\binom{n}{k}=\frac{n}{k}\cdots\frac{n-k+1}{1}\ge\left(\frac{n}{k}\right)^k$$

(You still need to prove these smaller steps by induction:)

Answer 2

The upper bound is straight forward.

You can calculate the lower bound directly as follows:

Note that for $0 < k \leq n$ you have for $i = 0,\ldots , k-1$

• $1-\frac{i}{k} \leq 1-\frac{i}{n}$

It follows $$\prod_{i=0}^{k-1} \left( 1-\frac{i}{k}\right) \leq \prod_{i=0}^{k-1} \left( 1-\frac{i}{n}\right)$$ $$\Rightarrow \frac{1}{k^k}\underbrace{\prod_{i=0}^{k-1} \left( k-i \right) }_{=k!}\leq \frac{1}{n^k}\prod_{i=0}^{k-1} \left( n-i \right)$$ $$\Rightarrow \frac{n^k}{k^k} \leq \binom{n}{k}$$