How do you prove ${n \choose k}$ is maximum when $k$ is $ \lceil \tfrac n2 \rceil$ or $ \lfloor \tfrac n2\rfloor $?

How do you prove $n \choose k$ is maximum when $k$ is $\lceil n/2 \rceil$ or $\lfloor n/2 \rfloor$?

This link provides a proof of sorts but it is not satisfying. From what I understand, it focuses on product pairings present in $k! (n-k)!$ term which are of the form $i \times (i-1)$. Since these are minimized when $i=n/2$, we get the result. But what about the reasoning for the rest of the terms?

Solution 1:

HINT:

As $\displaystyle \binom nk>0$ for $0\le k\le n$ where $n>0,k$ are integers

Check for $k$ such that $$\frac{\binom n{k+1}}{\binom nk}=\frac{n-k}{k+1}>=<1$$

Solution 2:

I have done this proof in Metamath before; it may help to see the whole thing laid out.

The proof follows from the fact that the binomial coefficient is monotone in the second argument, i.e. ${n\choose k'}\le{n\choose k''}$ when $0\le k'\le k''\le\lceil\frac n2\rceil$, which can be proven by induction. Given this, you just set $k''=\lceil\frac n2\rceil$ and $k'=k$ or $k'=n-k$ depending on whether $k\le\frac n2$, and you get ${n\choose k}={n\choose n-k}\le{n\choose \lceil n/2\rceil}={n\choose \lfloor n/2\rfloor}$ (where the equalities are deduced by symmetry of the binomial coefficient under $k\mapsto n-k$).

To prove monotonicity, we prove ${n\choose k-1}\le{n\choose k}$ for $1\le k\le\lceil\frac n2\rceil$, and thus ${n\choose k}\le{n\choose k+1}\le\dots\le{n\choose l}$ for any $k\le l$ in the range. Now we have:

$${n\choose k-1}=\frac{n!}{(k-1)!(n-k+1)!}=\frac{n!}{k!(n-k)!}\frac{k}{n-k+1}={n\choose k}\frac{k}{n-k+1},$$

so ${n\choose k-1}\le{n\choose k}$ iff $\frac{k}{n-k+1}\le 1$. But that is equivalent to $$k\le n-k+1\iff 2k\le n+1\iff k\le \frac{n+1}2\iff k\le \left\lceil\frac{n}2\right\rceil,$$

and we are done.

Solution 3:

Here's a combinatorial proof, by counting pairs of subsets contained in one another:

Any $k$-element subset is contained in $n-k$ different $(k+1)$-element subsets, whereas each $(k+1)$-element subset contains exactly $(k+1)$ different $k$-element subsets. So provided that $n-k > k+1$ we have that $\binom nk < \binom n{k+1}$, and an inequality the other direction in the other case. The fact that the maximum is in the middle follows immediately.

Solution 4:

The second identity here gives $$\binom{n}{k}-\binom{n}{k-1}=\frac{n+1-2k}{n+1} \binom{n+1}{k}. $$ Thus the sequence of binomial coefficients $\binom{n}{k}$, with $n$ fixed, is increasing as long as $2k \leq n+1$ or $$k \leq \left\lfloor \frac{n+1}{2} \right\rfloor, $$ and is decreasing for all values of $k$ satisfying $2k \geq n+1$ or $$k \geq \left\lceil \frac{n+1}{2} \right\rceil.$$

Solution 5:

There is a general trick for functions with symmetry which can be used here if you allow for non-integer continuation of the factorial function (which one should I think). Let us denote:

$\binom{n}{k} = F_{n}(k)$.

The binomial identity give us:

$ F_{n}(k) = F_{n}(n-k)$.

Taking the derivative of both sides gives:

$F'_{n}(k)=-F'_{n}(n-k)$.

Now assuming that only one extrema exists at $k = \bar{k}$ then $F'(\bar{k}) = 0$. We then have:

$F'(n-\bar{k}) = 0 \rightarrow \bar{k} = (n-\bar{k})$

Giving, $\bar{k} = n/2$. Translating to integers this gives the floor and ceil of (n/2) as the solutions.

Of course I had to assume there was only extrema of the binomial coefficient. One can see this by graphing the binomial coefficient but here is a sketchy outline of how it can be done with these functions.

From the requirements, $F_{n}(0) = F_{n} (n) = 1$ and $F_{n}(k)>1$, we know that the number of extrema must be odd. From the binomial identity,

$F_{n}(k+1) = \frac{n-k}{k+1} F_{n}(k)$,

one can show that the derivative an integer step to the left/right of the extremal point is positive/negative. This shows that the only extremal points allowed are concave. Since one can't have more than one extrema without having convex extrema, we conclude that there is only one extrema.