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

Question

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?

Answer 1

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.

Answer 2

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$$

Answer 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.

Answer 4

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.

Answer 5

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.$$

Answer 6

We can write $$\binom{n}k =\frac{n!}{(n-k)! k!}=\frac{\Gamma(n+1)}{\Gamma(n-k+1)\Gamma(k+1)},$$ where $\Gamma$ is the Gamma-function.

I will prove something slightly different, but related to the question, namely that, in the above sense, we have $$\binom{n}{\frac n2}\ge \binom{n}k$$ for all $k\in[0,n]$. and $n\in[1,\infty[$.

For this note that we only need to prove $$\Gamma(n-k+1)\Gamma(k+1)\ge\Gamma(n/2+1)^2.$$ After taking logarithms, this is just $$\frac12\left(\ln(\Gamma(n-k+1))+\ln(\Gamma(k+1))\right)\ge\ln(\Gamma(n/2+1)),$$ which follows immediately from log-convexity of $\Gamma$.