We are given a random walk on $\mathbb{Z}$, where $p_{i, i+1}= p < \frac{1}{2}$ and $p_{i,i-1}=1-p > \frac{1}{2}$, starting at $0$.
Now we have to compute the probability that we eventually reach $k \in \mathbb{N}$.
How could one solve that?
For the recurrence equation $d_i=p d_{i+1} + (1-p) d_{i-1}$ I have no base cases (except $d_k=1$) and computing $P[\text{eventually reaching k}]=\sum_{i=1}^{\infty} P[\text{ reaching k in step i}]$ seems to be very nasty.
So do you have a hint how to solve this?
Consider some nonnegative integers $i$ and $j$. To reach $i+j$ starting from $0$, one must first reach $i$ starting from $0$ then reach $i+j$ starting from $i$.
The probability of the first event is $d_i$. By the Markov property and the invariance of the dynamics by the translations of $\mathbb Z$, the property of the second event conditionally on the first is $d_j$. Thus $d_{i+j}=d_id_j$ for every nonnegative integers $i$ and $j$, with $d_0=1$.
Using that $d_i\lt1$ for every $i\geqslant1$ since the random walk has a negative drift, and the identity in your post, this suffices to show that $d_i=r^i$ for every $i\geqslant1$, where $r=$ $____$.