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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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