# Limit of recursive sequence $n^2q_n=1+(n-1)^2q_{n-1}+2(n-2)q_{n-2}$

When looking at this riddle, I came across the following sequence for the frequency of sampled integers between 1 and $n$ in a without replacement/without neighbour sampling: $$q_1=1,\quad q_2=1/2,\quad q_n=\frac{1}{n^2}+\frac{(n-1)^2}{n^2}q_{n-1}+\frac{2(n-2)}{n^2}q_{n-2}\quad (n>2)$$ and I wonder if there is a generic mathematical approach to computing an analytic solution for $$\lim_{n\to\infty} q_n$$Assessing the numerical limit with an R code like

q=rep(1,1e7)
for (n in 3:1e7) q[n]=(1+2*q[n-2]+(n-1)*q[n-1])/n
q[1e7]/1e7


led me to $0.432332...$ And a probabilistic reasoning indicates that $(n>1)$ $$\frac{1}{3}\le q_n\le \frac{1}{2}$$

• Using the code above, $q_{10000}\approx 0.432362058089209$ can be computed in < 1 second on a modern machine – parsiad Apr 25 '16 at 14:20
• @Did Solve $k=\frac{1}{n^2}+\frac{k(n-1)^2}{n^2}+\frac{2k(n-2)}{n^2}$. – almagest Apr 25 '16 at 14:28
• @almagest is correct, if there is a converging solution then $q_n \sim q_{n-1} \sim q_{n-2}$ so to solve that equation^ could would give the value of $q_n$ if it converges to anything. In this case $q_n = \frac{1}{3}$ is the only valid solution, so if it does converge to something, it'll be that. – frogeyedpeas Apr 25 '16 at 14:31
• @almagest your equation makes sense only in the limit when $n\to \infty$, where it is the trivial $k=k$. – Macavity Apr 25 '16 at 15:05
• $q_n$ should converge to $\frac{1-e^{-2}}{2} \approx 0.4323323583816936$. – achille hui Apr 25 '16 at 15:56

Let $a_n = (n+1)q_{n+1}$. We have $a_0 = a_1 = 1$ and

$$(n+1)a_n = 1 + na_{n-1} + 2a_{n-2}\quad\text{ for }\quad n > 1\tag{*1}$$

Let $f(z) = \sum\limits_{n=0}^\infty a_n z^n$, multiply $(*1)$ by $z^n$ and start to sum from $n = 2$, we get

\begin{align} & \left(z\frac{d}{dz} + 1 \right)(f(z) - 1 - z) = \frac{z^2}{1-z} + \left(z\frac{d}{dz}\right)(z(f(z)-1)) + 2z^2f(z)\\ \iff & zf' + f - 1 -2z = \frac{z^2}{1-z} + z^2 f' + zf - z + 2z^2 f\\ \iff & z(1-z)f' + (1-z-2z^2)f = \frac{1}{1-z} \end{align} Solving the ODE give us

$$f(z) = \frac{1-e^{-2z}}{2z(1-z)^2} = \frac{A}{(1-z)^2} + \frac{B}{(1-z)} + g(z)\tag{*2}$$ where $\displaystyle\;\begin{cases} A &= \frac{1-e^{-2}}{2}\\ B &= \frac{1-3e^{-2}}{2}\\ \end{cases}\;$ and $g(z) = \sum\limits_{n=0}^\infty g_n z^n$ is some function analytic over all $\mathbb{C}$.

Expanding $(*2)$ as a power series and compare coefficients of $z^n$ on both sides, we get

$$(n+1)q_{n+1} = a_n = (n+1)A + B + g_n$$

Since $g(z)$ is entire, its coefficients of taylor expansion $g_n$ is bounded. As a result, \begin{align} \lim_{n\to\infty} q_{n+1} &= A + \lim_{n\to\infty} \frac{B + g_n}{n+1} = A = \frac{1 - e^{-2}}{2}\\ &\approx 0.432332358381693654053000252513757798296184227045212059265 \end{align}

• If only I could upvote twice. – parsiad Apr 25 '16 at 16:41
• Very impressive!!! – Xi'an Apr 25 '16 at 19:35
• @achillehui: Concise and instructive presentation. Very nice! – Markus Scheuer Apr 27 '16 at 5:17
• @Did wow, thanks for the big bonus. – achille hui Apr 29 '16 at 22:03