Proving that for $n \equiv 0 \pmod{2}$, we get ${n \choose 0} < {n \choose 1} <\ldots< {n \choose n/2-1}<{n\choose n/2}$ etc.

Question

How can one prove that for $n \equiv 0$ mod $2$ we have

$${n \choose 0} < {n \choose 1} <\ldots< {n \choose n/2-1}<{n \choose n/2}>{n\choose n/2+1}>\ldots>{n\choose n-1}>{n\choose n}\,?$$

Can I say that for fixed $n$, the binomial coefficients $n \choose k$ increase with $k$ for $k < n/2$? If n is even (like in our case), then the central binomial coefficient $n \choose n/2$ is the largest one.

So $n \choose k+1$ is greater than, equal to, or less than $n \choose k$ according as $n-k$ is greater than, equal to, or less than $k+1$, that is according as $k$ is less than, equal to, or greater than $(n−1)/2$.

Is that correct?

Answer 1

All you need is this:

Lemma: $${n\choose k-1}<{n\choose k} \iff k\leq {n\over 2}$$

Proof: You can ask yourself:

In how many ways can we choose $k$ people, including one president, from a population of $n$ people?

First answer:

You choose $k-1$ people from $n$ people and then from the rest of them a president, so we have $${n\choose k-1}\cdot {n-k+1\choose 1}$$

Second answer:

You choose $k$ people from $n$ people and then from these selected you choose a president, so we have $${n\choose k}\cdot {k\choose 1}$$

So we have:$${n\choose k-1}\cdot (n-k+1)=k{n\choose k} $$ and from here we get $${n\choose k-1}<{n\choose k} \iff k\leq {n\over 2}$$

Answer 2

Let $n=2m$. You want to prove, that for

1. $0 \leq k<m$ we have ${{n}\choose{k}} < {{n}\choose{k+1}}$
2. $m\leq k< n$ we have ${{n}\choose{k}} > {{n}\choose{k+1}}$

First 1.: Let $0 \leq k<m$. Let's study the ratio

$$\frac{{{n}\choose{k+1}}}{{{n}\choose{k}}} = \frac{\frac{n!}{(k+1)!(n-(k+1))!)}}{\frac{n!}{k!(n-k)!}} = \frac{k!(n-k)!}{(k+1)!(n-k-1)!} = \frac{n-k}{k+1} > 1$$ since $n-k > n - m = n- \frac{n}{2} = \frac{n}{2} = m \geq k+1$.

Then 2.: Assume $m\leq k< n$. It goes similarly, the ratio $$\frac{{{n}\choose{k}}}{{{n}\choose{k+1}}} = \frac{k+1}{n-k} > 1 $$ because now $n-k \leq n-m = m < k+1 $.

Answer 3

Let's try using induction on $m$ where $n=2m$. For $m=0$, there is nothing to be proven, for $m=1$, then ${2\choose 0} = {2\choose 2} = 1 < 2 = {2\choose 1}$.

To get the induction step, observe that ${n+2\choose k} = {n+1\choose k-1} + {n+1 \choose k} = {n\choose k-2} + 2 {n\choose k-1} + {n\choose k}$. Suppose that $k<m+1 = \frac{n+2}{2}$, then \begin{align*} {2(m+1)\choose k} - {2(m+1)\choose k+1} &= {2m \choose k-2}+{2m\choose k-1}-{2m \choose k}-{2m\choose k+1}\\ &= \left[ {2m \choose k-2} - {2m \choose k} \right] + \left[ {2m\choose k-1} -{2m\choose k+1}\right] \end{align*} The first term is directly strictly negative by induction, the second term is too if $k<m$, if $k=m$ then ${2m\choose m-1}={2m\choose m+1}$ and the second term is $0$. This proves that ${2n+2\choose k}<{2n+2\choose k+1}$. The same can be done when $k>m+1$ to obtain ${2n+2\choose k}<{2n+2\choose k-1}$.