In a random walk problem where $S_n=S_0+X_1+\cdots+X_n$ with $S_0$ being an integer and $X_i$ following a Bernoulli distribution, the variable for the first arrival at levels $A$ or $-B$ is defined as $$ \tau=\min\{n\geq0:S_n=A \text{ or } S_n=-B\} $$ it can be shown that $$ E(\tau|S_0=k)=\frac{1}{2}E(\tau|S_0=k-1)+\frac{1}{2}E(\tau|S_0=k+1)+1 $$ but I cannot see why (formal proof) the $+1$ appears. It is only mentioned that
the gambler's fortune will have changed, and a unit of time will have passed
and then the last equation is derived. I would appreciate any suggestions or calculations that could help me understand this part.
After some time, I got a formal proof. By considering the expected values when initiating at $S_0=1$ and $S_0=-1$, we derive the following expressions:
\begin{align*} E[\tau|S_0=1]&=\sum_{m=0}^\infty nP(\tau=n|S_0=1)=\sum_{n=0}^\infty np_n\\ E[\tau|S_0=-1]&=\sum_{m=0}^\infty nP(\tau=n|S_0=1)=\sum_{m=0}^\infty mq_m \end{align*}
In the case of starting from $S_0=1$ as depicted in the left figure, each path is associated with its probability $p_n$. Notably, every path beginning from $S_0=0$ falls into one of two classes: those where $S_1=1$ or $S_1=-1$. This observation reveals that every path starting from $S_0=0$ and going $+1$ in the next step (right) is nearly identical to starting at $S_0=1$ (left), differing only in an additional step. Consequently, the probability of the new path is $\frac{1}{2}p_n$. Employing a similar analysis for paths going through $S_1=-1$ yields probabilities of $\frac{1}{2}q_m$.
When taking the expected value of these paths, we must also account for the extra "time" of $+1$:
\begin{align*} E[\tau|S_0=0]&=\sum_{n=0}^\infty \dfrac{1}{2}(n+1)p_n+\sum_{m=0}^\infty \dfrac{1}{2}(m+1)q_m\\ &=\dfrac{1}{2}\left(\sum_{n=0}^\infty np_n+\sum_{m=0}^\infty mq_m+\sum_{n=0}^\infty p_n+\sum_{m=0}^\infty q_m\right)\\ &=\dfrac{1}{2}\left(E[\tau|S_0=1]+E[\tau|S_0=-1]+2\right)\\ &=\dfrac{1}{2}E[\tau|S_0=1]+\dfrac{1}{2}E[\tau|S_0=-1]+1 \end{align*}
The generalization is clear: $$E[\tau|S_0=k]=\dfrac{1}{2}E[\tau|S_0=k+1]+\dfrac{1}{2}E[\tau|S_0=k-1]+1\qquad -B<k<A$$