How to prove that $B(n) < n!$ for all $n \geq 3$ where $B(n)$ is $n$-th Bell number

Question

When I approached this problem I thought that it can be easily solved by applying induction. However something went completely wrong and I haven’t managed to prove it by induction.

Maybe there is some different way to approach this problem? Any kind of help will be much appreciated

Answer 1

This inequality just says that there more permutations than partitions of the set $[n]=\{1,\ldots,n\}.$

Every permutation of $[n]$ has cycles. Every cycle is a permutation of some subset of $[n].$ Those subsets are disjoint, so they form a partition of $[n].$ But this mapping from permutations to partitions is not one-to-one. For example: $$ \begin{array}{ccc} \text{permutation} & & \text{partition} \\[8pt] \hline \left[ \begin{array}{ccc} 1 & \to & 2 \\ \uparrow & \swarrow \\ 4 & & 3 \end{array} \right] & \mapsto & \Big\{ \{1,2,4,\},\,\,\, \{3\} \Big\} \\[12pt] \left[ \begin{array}{ccc} 1 & \leftarrow & 2 \\ \downarrow & \nearrow \\ 4 & & 3 \end{array} \right] & \mapsto & \Big\{ \{1,2,4\},\,\,\, \{3\}\Big\} \end{array} $$ Different permutations can be mapped to the same partition.

So there are more permutations than partitions.

Answer 2

OP's supposed attempt in proving this confused me, and the only proof by induction that came into mind uses the recurrence relation $$B_{n+1}=\sum_{k=0}^n \binom nkB_k$$

We need strong induction, and $B_1=1!, B_2 = 2!$. The base case $n=3$ is trivial.

The induction step goes as follows:

$$B_{n+1}=\sum_{k=0}^n \binom nkB_k\le\sum_{k=0}^n \frac {n!}{(n-k)!k!}k!< \sum_{k=0}^n n!=(n+1)!$$

Answer 3

At least for large values of $n$, you could use $$\frac{\ln B_n}{n} \sim \ln n - \ln \ln n - 1 $$ while $$\frac{\ln n!}{n} \sim \ln n-1 $$ and $ln ln 3 =0.094$