2
$\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$
  • 1
    $\begingroup$ The binomial distribution is unimodal. $\endgroup$ – Jack D'Aurizio Oct 11 '18 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 Oct 11 '18 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 Oct 12 '18 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 Oct 12 '18 at 18:56
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$
  • $\begingroup$ Brilliant proof. Thank you! $\endgroup$ – Itsnhantransitive Oct 14 '18 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.