Can you help with this proof that the $n$-th Bell number is bounded by $n!$ for all natural numbers $n$?

Question

I am trying to prove that an upper bound for the nth Bell number is n factorial. I am trying to do this by induction. Firstly, the nth Bell number is given by:

$B_{n}=\sum\limits^{n-1}_{k=0} B_{k}{n-1\choose k}$, for $n \geq 2$ and $B_{0}=B_{1}=1$.

My proof is as follows:

Let the statement $S(n)$ be $B_{n}=\sum\limits^{n-1}_{k=0} B_{k}{n-1\choose k} \leq n!$. (*)

Clearly $S(2)$ is true.

Assume $S(n)$ true for some $n>2$.

RTP: $S(n+1)$ true, i.e. $B_{n+1}=\sum\limits^{n}_{k=0} B_{k}{n\choose k} \leq (n+1)!$

I tried multiplying both sides of (*) by $n+1$, so we get $(n+1)!$ on the RHS as needed, but then it is not clear that we get $\sum\limits^{n}_{k=0} B_{k}{n\choose k}$ on the LHS.

Can anyone help me to complete this proof? I tried using different forms of the Bell number as well - like using Dobinski's formula. I also got nowhere.

Thanks!

Answer 1

Assume $$B_{n}=\sum\limits^{n-1}_{k=0} B_{k}{n-1\choose k} \leq n!\,.$$ Then $$ \begin{align*} B_{n+1}&=\sum^{n}_{k=0} B_{k}{n\choose k}\\ &=\sum_{k=0}^{n-1}B_k\frac{n}{n-k}\binom{n-1}k+B_n\\ &\leq n\cdot\sum_{k=0}^{n-1}B_k\binom{n-1}k+B_n\\ &=(n+1)\cdot B_n\\ &\leq(n+1)!\,. \end{align*} $$

---

Hope this helps.

Answer 2

Since $B_n$ is the number of partitions of the set $[n]=\{1,2,3,\dots,n\}$ while $n!$ is the number of linear orderings of $[n]$, we can prove the inequality $B_n\le n!$ by exhibiting an injection from the set of partitions to the set of orderings.

Let $P=\{X_1,X_2,\dots,X_k\}$ be a partition of $[n]$, indexed so that $\min X_i\lt\min X_j$ when $i\lt j$. Map $P$ to the ordering of $[n]$ in which all elements of $X_i$ precede all elements of $X_j$ when $i\lt j$, and the elements within each set $X_i$ are arranged in the opposite of their natural order. For instance, $$\{\{1,7,8,9\},\{2,4,6\},\{3\},\{5\}\}\mapsto(9,8,7,1,6,4,2,3,5).$$ It is easy to see that this is an injection.

As a variation of this argument, the cycle decomposition of a permutation suggests an obvious surjection from the symmetric group $S_n$ to the set of all partitions of $[n]$.

Alternatively, there is an easy proof by induction based on the inequality $B_n\le nB_{n-1}$.
The inequality follows from the observation that any partition of $[n]$ can be obtained from some partition of $[n-1]$ by either adding the new element to one of the existing equivalence classes (of which there are at most $n-1$) or starting a new class.