$s_n=s_{n-1}+(n-1)s_{n-2}$ prove $s_n>\sqrt{n!n}$ for $n\ge4$ Define sequece as follows: $s_1=1,~s_2=2, s_n=s_{n-1}+(n-1)s_{n-2}$. I want to prove that $s_n>\sqrt{n!n}$ for $n\ge4$. I'd tried to use traditional induction on $n$, but it involves both two terms that are in front of the current term. Should I use strong induction? Or even should I solve such sequence first? (I'm not good at transform the recurrence relation to explicit formula)
 A: Let's try an induction : 
You have $s_1 = 1$ and $s_2 = 2$, so $s_3 = 4$ and $s_4 = 10$ and $s_5 = 26$.
Therefore, you have $s_4 = 10 = \sqrt{100} > \sqrt{96} = \sqrt{4! \times 4}$. And $s_5 = 26 = \sqrt{676} > \sqrt{600} = \sqrt{5! \times 5}$.
Now, let's suppose your result is true for two successive ranks $n$ and $n+1$, that is you have $s_n > \sqrt{n! n}$ and $s_{n+1} > \sqrt{(n+1)!(n+1)}$. You have then 
$$s_{n+2} = s_{n+1} + (n+1)s_n$$
so
$$s_{n+2}^2 = s_{n+1}^2 + (n+1)^2s_n^2 + 2 (n+1)s_{n+1}s_n$$
so you get
$$s_{n+2}^2 > (n+1)!(n+1) + (n+1)^2n! n + 2(n+1) \sqrt{(n+1)!(n+1)n!n}$$
$$=(n+1)!(n+1)^2 + 2(n+1)!(n+1)\sqrt{n}$$
$$=(n+1)!((n+1)^2 + 2(n+1)\sqrt{n})$$
Now $n \geq 4$, so $\sqrt{n} \geq 2$, so you get 
$$s_{n+2}^2 > (n+1)!((n+1)^2 + 4(n+1)) = (n+1)!((n+2)^2 + 2n +1)$$ $$> (n+1)!(n+2)^2 = (n+2)!(n+2)$$
Therefore you have 
$$s_{n+2} > \sqrt{(n+2)!(n+2)}$$
which is your equality at the rank $n+2$. This completes your proof.
A: Let us consider the exponential generating function of our sequence:
$$ f(x)=\sum_{n\geq 1}\frac{s_n}{n!} x^n = x+x^2+\frac{2}{3}x^3+\ldots$$
we have:
$$ f'(x) = \sum_{n\geq 0}\frac{s_{n+1}}{n!} x^{n},\qquad x\,f'(x)=\sum_{n\geq 1}\frac{n\,s_n}{n!}x^n $$
$$ f''(x)=\sum_{n\geq 0}\frac{s_{n+2}}{n!}x^n,\qquad x\,f'(x)+f(x)=\sum_{n\geq 1}\frac{(n+1)s_n}{n!}x^n $$
and the recursion
$$ s_{n+2}=s_{n+1}+(n+1)s_n $$
can be written as
$$ f''(x)-2 = (f'(x)-1)+x\,f'(x)+f(x), $$
$$ f(0)=0,\, f'(0)=1,$$
leading to
$$ f(x) = -1+e^{x+\frac{x^2}{2}}. \tag{1}$$
Since $e^{x}=\sum_{m\geq 0}\frac{x^m}{m!}$ and $e^{x^2/2}=\sum_{n\geq 0}\frac{x^{2n}}{2^n n!}$ for any $N\geq 1$ we have
$$ s_N = f^{(N)}(0) = N!\sum_{k=0}^{\lfloor N/2\rfloor}\frac{1}{2^k k!(N-2k)!}=\sum_{k=0}^{\lfloor N/2\rfloor}\frac{(2k)!}{(2k)!!}\binom{N}{2k}\tag{2}$$
i.e. our sequence is OEIS-A85, related to the number of involutions in $S_n$.
As recalled here, Hayman's method gives that the asymptotic behaviour of $s_N$ is
$$ s_N \sim \frac{N^{N/2}}{\sqrt{2}}\,\exp\left[\sqrt{N}-\frac{N}{2}-\frac{1}{4}\right]. \tag{3}$$
Coupling $(3)$ with Stirling's double inequality
$$ \left(\frac{N}{e}\right)^N\sqrt{2\pi N}\,e^{\frac{1}{12N+1}}\leq N!\leq\left(\frac{N}{e}\right)^N\sqrt{2\pi N}\,e^{\frac{1}{12N}}\tag{4}$$
proves the claim.
