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.

  • 5
    $\begingroup$ 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. $\endgroup$
    – Sasha
    Sep 27, 2011 at 19:32

3 Answers 3


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?

  • $\begingroup$ "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. $\endgroup$ Sep 27, 2011 at 20:18
  • $\begingroup$ @Michael: Right, right. I was going to change that term from the reference but spaced off. $\endgroup$
    – anon
    Sep 27, 2011 at 20:24
  • $\begingroup$ 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}$. $\endgroup$ Sep 27, 2011 at 20:24
  • $\begingroup$ @Michael: I'm still looking for an injection proof, but I'm unsure if the idea is powerful enough to prove that generalized inequality. $\endgroup$
    – anon
    Sep 27, 2011 at 20:43
  • $\begingroup$ @anon I would still be interested to see an injective proof, but I think the reference you provided may serve my purposes. Thank you. $\endgroup$ Sep 28, 2011 at 1:19

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.

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.