Recurrence for random walk I have 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}$
I would like to solve this for any integer $0\leq i \leq x$.  
This looks to be a 3rd order recurrence relation which would normally need more initial conditions. However I don't think they are needed in this case if you know we are only interested in $i\geq 0$.
How can one go about solving this?

If $x=4$ we get $p_0= 5/12$, $p_1= 2/3$, $p_2=5/6$, $p_3 = 11/12$.

My first generating function attempt.
We have $\sum_{n\geq 0}  z^n p_{n+2} = 2\sum_{n\geq 0} z_n p_n - \sum_{n\geq 0} z_n p_{n-1}$.
$\sum_{n\geq 0} p_{n+2} z^n = \frac{U(z) - p_0 - zp_1}{z^2}$. Also $\sum_{n\geq 0} z_n p_{n-1} = zU(z)$ (although I am worried about having to consider $p_{-1}$ here).
So we have to solve $\frac{U(z) - p_0 - zp_1}{z^2}= 2U(z) - zU(z)$ giving $U(z) = \frac{zp_1 + p_0}{z^3-2z^2+1}$.
Assuming the calculation is right we are stuck with something containing $p_0$ and $p_1$ which seems bad.
 A: The recursion $$p_{i+3}-2p_{i+1}+p_{i}=0$$ indicates that one should look for solutions linear combinations of the sequences $(r^i)$, where $r$ solves the characteristic equation 
$$r^3-2r+1=0.$$ This factors as $(r-1)(r^2+r-1)=0$, thus $r=1$ or $r=s$ or $r=-1/s$ with $s=\frac12(\sqrt5-1)$, and $$p_i=As^i+B(-s)^{-i}+C.$$ Furthermore, 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 Cramer system determines $(A,B,C)$.
Note that $z^3-2z^2+1$ is related to $r^3-2r+1$ by the map $r\to1/r$ and is the denominator of the expression you got for the generating function $$U(z)=\sum_{i=0}^xp_iz^i,$$ 
hence the approach based on $U(z)$ also yields the decomposition into powers of $1$, $s$ and $-1/s$ that we outlined above. More precisely, knowing that
$$
U(z)=\frac{p_0+p_1z}{1-2z^2+z^3},
$$
factoring $1-2z^2+z^3=(1-z)(1-sz)(1+z/s)$ and rewriting $U(z)$ as
$$
U(z)=\frac{A}{1-z}+\frac{B}{1-sz}+\frac{C}{1+z/s},
$$
one gets the general expression for $p_i$ that we reached above, where $(A,B,C)$ depends on $(p_0,p_1)$. Then the boundary conditions allow to identify $(p_0,p_1)$.
