Proving If $k \le \left\lfloor \frac{n}{2} \right\rfloor$ then $\binom{n}{k-1} < \binom{n}{k}$

So I'm trying to do a proof for this problem:

If $$\displaystyle{k \le \left\lfloor \frac{n}{2} \right\rfloor}$$ then $$\displaystyle{\binom{n}{k-1} < \binom{n}{k}}$$

I can do it algebraically but my professor asked for a combinatorial proof. How would one does it?

• The binomial distribution is unimodal. – Jack D'Aurizio Oct 11 '18 at 18:45
• Suppose you're choosing $k$ of $n$ items. Now, each such $k$-tuple can be included in some $k+1$-tuple when you try to choose $k+1$ items instead. Can you comment on how many of these $k+1$ tuples derived from the existing $k$ tuples can be distinct when $k>\lfloor\frac{n}{2}\rfloor$ and vice versa? – Boshu Oct 11 '18 at 19:24
• @JackD'Aurizio Can you explain more on that please? How would I use the fact that the binomial distribution is unimodal in the proof? – Itsnhantransitive Oct 12 '18 at 4:01
• @Itsnhantransitive: since there is a unique mode the function $f(k)=\binom{n}{k}=\frac{\Gamma(n+1)}{\Gamma(k+1)\Gamma(n-k+1)}$ has to be increasing on $[0,n/2]$ and decreasing on $[n/2,n]$. You may also exploit the fact that the $\Gamma$ function is log-convex to reach the same conclusion. – Jack D'Aurizio Oct 12 '18 at 18:56

3 Answers

Suppose we have $$n+1$$ items. The last item is special.

We can think of $$\binom{n}{k-1}$$ as counting the number of ways to pick $$k-1$$ items out of the first $$n$$. This is the same as the number of ways to pick $$k$$ items out of $$n+1$$ in a way that includes the last item.

We can think of $$\binom nk$$ as counting the number of ways to pick $$k$$ items out of the first $$n$$. This is the same as the number of ways to pick $$k$$ items out of $$n+1$$ in a way that does not include the last item.

Since $$k \le \lfloor \frac n2 \rfloor$$, we have $$k < \frac{n+1}{2}$$, so we are picking fewer than half of the $$n+1$$ items. This means we should include the special, last item less than half the time: so $$\binom{n}{k-1}$$ (which counts the cases when we include it) should be less than $$\binom{n}{k}$$ (which counts the cases when we don't).

• Brilliant proof. Thank you! – Itsnhantransitive Oct 14 '18 at 3:59

Let $$A$$ be a set of all $$k-1$$ subsets and $$B$$ be a set of all $$k$$ subsets in $$\{1,2,3,...n\}$$. Make a bipartite graph with partitions $$A$$ and $$B$$: $$a\in A,b\in B:\;\;a\sim b\iff a\subset b$$

Then the degree of each $$a$$ is $$n-k+1$$and the degree of each $$b$$ is $$k$$. Since we have $$\sum _{a\in A}d(a) = \sum _{b\in B}d(b)$$ we have also $$|A|\cdot (n-k+1) = |B|\cdot k$$

so $$1<{|B|\over |A|} = {n-k+1\over k} \iff k\leq {n\over 2}$$

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