Dan wrote:
P.S. It seems plausible that the nonlinear recurrence relation Emma derives for s[n] would imply s[n] -> 1/e^2, but it would be nice to see a proof.
This isn't a proof but suggests how one might get one: if I put the first few values of (n-1)!s[n] into OEIS, it tells me they're the coefficients of the e.g.f. of exp(-2x)/(1-x)^2. Well, OK, so let's just do it. (From first principles; an actual expert on this stuff would take much bigger steps.) Step 1: Exploit the correspondence between recurrence relations and differential equations. First of all, write t[n] = (n-1)!s[n]. Then the recurrence becomes t[n+2] = n t[n+1] + 2n t[n]. Now write y = sum t[n] x^n/n!. Then we have y' = sum t[n+1] x^n/n! y'' = sum t[n+2] x^n/n! xy' = sum nt[n] x^n/n! xy'' = sum nt[n+1] x^n/n! and therefore y'' = xy'' + 2xy'. Step 2: Solve the easy differential equation. Write z = y'; then z' = xz' + 2xz, or equivalently (1-x)z' = 2xz, or equivalently z'/z = 2x/(1-x), or equivalently (log z)' = 2x/(1-x) = 2/(1-x) - 2 so, integrating, log z = -2 log (1-x) - 2 x + const, or equivalently z = A exp(-2x)/(1-x)^2. (No need to get y explicitly at this point, because knowing z is just as good.) Step 3: extract the power-series coefficients and get decent estimates. We've shown that sum t[n+1] x^n/n! = A exp(-2x)/(1-x)^2, or equivalently sum s[n+1] x^n = A exp(-2x)/(1-x)^2. The constant coefficients are s[n+1] on the left and A on the right, so A=1: sum s[n+1] x^n = A exp(-2x)/(1-x)^2. OK. The (1-x)^2 is a nuisance so let's get rid of it: sum (s[n+1]-s[n]) x^n = exp(-2x)/(1-x) sum (s[n+1]-2s[n]+s[n-1]) x^n = exp(-2x) where we define s[-1] = 0. So s[n+1]-2s[n]+s[n-1] = (-2)^n/n!, so s[n+1]-s[n] = sum{0..n} (-2)^k/k! = exp(-2) + tail[k], say, so s[n] = n exp(-2) + (tail[1]+...+tail[k]) and therefore s[n]/n = exp(-2) + o(1) because the tails tend to 0. That was rather laborious, but I'm about 99% sure that to those truly skilled in the art it would take maybe three or four lines because every bit of it is standard. -- g