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 2 of 4: Expand

n^n

via the Binomial Theorem to establish the upper bound

Previous step Next step

In plain words

A single term in a sum of positive numbers is always smaller than the whole sum.

n^n = ((n-k) + k)^n = \sum_{i=0}^{n} \binom{n}{i} (n-k)^{n-i} k^i = \sum_{i=0}^{n} T_{i+1} > T_{k+1}

Detailed analysis

By the Binomial Theorem, $n^n = ((n-k) + k)^n = \sum_{i=0}^{n} T_{i+1}$ , where $T_{i+1} = \binom{n}{i} (n-k)^{n-i} k^i$ for $0 \le i \le n$ . Because $n > k \ge 1$ , every term $T_{i+1}$ is strictly positive and there are $n + 1 \ge 3$ terms in the sum. In particular, the single term $T_{k+1} = \binom{n}{k} k^k (n-k)^{n-k}$ is strictly less than the entire sum $n^n$ , which proves the right-hand inequality.