## Log-Convexity of the Bell Numbers

A sequence $\{a_n\}$ is said to be log-convex if, for all $n \geq 1$, $a_n^2 \leq a_{n-1} a_{n+1}$.

In this post I give a short, combinatorial-flavored proof that the Bell numbers are log-convex.  The argument is from my answer here on Math.SE.

The combinatorial interpretation of the Bell number $B_n$ is that it counts the number of ways to partition the set $\{1, 2, \ldots, n\}$ into nonempty subsets.  Let $S_n$ denote the total number of sets over all partitions of $\{1, 2, \ldots, n\}$.  Then $A_n = S_n/B_n$ is the average number of sets in a random partition of $\{1, 2, \ldots, n\}$.

Claim 1: $A_n$ is increasing.

Proof: Each partition of $\{1, 2, \ldots, n+1\}$ can be associated with a partition of $\{1, 2, \ldots, n\}$ by removing the element n+1 from the set containing it.  Under the inverse of this mapping, each partition of $\{1, 2, \ldots, n\}$ consisting of k sets maps to k partitions consisting of k sets (if n+1 is placed in an already-existing set) and one partition consisting of k+1 sets (if n+1 is placed in a set by itself) out of the partitions of $\{1, 2, \ldots, n+1\}$.  Thus partitions of $\{1, 2, \ldots, n\}$ with more sets map to more partitions of $\{1, 2, \ldots, n+1\}$ containing the same number of sets as well as one partition with one more set.  This raises the average number of sets as you move from n elements to n+1 elements.

Claim 2: The log-convexity of $B_n$ is equivalent to the fact that $A_n$ is increasing.

Proof: Separate the partitions counted by $B_{n+1}$ into (1) those that have a set consisting of the single element n+1 and (2) those that don’t.  It should be clear that there are $B_n$ of the former.  Also, there are $S_n$ of the latter because each partition in group (2) is formed by adding n+1 to a set in a partition of $\{1, 2, \ldots, n\}$.  Thus $B_{n+1} = B_n + S_n$.

Therefore,

$\displaystyle B_n^2 \leq B_{n-1} B_{n+1} \iff \frac{B_{n+1}}{B_n} \geq \frac{B_n}{B_{n-1}} \iff 1 + \frac{S_n}{B_n} \geq 1 + \frac{S_{n-1}}{B_{n-1}}$ $\iff A_n \geq A_{n-1}.$

Since we established the last inequality in Claim 1, the Bell numbers are log-convex.

I was not the first to find this proof; Canfield [1] published it in 1995.  Engel [2] was the first to prove that the Bell numbers are log-convex; he used a different method.  See my answer here on Math.SE for references to more proofs.

References

1.  E. Rodney Canfield, “Engel’s Inequality for Bell Numbers,” Journal of Combinatorial Theory, Series A, 72 (1995) 184-187.

2. Konrad Engel, “On the Average Rank of an Element in a Filter of the Partition Lattice,” Journal of Combinatorial Theory, Series A, 65 (1994) 67-78.