Intereting Posts

Example of topological spaces with continuous bijections that are not homotopy equivalent
Does same cardinality imply a bijection?
proving the inequality $\triangle\leq \frac{1}{4}\sqrt{(a+b+c)\cdot abc}$
Burgers equation with initial data $u(x,0) = x^2$
Is Inner product continuous when one arg is fixed?
Any “natural” examples of true statements in number theory not provable in 2nd order systems?
Integration of $\dfrac{x}{\sinh x}~dx$ from $-\infty$ to $\infty$
Why are Quotient Rings called Quotient Rings?
Asymptotic behaviour of a multiple integral on the unit hypercube
There's no continuous injection from the unit circle to $\mathbb R$
Assumption that $\delta q'$ is small in the derivation of Euler-Lagrange equations.
Probability of $5$ fair coin flips having strictly more heads than $4$ fair coin flips
Very elementary proof of that Euler's totient function is multiplicative
Proving Cauchy's Generalized Mean Value Theorem
wildly ramified extensions and $p$-power roots of unity

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

- Multiplying three factorials with three binomials in polynomial identity
- finding the combinatorial sum
- Ferrers Diagram Partitions
- How to prove $ \sum_{k=0}^n \frac{(-1)^{n+k}{n+k\choose n-k}}{2k+1}=\frac{-2\cos\left(\frac{2(n-1)\pi}{3}\right)}{2n+1}$
- Mrs Reed safe combination
- How many distinct functions can be defined from set A to B?

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.

- Identical balls arrangement in a circle
- Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$
- Poincaré Inequality
- Solving permutation problem sequentially.
- Generalised inclusion-exclusion principle
- Combination Problem Understanding
- “8 Dice arranged as a Cube” Face-Sum Equals 14 Problem
- Shortest sequence containing all permutations
- Maximum integer not in $\{ ax+by : \gcd(a,b) = 1 \land a,b \ge 0 \}$
- Adding equations in Triangle Inequality Proof

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?

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 A65 (1994) 67-78] . Then Bender and Canfield [“Log-concavity and related properties of the cycle index polynomials,”Journal of Combinatorial Theory Series A74 (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*72 (1995) 184-187], discusses this inequality as well and gives the same proof as in my other answer.

Combinatorial Theory Series A

- complicated derivative with nested summations
- How to solve exact equations by integrating factors?
- How to calculate gradient of $x^TAx$
- What's the largest possible volume of a taco, and how do I make one that big?
- $f,\overline f$ are both analytic in a domain $\Omega$ then $f$ is constant?
- For all square matrices $A$ and $B$ of the same size, it is true that $(A+B)^2 = A^2 + 2AB + B^2$?
- Finding the coefficient using the multinomial theorem?
- What is the importance of Calculus in today's Mathematics?
- An inflection point where the second derivative doesn't exist?
- Determine whether $712! + 1$ is a prime number or not
- Self-Studying Abstract Algebra; Aye or Nay?
- Show that $(\mathbb{Z}/(x^{n+1}))^{\times}\cong \mathbb{Z}/2\mathbb{Z}\times\Pi_{i=1}^n\mathbb{Z}$
- How to exactly write down a proof formally (or how to bring the things I know together)?
- If $f$ is a strictly increasing function with $f(f(x))=x^2+2$, then $f(3)=?$
- Calculating Bernoulli Numbers from $\sum_{n=0}^\infty\frac{B_nx^n}{n!}=\frac x{e^x-1}$