How to prove that $B(n) < n!$ for all $n \geq 3$ where $B(n)$ is $n$-th Bell number 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
 A: 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.
A: 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)!$$
A: 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$
