I'm trying to show that the expected stopping time of the Gambler's Ruin game is $x(n-x)$, where the gambler starts with \$$x$ and the game stops at \$0 or \$$n$. The probabilities of gaining and losing \$1 at each time step are equal (1/2).
I've set up a recursion $\mathbb{E}(T_k) = \frac12 \mathbb{E}(T_{k-1}) + \frac12 \mathbb{E}(T_{k+1}) + 1$ where $T_k$ is the stopping time when the gambler has \$$k$. The recursion has base cases $\mathbb{E}(T_0) = \mathbb{E}(T_n) = 0$.
I'm not exactly sure how to proceed from here. I tried expanding the recursion even more, but this just leads to a mess of terms, and I'm not seeing the pattern. Any help would be very much appreciated!