Rectangular box $ABCD.A'B'C'D'$. At vertex $A$ there is a worm. It moves along the edges of the box and goes to a vertex adjacent to the vertex it is standing. Calculate the probability that after nine moves it stands at vertex $C'$.
example : A-B-C-B-A-D-A-B-C-C’
I think I need a recursive formula, but I do not know how to formulate it.
Denote by $p_n$ the probability that after $n$ moves the worm is at one of the poles $A$ or $C'$. Then $$p_0=1,\qquad p_{n+1}={1\over3}(1-p_n)\qquad(n\geq0)\ .\tag{1}$$ Proof. You can get to a pole from any one of the six non-poles. The probability that after $n$ moves the worm is at a non-pole is $1-p_n$, and with probability ${1\over3}$ he then decides to move to a pole. (I'm assuming that the worm does not remember where he came from.)
Subtracting ${1\over4}$ on both sides of $(1)$ we obtain $$p_{n+1}-{1\over4}=-{1\over3}\left(p_n-{1\over4}\right)\ .$$ This implies $$p_n={1\over4}+\left(-{1\over3}\right)^n\cdot{3\over4}\qquad(n\geq0)\ ,$$ and in particular $$p_9={1640\over6561}\ .$$ Now after $9$ moves the worm cannot be at $A$, since the cube graph is bipartite. Therefore with probability $p_9$ it is at $C'$ after $9$ moves.