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 4 of 4: Bound the maximum term below by the average of all n + 1 terms

Previous step Next step

In plain words

The largest of $n + 1$ numbers that are not all equal is always strictly greater than their average.

T_{k+1} = \max_{1 \le j \le n+1} T_j > \frac{1}{n+1} \sum_{j=1}^{n+1} T_j = \frac{n^n}{n+1}

Detailed analysis

Since $T_{k+1} = \binom{n}{k} k^k (n-k)^{n-k}$ is strictly greater than every other term among the $n + 1$ terms $T_1, T_2, \ldots, T_{n+1}$ , we have $(n+1) T_{k+1} > \sum_{j=1}^{n+1} T_j = n^n$ . Dividing by $n + 1$ gives $\binom{n}{k} k^k (n-k)^{n-k} > \frac{n^n}{n+1}$ , establishing the left-hand inequality and completing the proof.