3
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ The binomial distribution is unimodal. $\endgroup$
    – Jack D'Aurizio
    Commented Oct 11, 2018 at 18:45
  • 1
    $\begingroup$ 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? $\endgroup$
    – Boshu
    Commented Oct 11, 2018 at 19:24
  • $\begingroup$ @JackD'Aurizio Can you explain more on that please? How would I use the fact that the binomial distribution is unimodal in the proof? $\endgroup$
    – Itsnhantransitive
    Commented Oct 12, 2018 at 4:01
  • $\begingroup$ @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. $\endgroup$
    – Jack D'Aurizio
    Commented Oct 12, 2018 at 18:56

3 Answers 3

Reset to default
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Brilliant proof. Thank you! $\endgroup$
    – Itsnhantransitive
    Commented Oct 14, 2018 at 3:59
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .