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

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!

• Maybe start from the definition of the Bell numbers as the number of partitions of an $n$-element set? Apr 9 '20 at 9:19
• There is a tremendous amount of information about the Bell numbers at oeis.org/A000110 including "$a(n)$ is the number of permutations on $[n]$ in which a 3-2-1 (scattered) pattern occurs only as part of a 3-2-4-1 pattern. Example: $a(3) = 5$ counts all permutations on $[3]$ except $321$." Apr 9 '20 at 9:33

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.

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.