4
$\begingroup$

How do we prove that Binomial coefficients are log-concave? A sequence $a_0, \dots, a_n$ is log-concave if $a_k^2 \geq a_{k-1}a_{k+1}$.

$$ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $$

If $ n >> k$ I suppose we get some estimates related to Poisson distribution : $\binom{n}{k} \approx \frac{n^k}{k!} $

$$ \left(\frac{n^k}{k!}\right)^2 \geq \frac{n^{k-1}}{(k-1)!} \frac{n^{k+1}}{(k+1)!} \hspace{0.25in}\text{ or }\hspace{0.25in} k!^2 \leq (k-1)!(k+1)!$$

In my homework, I have a product of 3 binomial coefficients and I want to know if I can replace them with the average:

$$ \binom{n}{\frac{a+b+c}{3}}^3 \geq \binom{n}{a}\binom{n}{b}\binom{n}{c} $$

$\endgroup$
  • 5
    $\begingroup$ In your initial inequality divide the left hand side by the right hand side and simplify. $\endgroup$ – WimC Jun 15 '14 at 12:06
11
$\begingroup$

Since $$ \binom nk = \left((n+1)\int_0^1 t^k (1-t)^{n-k}\,dt\right)^{-1} $$ (see beta function, and/or this question), the desired inequality is equivalent to $$ \left(\int_0^1 t^k (1-t)^{n-k} \,dt\right)^2 \le \left(\int_0^1 t^{k-1} (1-t)^{n-k+1} \,dt\right) \left(\int_0^1 t^{k+1} (1-t)^{n-k-1} \,dt\right) $$ which is an instance of Hölder's inequality.

$\endgroup$
3
$\begingroup$

Hint: Replace them with their factorial expressions, $\displaystyle{a\choose b}=\frac{a!}{b!(a-b)!}$ , and then use the basic

properties of the factorial function, such as $m!=m(m-1)!$

$\endgroup$
3
$\begingroup$

First part: Here is an argument with a slight combinatorial flavor: Rewrite the inequality as $$\frac{\binom{n}{k}}{\binom{n}{k-1}}\ge \frac{\binom{n}{k+1}}{\binom{n}{k}}\qquad \dots(A)$$ LHS is the ratio of number of $k$ sized subsets to the number of $k-1$ sized subsets. We ask 'in how many ways can we extend a $k-1$ sized subset of $[n]:=\{1,2,\dots ,n\}$ into a $k$ sized subset'? This can be done by including one more element which is not the part of the $k-1$ sized set, that is, in $n-(k-1)$ ways. Each $k-1$ sized set gives rise to $n-k+1$ subsets of size $k$. But, each subset of size $k$ is formed by extending $k$ different $k-1$ subsets. Hence the ratio of number of $k$ sized subsets to the number of $k-1$ sized subsets is $\frac{n-k+1}{k}$. Similar argument for RHS gives $\frac{n-k}{k+1}$

Now, $$\frac{n-k+1}{k}\ge \frac{n-k}{k+1} \qquad \dots (B)$$ is obvious. Note that we can obtain (B) from (A) by simplifying using the usual definition of $\binom{n}{r}$.

$\endgroup$
  • $\begingroup$ The argument only works when $n$ and $k$ are positive integers and $k+1\le n$. $\endgroup$ – talegari Jun 15 '14 at 18:32
2
$\begingroup$

Here's an injection argument which fixes the error made by @Michael. Consider a pair $(S,T)\in{[n]\choose k-1}\times{[n]\choose k+1}$. Define $S_i:=S\cap[i]$ and similarly define $T_i$. Now, consider the sequences $S_0,S_1,\dots,S_n$ and $T_0,T_1,\dots,T_n$. Since $|S_0|=|T_0|=0$, $|S_n|=k-1=|T_n|-2$, and each set increases by at most one in size at each step, there must be an index $I$ for which $|S_I|=|T_I|-1$ (if there are multiple, choose the smallest). Define $S'=T_I\cup(S\setminus S_I)$, $T'=S_I\cup(T\setminus T_I)$ and $f(S,T)=(S',T')$. Firstly, it is obvious that $|S'|=|T'|=k$ since, for example, $T_I\subseteq[I]$ while $S\setminus S_I\subseteq[I+1,n]$, so $|S'|=|T_I|+(|S|-|S_I|)=|S_I|+1+(k-1)-|S_I|=k$ (similarly for $T'$). Therefore, $f$ is, in fact, a map from ${[n]\choose k-1}\times{[n]\choose k+1}\to{[n]\choose k}^2$. The fact that $f$ is an injection follows quickly from the fact that you can recover the index $I$ and, from that, reconstruct $S$ and $T$.

$\endgroup$
0
$\begingroup$

A simple counting argument:

The left-hand side is the number of ways of choosing two $k$ subsets of the integers $\{1,\dots, n\}$ independently.

The right-hand side is the number of ways of choosing a $k-1$ subset and a $k+1$ subset independently. Such a choice can be converted into two $k$ subsets since the $k+1$ subset has at least two elements that are not members of the $k-1$ subset. If we choose to switch the least element of the $k+1$ subset that is not a member of the $k$ subset. This conversion, as a mapping, is one-to-one: the inverse conversion is to take, from such an ordered pair of $k$ subsets, in which the second set has at least one element not in the first set (and therefore vice versa), the least element of the first $k$ subset that is not a member of the second $k$ subset and put it (back) into the second.

This defines an injection of the product of $k-1$ subsets and $k+1$ subsets into the product of the $k$ subsets with itself. Hence inequality may be deduced.

$\endgroup$
  • $\begingroup$ This doesn't work. As an example, consider the pair $(\{1,2\},\{3,4\})$. This is the image of both $(\{1\},\{2,3,4\})$ and $(\{2\},\{1,3,4\})$. $\endgroup$ – munchhausen Aug 10 '18 at 19:31
  • $\begingroup$ I've written a fix to your argument as an answer below. $\endgroup$ – munchhausen Aug 13 '18 at 15:40
  • $\begingroup$ @munchhausen Thanks. (+1 to you.) $\endgroup$ – Michael E2 Apr 21 at 18:10
0
$\begingroup$

Following up Lucian's answer, start with the definition. We want to prove that

$$ A=\frac{{n\choose k}^2}{{n\choose k-1}{n\choose k+1}} \geq 1. $$

$$ A=\frac{(n!)^2}{((n-k)!)^2(k!)^2}\times\frac{(k-1)!(n-k+1)!}{n!} \times\frac{(k+1)!(n-k-1)!}{n!} $$

$$ =\frac{n-k+1}{n-k}\times\frac{k+1}{k}\geq 1, $$

which holds for $n\geq k+1$ and $k\geq 1$.

$\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.