Calculating the hitting probability using the strong markov property ** This problem is from Markov Chains by Norris, exercise 1.5.4.**
A random sequence of non-negative integers $(F)n)_{n\ge0}$ is obtained by setting $F_0=0$ and $F_1=1$ and, once $F_0,\ldots,F_n$ are known, taking $F_{n+1}$ to be either the sum or the difference of $F_{n-1}$ and $F_n$, each with the probability $1/2$.  Is $(F_n)_{n\ge0}$ a Markov chain?
(a) By considering the Markov chain $X_n=(F_{n-1},F_n)$, find the probability that $(F_n)_{n\ge0}$ reaches $3$ before first returning to $0$.
(b) Draw enough of the flow diagram for $(X_n)_{n\ge0}$ to establish a general pattern.  Hence, using the strong Markov property, show that the hitting probability for $(1,1)$, starting from $(1,2)$, is $(3-\sqrt{5})/2$.
(c) Deduce that $(X_n)_{n\ge0}$ is transient.  Show that, moreover, with probability $1$, $F_n \rightarrow \infty$ as $n \rightarrow \infty$.

My attempt for (b): From $(1,2)$ the chain looks like $(1,2)\rightarrow (2,3)$ or $(1,2)\rightarrow (2,1)$ each with probability 1/2. From $(2,1)$ we can reach $(1,1)$. I want to calculate the probability generating function using the strong markov property $\phi(s)=\mathbb{E}_{(1,2)}(s^{H_{(1,2)}^{(1,1)}})$ where $H_{(1,2)}^{(1,1)}=\inf \{n\geq 0\colon X_n=(1,1) \text{ starting from } (1,2)\}$. I thought that if we start in $(2,3)$ and we want to reach $(1,1)$ we at least have to go trough $(1,2)$ again and then from $(1,2)$ to $(1,1)$. So I believe that $\mathbb{E}_{(2,3)}(s^{H_{(2,3)}^{(1,1)}})=\phi(s)^2$, but I am not sure if this true
I really need help with this exercise.
Thank you.

I also stumbled upon this problem.  I did not solve (a) and (c) so far, but for you specific questions I have the answer.
If drawing the flow diagram of the Markov chain up to 4 steps from $(1,2)$ (i.e., about $2^4$ states can be reached), one notices, that one step into the wrong direction (e.g., from $(1,2)$ to $(2,3)$ requires 2 steps back.
An example: $(1,2) \rightarrow (2,3)$ requires 2 steps $(2,3) \rightarrow (3,1) \rightarrow (1,2)$ to get back to the initial position.  This holds true for any state.  With this observation in mind, we can write down the hitting probability of $(1,1)$ starting from $(1,2)$ denoted as $h_{(1,2)}^{(1,1)} := h_{(1,2)}$:
$$h_{(1,2)} = \frac{1}{2} h_{(2,3)} + \frac{1}{2} h_{(2,1)},$$
and
$$h_{(2,3)} = h_{(2,3)}^{(1,2)} h_{(1,2)} = h_{(1,2)} h_{(1,2)} = h_{(1,2)}^2,$$
because $h_{(2,3)}^{(1,2)}$ has the same distribution as $h_{(1,2)}$.  A similar argument can be used to derive
$$h_{(2,1)} = \frac{1}{2-h_{(1,2)}}.$$
Putting this together, we end up at
$$0 = h_{(1,2)}^3 + 4h_{(1,2)}^2 - 4h_{(1,2)} + 1.$$
In this case, the only valid solution to this equation is $h_{(1,2)}=\frac{3-\sqrt{5}}{2}$.
