$s_n=s_{n-1}+(n-1)s_{n-2}$ prove $s_n>\sqrt{n!n}$ for $n\ge4$

Question

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)

Answer 1

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.

Answer 2

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.