Explicit formula for implicitly defined sequence? In brief, I'd like an explicit formula, asymptotic behavior, or at least some analytic information, about the following sequence:
$$w_0 = 0, w_1 = 1,$$
$$n \ge 1: w_{n+1} = \frac{(n-1)w_n + 2 w_{n-1}}{n}.$$
At length...
So far I've tried guessing a solution of the form $w_n = z^n(c_s n^s + c_{s-1} n^{s-1} \ldots)$ but I find that $z$ must be zero or one. That first case doesn't seem useful; in the latter case I obtain $w_n = c(n+2)$ as a solution. However, this doesn't fit the initial conditions. When I try to subtract this solution off (the recursion is linear and homogenous so different solutions can be combined and rescaled freely), I find something that seems to be roughly but not exactly exponentially decaying (and oscillating) left over.
The motivation for this is what I'm calling the "couples seating problem" (it might have appeared before, but I don't know it). Suppose you have a row of $n$ seats, and couples (pairs of people) sit down in pairs of adjacent open seats, equally likely to take any open seats. For example, if there is a block of five open seats, a couple sitting in that block has four places they might sit. Eventually, there will be some number of single open seats and no more couples can sit down. $w_n$ is meant to be the average number of wasted seats, with the recursion relationship obtained by first writing down the number of wasted seats $w_n$ relative to $w_0, \ldots w_{n-2}$ by averaging over all possible seats, then combining the $w_n$ and $w_{n+1}$ expressions to obtain the recursion relationship without a long sum. The problem generalizes easily from couples to trios, etc. Barring an explicit formula, I'm most interested in knowing what fraction of seats is wasted in the large system limit (numerically, it seems to be about .135).
Any suggestions? Thanks in advance.
 A: As a general solution, Wolfram Mathematica gives \begin{align*}
& w_n= c_1 (n+2) \\&+c_2\frac{(-1)^{n+1} 2^{-n-3}}{e^2 (n+4)!(n+1)!} \left((-1)^n 3 \cdot2^{n-1} (n+4)!(n+2)! \left(-8-8 e^2+4 \Gamma(3,-2)\right)\right.\\ &+(-1)^{n+1} 3\cdot 2^n \left(-(n+1) (n+4)! \Gamma(n+3,-2)\right.\\ & +(n+2)! \left((n+1) (n+4)!\right.\\ &+(n+4) \left.\left.\left.\left((-1)^n 2^{n+4} e^2-(n+5) (n+3)!+(5+n) \Gamma(n+4,-2)\right)\right)\right)\right)
\end{align*}
where for the incomplete gamma function one can use $(8.4.8)$.
A: As we can see from Gary's answer, you can get a lot out of Mathematica for your money. But let's try an old-fashioned way: since $w_n=n+2$ is a particular solution of $$n\,w_{n+1}=(n-1)\,w_n+2\,(n+1)\,w_{n-1},$$ we let
$$w_n=(n+2)\,v_n,$$ i.e.
$$n\,(n+3)\,v_{n+1}=(n-1)\,(n+2)\,v_n+2\,(n+1)\,v_{n-1}.$$ Now since
$$(n-1)\,(n+2)=n\,(n+3)-2\,(n+1)$$ (this is just another way to say that $w_n=n+2$ satisfies the recurrence),
this becomes
$$n\,(n+3)\,(v_{n+1}-v_n)=-2\,(n+1)\,(v_n-v_{n-1}).$$ Since $v_0=0$ and $v_1=1/3$, this gives (by induction)
$$v_n-v_{n-1}=-(-2)^n\frac{n}{(n+2)!}.$$ Thus,
$$\lim_{n\to\infty}\frac{w_n}n=\lim_{n\to\infty}v_n=-\sum^\infty_{n=1}(-2)^n\frac{n}{(n+2)!}.$$ Observing $n=(n+2)-2$ and using the well-known series for $e^{-2}$ should easily give the result, now.
