Probability of landing on a particular point in an infinite 1D random walk

Question

$50\%$ of the time you walk right one unit, and $n$ units to the left o.w. The probability in question is ever landing one unit to the right of where you start at (as your number of moves goes to infinity).

I've read somewhere that the answer is (not sure if I remember correctly): $$P=\frac{1}{2}+\frac{1}{2}P^{n+1}$$

but I cant figure out why. The first term is self-explanatory (half the time you reach your goal right-then-and-there), but I can't find an intuitive explanation for the second (recursive) term - the coefficient of the second term makes sense (half of the other time something else happens), but I can't explain the second factor and its power. Please explain what the interpretation is.

Answer 1

If you start by going left $n$ units, then you have to go right $n + 1$ times.

Answer 2

You might find the idea of Markov Chains useful to help solve your problem.

Answer 3

Equation 3 here gives the probability of taking $n_1$ steps to the right as

$$ P\left(n_1\right) = \frac{N!}{2^N n_1!\left(N-n_1\right)!}, $$

where I've substituted $p = 1/2$, the probability of taking a step to the right. You're asking for the probability that $n_1 = \left(N+1\right)/2$, which is

$$ P\left(\frac{N+1}{2}\right) = \frac{N!}{2^N \left(\frac{N+1}{2}\right)!\left(\frac{N-1}{2}\right)!}. $$

You might be able to simplify further. I guess you're looking for large N behavior?

Update: Since you're looking for large N behavior, I'd try to use Stirling's approximation.