Finding limit involving a recursively defined sequence I have the following recursive sequence:
$$
S(n) = 1 + S(n-1) + \frac{2S(n-2)}n\\S(1) = 1\\S(0) = 0
$$
I've written a program that computes elements of $S(n)$ and seems to imply that:
$$
\lim_{n\to\infty} \frac{S(n) - S(n-1)}n = \frac{1 - e^{-2}}2
$$
I don't believe there is a closed form for $S(n)$ (bonus points if there is!), but I'm curious if there is some way to prove that the above limit is correct.
 A: Hint: You could try the following. Multiply the equation with $x^n$ and sum over $n=2$ to $n= \infty$.
$$\sum_{n=2}^{\infty}S(n)x^n=\sum_{n=2}^{\infty}x^n+\sum_{n=2}^{\infty}S(n-1)x^n+2\sum_{n=2}^{\infty}\frac{S(n-2)}{n}x^n$$
Now, switch the index for the second and third sum on the right hand side to get:
$$\sum_{n=2}^{\infty}S(n)x^n=\sum_{n=2}^{\infty}x^n+\sum_{n=1}^{\infty}S(n)x^{n+1}+2\sum_{n=0}^{\infty}\frac{S(n)}{n+2}x^{n+2}.$$
Now, split the sums so that they all start from $n=2$
$$\sum_{n=2}^{\infty}S(n)x^n=\sum_{n=2}^{\infty}x^n+S(1)x^2+\sum_{n=2}^{\infty}S(n)x^{n+1}+2\sum_{n=2}^{\infty}\frac{S(n)}{n+2}x^{n+2}+2\frac{S(0)}{2}x^2+2\frac{S(1)}{3}x^3$$
Get the sums on the right hand side:
$$(1-x-2x^2)\sum_{n=2}^{\infty}S(n)x^n=\sum_{n=2}^{\infty}x^n+S(1)x^2+2\frac{S(0)}{2}x^2+2\frac{S(1)}{3}x^3.$$
Now divide by $(1-x-2x^2)$:
$$\sum_{n=2}^{\infty}S(n)x^n=\left(\sum_{n=2}^{\infty}x^n+S(1)x^2+2\frac{S(0)}{2}x^2+2\frac{S(1)}{3}x^3\right)/(1-x-2x^2).$$
Find the talyor expansion of the right hand side and compare coefficients. Maybe you might get a closed formula for your $S(n)$. Note, that $\sum_{n=2}^{\infty}x^n$ is related to the infinite geometric series. Plug in $S(0)=0$ and $S(1)=1$ to reduce the complexity.
$$\sum_{n=2}^{\infty}S(n)x^n=\left(\frac{1}{1-x}-1-x^2-x^3+x^2+\frac{2}{3}x^3\right)/(1-x-2x^2)$$
$$\sum_{n=2}^{\infty}S(n)x^n=\frac{\frac{1}{1-x}-1-\frac{1}{3}x^3}{1-x-2x^2}$$
Divide by $x^2$ and change index of summation:
$$\sum_{n=0}^{\infty}S(n+2)x^n=\frac{\frac{1}{1-x}-1-\frac{1}{3}x^3}{x^2(1-x-2x^2)}.$$ 
Now, determine the taylor expansion on the right side to get your coefficients.
