Solution
= Solution
{c}
Let $q_n=\mathbb P(M_n=Y)$. The <law of total probability> applied to the current <markov chain state> gives
$$
p_n=\frac12p_{n-1}+\frac38q_{n-1},\qquad q_{n-1}=\frac12p_{n-2}\quad(n\ge2).
$$
The second equality holds because $Y$ can only be reached from $X$. Eliminating $q_{n-1}$ gives the <linear recurrence relation>
$$
\boxed{16p_n=8p_{n-1}+3p_{n-2},\qquad n\ge2.}
$$