Probability that a random pairing of numbered people is "good" There are two people numbered $1$, two people numbered $2$, ..., two people numbered $n$. The $2n$ people are randomly paired up by choosing a random permutation of the people. So for $n=3$, if the randomly chosen permutation is $121332$, then the pairings are $(12)(13)(32)$.
A "good" pair is a pair such that both people's numbers are either the same, or one apart. $(11)$ and $(12)$ are good pairs, while $(31)$ is not. What is the probability that for a random pairing, all pairs are good?
My attempt: Let $p(n)$ be the probability that all pairs are good for the $n$ case. Then $p(1)=p(2)=1$. For $p(n)$, choose one of the people labeled $n$. The probability is $\frac{1}{2n-1}$ that they're paired with the other person labeled $n$, and $\frac{2}{2n-1}$ that they're paired with someone labeled $n-1$. If they're paired with someone labeled $n-1$, then the other person labeled $n$ must also be paired with the other person labeled $n-1$, which has probability $\frac{1}{2n-3}$ of happening. So the recursion I'm getting is $p(n) = \frac{1}{2n-1}\cdot p(n-1) + \frac{2}{2n-1}\cdot \frac{1}{2n-3}\cdot p(n-2)$.
The problem is I can't confirm whether this is correct, and even if it is I don't know how to find an explicit formula.
 A: Let's imagine all items are distinguishable. The total number of permutatons is $z_n = (2n)!$
Let $x_n$ count the good permutations.
By a similar reasoning we get the recurrence
$$x_n = 2 \, n \, x_{n-1} + {n  \choose 2} 16 \, x_{n-2} =  \, n \, x_{n-1} + n(n-1) 8 \, x_{n-2} \tag1$$
with $x_0=1$, $x_1=z_1=2$.
Letting $x_n = w_n \, 2^{n} \,n!$ we can also write the simpler
$$w_n = w_{n-1} + 2 \, w_{n-2} \tag 2$$
with $w_0=1$, $w_1=1$.
And the desired probability is then
$$p_n = \frac{x_n}{z_n}= w_n \, 2^n \frac{ n!}{(2n)!} \tag 3 $$
The Fibonacci-like recursive equation $(2)$ can be solved
by the usual methods. Its characteristic polynomial is $x^2-x-2=(x+1)(x-2)$, hence the general term has the form
$$w_n = k_1 2^n + k_2(-1)^n \tag 4$$
Plugging the initial conditions we get the solution
$$ w_n = \frac{2^{n+1}+(-1)^n}{3} \tag 5$$
These are also known as Jacobsthal numbers (with an index shift). See also
sequence https://oeis.org/A001045. Finally
$$ p_n = \frac{ n!}{(2n)!} \left( \frac23 4^n + \frac13(-2)^n \right) \approx (e/n)^n \frac{\sqrt{2}}{3} \tag 6$$
The latter asymptotic is quite precise already for $n \ge 5$.
