I have a sequence defined by $h_0=h_1=1$, $h_2=2$ and $h_{n+1}=(n+1)h_n + \frac{n(n-1)}{2}$. The paper I'm reading claims $n! \le h_n \le 2(n!)$. It is easy to show the first inequality by induction. $$h_{n+1} = (n+1)h_n + \frac{n(n-1)}{2} \ge (n+1)! + \frac{n(n-1)}{2} \ge (n+1)!$$
However, I am having trouble with the other one. Doing the same technique doesn't quite work: $$h_{n+1}=(n+1)h_n + \frac{n(n-1)}{2} \le 2(n+1)!+\frac{n(n-1)}{2}.$$ Am I missing something? Thanks in advance!
Set $$\frac{h_n}{n!} = t_n$$
We get
$$t_{n+1} = t_n + \frac{n(n-1)}{2(n+1)!}$$
Thus (adding up the telescopic series $t_{r} - t_{r-1}$) we get
$$t_n = 1 + \sum_{k=0}^{n-1} \frac{k(k-1)}{2(k+1)!}$$
Now $\lim_{n\to \infty} \sum_{k=0}^{n-1} \frac{k(k-1)}{2(k+1)!} = \frac{1}{2}(e-2)$ (easily found using taylor series for $e^x$)
And thus $$1 \lt t_n \lt \frac{1}{2}(e-2) \lt 2$$