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! 
 A: 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.
A: 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.
