I previously asked about the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$.
$p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$
$p_i = 1$ if $i \geq x$
$p_0 = \dfrac{p_{2}}{2}$
Numerically it appears that $p_0$ tends to the ratio between every second term in the Fibonacci sequence as $x \to \infty$. Why is this?
We previously showed that the generating function for the recurrence is $U(z) = \frac{zp_1 + p_0}{z^3-2z^2+1}$. @Did also showed that
$$p_i=As^i+B(-s)^{-i}+C$$
where $s=\frac12(\sqrt5-1)$ . The boundary conditions $p_2=2p_0$ and $p_x=p_{x+1}=1$ indicate that $$ (2-s^2)A+(2-s^{-2})B+C=0, $$ and $$ As^x+B(-s)^{-x}+C=As^{x+1}+B(-s)^{-x-1}+C=1. $$
This enables us in principle to determine $A,B,$ and $C$. However the solution I get using Maple looks really horrible. As I only want to get $p_0$ and $p_1$ in this question is there some way of getting a good large $x$ estimate that is easier to interpret?
It also seems numerically that as $x\to \infty$, $p_1$ tends to $s$ (that is the ratio between consecutive terms in the Fibonacci sequence). Why is this?
Consider a random walk on the integer line making $+2/-1$ steps with equal probabilities. The usual one-step recursion shows that each $p_i$ in the question is the probability to hit the negative halfline $H=\{n\in\mathbb Z\mid n\leqslant-1\}$ after the halfline $\{n\in\mathbb Z\mid n\geqslant x\}$ above $x$, starting from $i$.
When $x\to\infty$, the situation becomes simpler since $p_i\to q_i$ the probability to never hit $H$, starting from $i$. The drift of the random walk is positive hence $q_i\gt0$ for every $i\geqslant0$ and $q_i\to1$ when $i\to\infty$. To reach $H$ starting from $i\geqslant1$, one must first hit $i-1$ starting from $i$, then hit $i-2$ starting from $i-1$, and so on until one hits $-1$ starting from $0$. By the Markov property and the space invariance of the walk, this implies that $$1-q_i=(1-q_0)^{i+1},$$ for every $i\geqslant0$. Since $q_2=2q_0$ one gets $q_i=1-r^{i+1}$ for every $i\geqslant0$, where $r$ solves $$r^3-2r+1=0,$$ and $0\lt r\lt1$. Since $x^3-2x+1=(x-1)(x^2+x-1)$, one gets $$r^2+r-1=0.$$ The roots of $x^2+x-1$ are $x=\frac12(\pm\sqrt5-1)$, hence $$r=\tfrac12(\sqrt5-1),$$ which implies $$q_0=1-r=r^2=\tfrac12(3-\sqrt5),\quad q_1=1-r^2=r=\tfrac12(\sqrt5-1).$$