Contest problem - Solution is beyond my comprehension Starting with the number 0, Casey performs an infinite sequence of moves as follows: he chooses a
number from {1, 2} at random (each with probability $\frac{1}{2}$) and adds it to the current number. Let $p_m$
be the probability that Casey ever reaches the number m. Find $p_{20}$ − $p_{15}$.
Answer: $\frac{11}{2^{20}}$
This problem appeared in Harvard-MIT math tournament.  The solution for this is posted at this website, http://hmmt.mit.edu/static/archive/february/solutions/2015/combo.pdf.  The solution given in this problme does not reach my stone head.  But I solved it in another way that is very primitive.  Could someone let me know how this recurrence relation is obtained in this solution.
 A: In order for Casey to fail to reach $n$, he must reach $n-1$ and then pick $2$. The probability that he reaches $n-1$ is $p_{n-1}$, and the probability that he picks $2$ on his next step is $\frac12$, so the probability that he fails to reach $n$ is $\frac12p_{n-1}$. The probability of the complementary event that he does reach $n$ must therefore be $1-\frac12p_{n-1}$, so we have the recurrence $p_n=1-\frac12p_{n-1}$.
The rest of the posted answer is simply one way of solving this recurrence to get a closed form. Subtracting $\frac23$ from both sides, we have
$$p_n-\frac23=1-\frac12p_{n-1}-\frac23=\frac13-\frac12p_{n-1}=-\frac12\left(p_{n-1}-\frac23\right)\;.\tag{1}$$
Now let $x_n=p_n-\frac23$; $(1)$ shows that $x_n$ satisfies the recurrence $x_n=-\frac12x_{n-1}$. Thus, $x_1=-\frac12x_0$, $x_2=\left(-\frac12\right)^2x_0$, and in general $x_n=\left(-\frac12\right)^nx_0$: at each step you’re simply multiplying by $-\frac12$. Moreover, $x_0=p_0-\frac23=1-\frac23=\frac13$, so
$$x_n=\left(-\frac12\right)^n\cdot\frac13=\frac{(-1)^n}{3\cdot2^n}\;.$$
And $p_n=x_n+\frac23$, so we have finally
$$p_n=\frac23+\frac{(-1)^n}{3\cdot2^n}\;.$$
By the way, that $-\frac23$ doesn’t really appear by magic; this answer explains where it came from.
