TAOCP 1.2.6 Exercise 7

Exercise 7. [12] If $n$ is a fixed positive integer, what value of $k$ makes $\binom{n}{k}$ a maximum?

Verified: yes
Solve time: 37s

Solution

By Eq. (5),

$$ \binom{n}{k}=\frac{n!}{k!(n-k)!}, \qquad 0\le k\le n. $$

To determine where this quantity is maximal, compare consecutive terms. For $0\le k<n$,

$$ \frac{\binom{n}{k+1}}{\binom{n}{k}} = \frac{n!}{(k+1)!(n-k-1)!} \frac{k!(n-k)!}{n!} = \frac{n-k}{k+1}. $$

Hence

$$ \binom{n}{k+1}>\binom{n}{k} \iff \frac{n-k}{k+1}>1 \iff n-k>k+1 \iff n>2k+1, $$

and

$$ \binom{n}{k+1}=\binom{n}{k} \iff n=2k+1. $$

Therefore the sequence

$$ \binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n} $$

strictly increases while $2k+1<n$, and strictly decreases while $2k+1>n$.

If $n=2m$ is even, then

$$ 2k+1<n \iff k\le m-1, $$

so the sequence increases up to $k=m$ and decreases afterward. Hence the unique maximum occurs at

$$ k=m=\frac n2. $$

If $n=2m+1$ is odd, then

$$ 2k+1<n \iff k\le m-1, $$

and equality occurs when $k=m$:

$$ \binom{n}{m+1}=\binom{n}{m}. $$

Thus the sequence increases up to $k=m$, then remains equal for one step, then decreases. The maximum occurs at the two values

$$ k=m,\qquad k=m+1. $$

By Eq. (6), these two values are symmetric:

$$ \binom{2m+1}{m}=\binom{2m+1}{m+1}. $$

Consequently, the maximum value of $\binom{n}{k}$ occurs when $k$ is nearest to $n/2$:

$$ \boxed{ \begin{cases} k=\dfrac n2, & n \text{ even},\[1.2ex] k=\dfrac{n-1}{2}\text{ and }k=\dfrac{n+1}{2}, & n \text{ odd}. \end{cases} } $$