A few days ago I asked a question about a probability puzzle. After a lot of working out, I found that the answer to the puzzle involves a pair of recurrence relations of polynomials. To be explicit, I can define the following sequences of polynomials:
\begin{align*} P_1 & = x \\ P_j & = P_{j-1} + P_1 \prod_{k=1}^{j-1} P_k \\ T_1 & = x \\ T_j &= T_{j-1} + P_j \end{align*}
It turns out the solution to the puzzle for $n$ coins is the real root of $T_n - \alpha$ (the real root between 0 and 1 if there are multiple). Here are the first few polynomials and the associated real root when $\alpha = \frac{n}{2}$ (this specific choice of $\alpha$ is relevant to the problem - the motivation is that we want $n$ probabilities to average to $\frac{1}{2}$).
\begin{matrix} T_1 = x & p_1 = \frac{1}{2} \\ T_2 = x^2 + 2x & p_2 = \sqrt{2} - 1 \\ T_3 = x^4 + x^3 + 2x^2 + 3x & p_3 \approx 0.379125 \\ T_4 = x^8 + 2x^7 + 2x^6 + 2x^5 + 3x^4 + 2x^3 + 3x^2 + 4x & p_4 \approx 0.361182 \end{matrix}
$T_n$ is a polynomial of degree $2^{n-1}$ so it is very difficult to find its roots numerically (and obviously impossible analytically). However, because $T_n$ comes from a very nice recurrence relation, it may be more structured than at first glance. Furthermore, I can find $p_n$ for larger $n$ by solving an equivalent optimization problem, and it seems as though $\lim_{n \to \infty} p_n$ converges to something around 0.3. This leaves me two questions about this problem that I don't see how to tackle.
- Is it possible to determine the coefficients of $T_n$ without recursively building up $T_1, T_2, \ldots, T_{n-1}$?
- Is it possible to easily find $\lim_{n \to \infty} p_n$?