<s>[INST] $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)
 [/INST] 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.
</s>