# Log concavity of binomial coefficients: $\binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1}$

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

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

## 6 Answers

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.

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)!$

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

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

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

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.

• 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\})$. – munchhausen Aug 10 '18 at 19:31
• I've written a fix to your argument as an answer below. – munchhausen Aug 13 '18 at 15:40
• @munchhausen Thanks. (+1 to you.) – Michael E2 Apr 21 '19 at 18:10

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