I have a question that relates to string and connectivity:
I have in my hand 2n lengths of string, each piece of string having one end on my left and one on my right. It is impossible to see how the ends on the left match up with the ends on the right. An assistant ties the 2n ends on the left together randomly into n pairs. They then do the same with the ends on the right. Let pn be the probability that when I take my hand away and untangle things, I have created a single, large loop of 2n pieces of string.
The question doesn't matter too much for this question, but its some background to why I am asking. So far I have found $P_1=1$, $P_2=\frac{2}{3}$ and $P_3=\frac{8}{15}$. Now I am looking for a general formula for $P_n$. Looking at my terms before I have found the formula: $P_n=P_{n-1} \times \frac{2n-2}{2n-1}$. Now I was going to attempt to prove this by induction.
So I have all my base cases above, that all work.
Then I assumed true for $n=k$.
Then considering $n=k+1$:
$$P_{k+1}=P_{k} \times \frac{2(k+1)-2}{2(k+1)-1}$$
But I am not sure how this can finish my induction from this last stage? Could anyone help point me in the right direction?
The general formula you require is $$P_n=\frac{((n-1)!)^22^{2n-2}}{(2n-1)!}.$$ As you have shown, this formula holds for small values of $n$.
Proof of the recurrence relation
Suppose we have $2k+2$ lengths of string. Consider the $2k+2$ RH ends once the LH ends have been tied. To eventually produce a single length, the first RH end can be tied to $2k$ of the other $2k+1$ ends. This has probability $\frac{2k}{2k+1}$.
The situation is now the same as if we had $2k$ lengths of string. Therefore $$P_{k+1}=\frac{2k}{2k+1}P_{k}.$$ Proof of the general formula
Assuming that $$P_k=\frac{((k-1)!)^22^{2k-2}}{(2k-1)!}$$ then $$P_{k+1}=\frac{2k}{2k+1}\frac{((k-1)!)^22^{2k-2}}{(2k-1)!}$$ $$=\frac{2k}{2k}\frac{2k}{2k+1}\frac{((k-1)!)^22^{2k-2}}{(2k-1)!}$$ $$=\frac{(k!)^22^{2k}}{(2k+1)!}$$
Together with the base case which we have already mentioned this completes the proof of the formula.