Problem 4

Let

n, k

be given positive integers with

n > k

. Prove that

\frac{1}{n+1} \cdot \frac{n^n}{k^k (n-k)^{n-k}} < \frac{n!}{k!(n-k)!} < \frac{n^n}{k^k (n-k)^{n-k}}

Step 1 of 4: Multiply by

k^k (n-k)^{n-k}

to isolate the binomial term

Previous step Next step

In plain words

Moving $k^k (n-k)^{n-k}$ next to $\binom{n}{k}$ immediately reveals a single term of the binomial expansion of $((n-k) + k)^n = n^n$ .

\frac{n^n}{n+1} < \binom{n}{k} k^k (n-k)^{n-k} < n^n

Detailed analysis

Since $k \ge 1$ and $n - k \ge 1$ , the quantity $k^k (n-k)^{n-k}$ is positive. Multiplying the given double inequality by $k^k (n-k)^{n-k}$ and writing $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ shows that it is equivalent to $\frac{n^n}{n+1} < \binom{n}{k} k^k (n-k)^{n-k} < n^n$ .