Expected time to get x units away when only able to move 1 unit either way

Question

I know this is a common problem, but this problem has been bugging me after someone asked me it, and I can't find the answer anywhere on the Internet.

Say we have a number line, and we start at the point 0. On each turn, we can move left with the probability of 1/2, or we can move right with the probability of 1/2. What is the expected number of turns until we get x units away on either side? (i.e., I don't care which side I get to, I'll stop when I get x units away)

Answer 1

Let $u(i)$ be the expected number of turns to reach $\pm x$, starting at $i \in \{-x, -x+1, \ldots, x\}$. Then $u(-x) = u(x) = 0$ and if $-x < i < x$, $u(i) = 1 + (u(i-1) + u(i+1))/2$. The general solution of the last equation is $u(i) = a + b i - i^2$, and from the conditions $u(-x) = u(x) = 0$ we get $a = x^2$, $b = 0$. In particular $u(0) = x^2$.

Answer 2

If $E_d$ is the expected number of steps to reach $\pm x$ when an absolute distance of $d$ from $0$ then $$E_d=1+\frac12 E_{d-1}+\frac12E_{d+1}$$ for $0 \lt d \lt x$, but $$E_x=0$$ $$E_0=1+E_1$$ which leads to $E_d = 2d+1 +E_{d+1}$ and so $E_d = x^2 - d^2$ and in particular $E_0=x^2$.