# An Inequality Involving Bell Numbers: $B_n^2 \leq B_{n-1}B_{n+1}$

The following inequality came up while trying to resolve a conjecture about a certain class of partitions (the context is not particularly enlightening): $$B_n^2 \leq B_{n-1}B_{n+1}$$ for $n \geq 1$, where $B_n$ denotes the $n$th Bell number (i.e. the number of partitions of an $n$-element set). I ran this inequality through Maple for values of $n$ up to 500 or so and did not find a counterexample.

There is no nice closed form for $B_n$, so I was hoping to prove this inequality combinatorially rather than analytically (particularly since the given inequality is just the simplest version of a more general inequality I hope to establish).

Let $P_n$ be the collection of (not number of) all partitions of an $n$-element set. My approach was to find an injection from $P_n \times P_n$ into $P_{n-1} \times P_{n+1}$. Suppose we are to map $(C_1, D_1)$ to $(C_2, D_2)$ and suppose, for convenience, our ground set is the integers from $1$ to $n$.

A natural seeming choice was to choose $C_2$ to be the partition $C_1$ with the element $n$ removed. Since removing $n$ will map many partitions in $P_n$ to the same partition in $P_{n-1}$, we would need somehow to choose $D_2$ in such a way as to retain information about where $n$ was in $C_1$. We have the new element $n+1$ to work with, so perhaps it can be used to "tag" the partitions in some unique way.

I've stressed a combinatorial approach in this post, but I would greatly appreciate any techniques that might be of use in establishing (or refuting) this inequality.

-
A sequence $c_n$ satisfying $c_n^2 \le c_{n-1} c_{n+1}$ for all $n$ is called discrete log-convex, for what it's worth. –  Sasha Sep 27 '11 at 19:32

This answer is courtesy of Bouroubi (paraphrased):

Theorem. Define $B(x)=e^{-1}\sum_{k=0}^\infty k^x k!^{-1}$. Dobinski's formula states $B(n)=B_n$ is the $n$th Bell number. Now we let $\frac{1}{p}+\frac{1}{q}=1$. Then $$B(x+y)\le B(px)^{1/p}B(qx)^{1/q}.$$ Proof. Let $Z$ be the discrete random variable with density function (under counting measure) $$P(Z=k)=\frac{1}{e}\frac{1}{k!}.$$ Observe $\mathbb{E}(Z^x)=B(x)$. Hölder's inequality gives $\mathbb{E}(Z^{x+y})\le\mathbb{E}(Z^{px})^{1/p}\mathbb{E}(Z^{qx})^{1/q}$, which proves the theorem.

Corollary. The sequence $B_n$ is logarithmically convex, or equivalently $$B_n^2\le B_{n-1}B_{n+1}.$$ Proof. Set $x=\frac{n-1}{2}$, $y=\frac{n+1}{2}$, and $p=q=2$ in the original theorem.

Not a combinatorial proof, but straightforward given a couple powerful premises at least. I'm curious, what's the general formula you're trying to establish?

-
(+1) Very nice proof, and thanks for the reference. –  Sasha Sep 27 '11 at 19:44
"Probability mass function", or "probability density function with respect to counting measure", or just "probability distribution", would be a term less likely to be misunderstood than "probability distribution function", because of the convention of using that latter term to refer to the cumulative distibution function. –  Michael Hardy Sep 27 '11 at 20:18
@Michael: Right, right. I was going to change that term from the reference but spaced off. –  anon Sep 27 '11 at 20:24
I have a suspicion that finding an injection of the sort proposed in the question is possible, and I wonder wheter, in the case where $x$ and $y$ and $ps$ and $py$ are integers, the same thing could be done in order to prove the inequality $B(x+y)\le B(px)^{1/p}B(qx)^{1/q}$. –  Michael Hardy Sep 27 '11 at 20:24
@Michael: I'm still looking for an injection proof, but I'm unsure if the idea is powerful enough to prove that generalized inequality. –  anon Sep 27 '11 at 20:43

Here's a combinatorial argument. Let $S_n$ denote the total number of sets over all partitions of $\{1, 2, \ldots, n\}$, so that $A_n = \frac{S_n}{B_n}$ is the average number of sets in a partition of $\{1, 2, \ldots, n\}$.

First, $A_n$ is increasing. 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 with more sets reproduce more partitions of their size as well as one larger partition, raising the average number of sets as you move from $n$ elements to $n+1$ elements.

Next, the inequality to be proved is equivalent to the fact that $A_n$ is increasing. 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$.

The inequality to be shown can then be reformulated as $$\frac{B_{n+1}}{B_n} \geq \frac{B_n}{B_{n-1}} \Longleftrightarrow 1 + \frac{S_n}{B_n} \geq 1 + \frac{S_{n-1}}{B_{n-1}} \Longleftrightarrow A_n \geq A_{n-1},$$ and we know the last inequality holds because we've already shown that $A_n$ is increasing.

-

Some more references, which will give you some additional proofs if you're interested in tracking them down.

(Added: The Bender and Canfield paper mentioned below gives this bound as well.)

"The log-convexity of the Bell numbers was first obtained by 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] . Then Bender and Canfield ["Log-concavity and related properties of the cycle index polynomials," Journal of Combinatorial Theory Series A 74 (1996) 57-70] gave a proof by means of the exponential generating function of the Bell numbers. Another interesting proof is to use Dobinski formula [as in anon's answer]. We can also obtain the log-convexity of the Bell numbers by Proposition 2.3 and the well-known recurrence $$B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k."$$

Liu and Wang's proposition 2.3 (due to Davenport and Pólya) says

If $\{x_n\}$ is log-convex, and $z_n = \sum_{k=0}^n \binom{n}{k} x_k$, then $\{z_n\}$ is log-convex as well.

While at first this may seem circular when applied to the Bell numbers, it's not. Proposition 2.3 says that if $x_{k-1}x_{k+1} \geq x_k^2$ for $1 \leq k \leq n-1$ then $z_{k-1}z_{k+1} \geq z_k^2$ for $1 \leq k \leq n-1$. With the Bell number recurrence, then, we have $B_{k-1}B_{k+1} \geq B_k^2$ for $1 \leq k \leq n-1$ implying $B_{k}B_{k+2} \geq B_{k+1}^2$ for $1 \leq k \leq n-1$. Since we can easily check that $B_0 B_2 \geq B_1^2$, this gives us an inductive proof of the log-convexity of the Bell numbers.

• (Added 2) Canfield, in "Engel's inequality for Bell numbers" [Journal of Combinatorial Theory Series A 72 (1995) 184-187], discusses this inequality as well and gives the same proof as in my other answer.
-