 Solution

The homogeneous linear recurrence relation has characteristic polynomial $(\lambda -1{)}^2$, hence general solution $h_k=A+Bk$. For the expected-time recurrence, rearrangement gives $m_{k+1}-2m_k+m_{k-1}=-2$, for which $-k^2$ is a particular solution. ThusImposing the absorbing boundary conditions from the preceding parts gives the gambler's ruin formulas