Let $Y_1, Y_2, ....$ be iid random variables with $Y_i = \pm 1$ with equal probability. Define random variables $X_0 = 0$ and $X_k = Y_1+ ...+ Y_k$. I'm trying to understand the solution to the exercise: Given two positive integers $A$ and $B$ what is the probability that random walk reaches $A$ before $-B$?
Solution: Let $\tau$ be the first time at which the rw reaches $A$ or $-B$. Define $$ f(k)= P(X_\tau = A | X_0 = k). $$ The answer we are looking for is then $f(0)$. It is easy to solve from the recursive formula $$ f(k) = \frac12 f(k+1) + \frac12 f(k-1). $$
question: I don't understand how this recursive formula is found (no explanation in the solution). I get as far as: $$ f(k)= P(X_\tau = A | X_0 = k) = P(X_\tau = A | X_1 = k+1) P(X_1 = k+1|X_0 = k) + P(X_\tau = A | X_1 = k-1) P(X_1 = k-1| X_0 = k). $$ Then $P(X_1 = k+1|X_0 = k) = P(X_1 = k+1|X_0 = k) = 1/2$ so $$ f(k)= \frac12 P(X_\tau = A | X_1 = k+1) + \frac12 P(X_\tau = A | X_1 = k-1). $$ But $P(X_\tau = A | X_1 = k+1)$ is not $f(k+1)$ so I don't the formula...
How can I get the formula? Any clarifications are appreciated. thank you!