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 3 of 4: Compare consecutive terms to show

T_{k+1}

is the maximum term

Previous step Next step

In plain words

As $i$ grows, the factor $\binom{n}{i}$ trades $(n-i+1)$ for $i$ while $(n-k)^{n-i} k^i$ trades $(n-k)$ for $k$ ; the tipping point occurs precisely when $\frac{i}{n-i+1}$ crosses $\frac{k}{n-k}$ , which is right after $i = k$ .

\frac{T_{i+1}}{T_i} = \frac{\binom{n}{i}(n-k)^{n-i}k^i}{\binom{n}{i-1}(n-k)^{n-i+1}k^{i-1}} = \frac{(n-i+1)k}{i(n-k)}, \qquad \frac{T_{i+1}}{T_i} > 1 \iff i \le k

Detailed analysis

For $1 \le i \le n$ , the ratio of consecutive terms is $\frac{T_{i+1}}{T_i} = \frac{(n-i+1)k}{i(n-k)}$ . Therefore $\frac{T_{i+1}}{T_i} > 1 \iff (n-i+1)k > i(n-k) \iff (n+1)k > in \iff i < k + \frac{k}{n}$ . Since $0 < \frac{k}{n} < 1$ and $i$ is an integer, $i < k + \frac{k}{n}$ is equivalent to $i \le k$ (and equality $\frac{T_{i+1}}{T_i} = 1$ never occurs). Thus $T_1 < T_2 < \cdots < T_{k+1} > T_{k+2} > \cdots > T_{n+1}$ .