Let $f(1)=f(2)=1$ and recursively define $f(n+1) = f(n) + f(i)$, where $i$ is chosen uniformly at random from $1,\ldots,n-1$. About how big should we expect $f(n)$ to be for $n$ large? We can examine the expected value of $f(n)$, say $E(f(n)) = g(n)$. After some algebra we get the second-order difference equation $$g(n+2) = \left(2-\frac{1}{n}\right)g(n+1) - \left(1-\frac{2}{n}\right)g(n)$$ for $n>0$. I did some guesswork by first looking at related differential equations, then adjusting the fit, then numerically estimating the constant to suggest $$g(n) \sim \frac{1}{\sqrt{\pi e}} \frac{e^{2\sqrt{n}}}{n^{3/4}}.$$

That the order is correct follows from Wong and Li, "Asymptotic Expansions for Second-Order Linear Difference Equations".

I have two questions.

First question. How do you rigorously prove that $1/\sqrt{\pi e}$ is the correct proportionality constant? I guessed it from numerical evidence, but the fit is good enough that I believe it's correct. The paper by Wong and Li doesn't appear to address determining the proportionality constant, likely because it depends on initial values.

Second question. Wong and Li give a recursive procedure at (2.18) to generate higher-order asymptotic terms. I've implemented the code to compute the next term $c_1$, but it disagrees with the value for $c_1$ they give in an alternate form at (2.19). Numerically, the value from (2.19) appears to be correct. Is there a typo in (2.18) somewhere?

Using (2.19) we get $$g(n) \sim \frac{1}{\sqrt{\pi e}} \frac{e^{2\sqrt{n}}}{n^{3/4}}\left(1-\frac{101}{48}\frac{1}{\sqrt{n}}\right).$$

I've implemented both (2.18) and (2.19) to compute $c_1$ in SageMath (my code).

My SageMath code calculates $187/48$ using (2.18), but $-101/48$ using (2.19). The value $-101/48$ appears to be correct numerically.

Added: Brendan McKay pointed out this wonderful connection to sequence A000262 in the OEIS: $$g(n) = \frac{2}{(n-2)!} A(n-2)$$ for $n>2$. I haven't proven this relationship, but it definitely appears to be true. It implies, for example, that $$g(n) = \frac{2}{n-2} L_{n-3}^1 (-1),$$ the generalized Laguerre polynomials, for $n>2$, giving the asymptotic series $$g(n) = \frac{1}{\sqrt{\pi e}} \frac{e^{2\sqrt{n}}}{n^{3/4}}\left( 1 - \frac{101}{48}\frac{1}{n^{1/2}} + \frac{16609}{4608}\frac{1}{n} - \frac{18575473}{3317760}\frac{1}{n^{3/2}} + \ldots \right).$$

This establishes the proportionality constant for the asymptotics of this particular sequence, but still leaves open my original questions. How do you determine proportionality constants for similar second-order linear difference equations in general? Given the additional terms for this asymptotic series, I should be able to track down the error(s) in the recursive algorithm given by Wong and Li, but it'll take some calculation and time.

Added: I've now proven that $g(n) = 2 L_{n-2}^{-1}(-1)$, and it was actually quite easy.

We have the recurrence $$g(n+3) = \left(2-\frac{1}{n+1}\right) g(n+2) - \left(1-\frac{2}{n+1}\right) g(n+1),$$ which we can write $$g(n+3) = \frac{1}{n+1} \left( (2n+1) g(n+2) - (n-1) g(n+1) \right).$$

But this is a generalized Laguerre recurrence!

We need $1+\alpha-x = 1$ and $-1 = \alpha$, and so $\alpha = x = -1$, thus $$g(n) = C\cdot L_{n-2}^{-1}(-1)$$ for some constant $C$, assuming agreement with initial values. But $g(3) = 2 = 2 L_1^{-1}(-1) = 2\cdot 1$ and $g(4) = 3 = 2 L_2^{-1}(-1) = 2\cdot 3/2$, thus $g(n) = 2 L_{n-2}^{-1}(-1)$ for all $n>2$!

2more comments