Prove that, for all even integers n ≥ 2, $(n/2)^{n/2} \le r_n \le n^n$ where $r_n$ are the Bell numbers.
I know the Bell numbers are given by the following recurrence relation:
$B_{n+1} = \sum_{k=0}^n {n \choose k} \ast B_k$
So far I've tried to use an inductive proof, but after the initial step I'm not sure where to go with it. I also tried the reasoning of how the Bell numbers are directly related to the power set on $n$ which can only be as large as $2^n$, but the Bell numbers grow faster than this. The answer seems obvious to me, but I lack the tools to prove it myself.
Best Answer
$B_n$ is the number of equivalence elations on a set with $n$ elements. We can take the set to be $[n]=\{1,\dots,n\}$. Put each odd number in a separate equivalence class. Then for each of the $N/2$ even numbers, we have $n/2$ choices fo the class it belongs to, giving $\left(\frac{n}{2}\right)^{n/2}$ different equivalence relations.
On the other hand, imagine that we have $n$ distinct buckets, and we put each element in one of the buckets. There are $n^n$ ways to do this, and every equivalence relation corresponds to one or more such distributions, so there are fewer than $n^n$ equivalence relations.