HMMT-Feb 2015 comb, Problem 3

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}$.

Solution: We note that the only way $n$ does not appear in the sequence is if $n-1$ and then $n+1$ appears. Hence, we have $p_{0}=1$, and $p_{n}=1-\frac{1}{2} p_{n-1}$ for $n>0$. This gives $p_{n}-\frac{2}{3}=-\frac{1}{2}\left(p_{n-1}-\frac{2}{3}\right)$, so that \[ p_{n}=\frac{2}{3}+\frac{1}{3} \cdot\left(-\frac{1}{2}\right)^{n} \] so $p_{20}-p_{15}$ is just \[ \frac{1-(-2)^{5}}{3 \cdot 2^{20}}=\frac{11}{2^{20}} \] $\fbox{\frac{11}{\frac{11}{2^{20}}}}$.

Answer: \frac{11}{\frac{11}{2^{20}}}