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.

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(qy)^{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^{qy})^{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?

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.

• Asai, Kubo, and Kuo ["Bell numbers, log-concavity, and log-convexity," Acta Applicandae Mathematicae 63 (2000) 79-87] give an upper bound as well as the lower one:

  $$1 \leq \frac{B_{n+1}B_{n-1}}{B_n^2} \leq 1 + \frac{1}{n}.$$

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

• Liu and Wang ["On the log-convexity of combinatorial sequences," Advances in Applied Mathematics 39 (2007) 453-476] state

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