# Prove limit of non linear recursive sequence

Let $$p_0=1$$ and $$p_2=0$$. For $$n\in\mathbb{N}$$, $$n\geq 4$$, $$n$$ even the series is defined by \begin{align*} p_{n} =\frac{n-2}{n-1}\left(p_{n-2} + \frac{1}{n-3}p_{n-4} \right). \end{align*} I played around with that and I am pretty sure that \begin{align*} \lim\limits_{n\rightarrow \infty} p_n = \frac{1}{\sqrt{e}}, \end{align*} but I did not manage to prove that. The series itself is a solution to a nice riddle that I won't reveal for now so as not to spoil anything. But $$p_n$$ are probabilities, so $$0\leq p_n\leq 1$$ for all $$n$$. Maybe someone here has an idea how to go about it?

EDIT

If it is easier we can also define the series for $$t\in\mathbb{N}$$ as $$p_0=1$$, $$p_1=0$$ and for $$t\geq 2$$ \begin{align*} p_{t} =\frac{2t-2}{2t-1}\left(p_{t-1} + \frac{1}{2t-3}p_{t-2} \right). \end{align*}

EDIT-2

@dxiv: Your answer is completley sufficient. I was't aware oeis covered that so well and I have no idea how you could spot the transformation so quickly...amazing! Now that the cat's out of the bag, the original riddle (which is basically the dancing problem) goes like this: You have $$n=2t$$ students sitting pairwise at $$t$$ tables in a classroom and you randomly create a new seating order. What is the probability that no old partner sits together again?

And this is how I came up with the sequence: Randomly drawing names from a bowl: With probability $$\frac{n-2}{n-1}$$ we have no old couple at the first table. Given this situation, the old partners of the first couple can either sit together or not.

• They sit together: This has probability $$\frac{1}{n-3}$$. After that we have the original situation minus two couples.
• They do not sit together: We can treat them as if they had been an old couple and we immediatly have the original situation minus one couple.

This leads directly to $$p_{n} =\frac{n-2}{n-1}\left(p_{n-2} + \frac{1}{n-3}p_{n-4} \right)$$.

• Is your $p_n$ taken from some other series defined for all $n$? Ask because your question only refers to values of $p_n$ at $n=0,2,4,6,\cdots.$ Commented Apr 3, 2023 at 19:53
• No that is just for convenience (or inconvenience?), in can be rewritten that $n=0,1,2,\dots$. Commented Apr 3, 2023 at 19:57

(Not a complete answer but too long for a comment.)

Let $$\,q_t = (2t-1)!!\,p_{t}\,$$, then:

$$p_{t} =\frac{2t-2}{2t-1}\left(p_{t-1} + \frac{1}{2t-3}p_{t-2}\right) \quad\iff\quad q_{t} =2(t-1)\left(q_{t-1} + q_{t-2}\right)$$

With $$\,q_0=1, q_1=0\,$$ this is OEIS A053871:

Number of deranged matchings of 2n people with partners (of either sex) other than their spouse. 2n objects are initially paired in some way and then are re-paired so that no object is with its original partner (the dancing problem in the article).

The OEIS page attributes to Lewis Mammel the result that $$\,\lim_{t\to\infty}\dfrac{q_t}{(2t-1)!!} = \dfrac{1}{\sqrt{e}}\,$$.

• Really cool, thanks! My answer to your solution was also too long for a comment, so I edited my question. Commented Apr 4, 2023 at 10:00
• @IWilms Glad it helped, and thanks for the background. The substitution was suggested by the pattern $1, (2t-1), (2t-1)(2t-3)$ in the denominators of the original recurrence. That simplified the relation nicely, but the solution was still not obvious, so I entered the first few values $1, 0, 2, 8, 60$ in OEIS which promptly found A053871.
– dxiv
Commented Apr 4, 2023 at 17:58