A particle performs a random walk on the non-negative integers as follows. When at the point $n\ (> 0)$ its next position is uniformly distributed on the set $\{0, 1, 2, \ldots, n + 1\}$. When it hits $0$ for the first time, it is absorbed. Suppose it starts at the point $a$.
(a) Find the probability that its position never exceeds $a$, and prove that, with probability $1$, it is absorbed ultimately.
(b) Find the probability that the final step of the walk is from $1$ to $0$ when $a = 1$.
(c) Find the expected number of steps taken before absorption when $a = 1$.
I completed part (a) and obtained the probability of not exceeding $a$ to be $$ p = \frac{(a + 1)!}{1 + \sum_{n=1}^{a + 1} n!}. $$
Now I am stuck on part (b). Here is what I have so far:
Let $p_n$ be the probability that the final step of the walk is from $1$ to $0$. Then $$ p_n = \frac{1}{n + 2}(p_{n + 1} + p_{n - 1} + \cdots + p_1), $$ and, $$ p_{n - 1} = \frac{1}{n + 1}(p_n + p_{n - 1} + \cdots + p_1). $$ From these two equations we obtain \begin{align} p_{n + 1} - p_n &= (n + 1)(p_n - p_{n - 1}), \\ \implies p_{n + 1} - p_n &= \frac{1}{2}(n + 1)!(p_2 - p_1). \end{align} Summing the above expression for $p_{n + 1} - p_n$ from $2$ to $n$ gives $$ p_{n + 1} - p_2 = \frac{1}{2}(p_2 - p_1) \sum_{i = 3}^{n + 1} i! $$ But we also know that $$ p_1 = \frac{1}{3}(p_2 + p_1 + 1). $$ Therefore $p_2 = 2 p_1 - 1$. Substituting for $p_2$ in the expression for $p_{n + 1} - p_2$ we obtain $$ p_{n + 1} = p_1 + \frac{1}{2}(p_1 - 1) \sum_{i = 2}^{n + 1} i! $$ Now I am stuck because the last expression does not make sense. This is because for all $p_1 \neq 1$, $p_n \rightarrow -\infty$ as $n \rightarrow \infty$. Where have I gone wrong? Please can you provide a hint on how to approach this problem in the correct way?
Edit (2016/02/28)
With help from the comments of @zhoraster and @mick-a below, the expression for $p_{n + 1}$ actually turns out to be $$ p_{n + 1} = 5p_1 - 3 + \frac{3 p_1 - 2}{6}\sum_{i = 3}^n (i + 1)! $$ For $p_{n + 1}$ to be a valid probability the coefficient of the factorial sum on the right hand side must be equal to $0$ as $n \rightarrow \infty$. This implies that $p_1 = 2/3$ and hence that $p_n = 5 \times 2/3 - 3 = 1/3$ for $n \geq 2$. I would never have expected that!
For completeness, here is the solution to part(c):
Assuming that a transition from $i$ to $j$ is always a step of length 1 (regardless of the values of $i$ and $j$) we can write the expected number of steps, $\lambda_n$, given that the particle starts at $n \geq 1$ as,
\begin{align} \lambda_n &= \frac{1}{n + 2}((\lambda_{n + 1} + 1) + (\lambda_n + 1) + \cdots + (\lambda_1 + 1) + 1), \\ &= \frac{1}{n + 2}(\lambda_1 + \lambda_2 + \cdots + \lambda_{n + 1}) + 1. \end{align}
And for $n \geq 2$,
$$ \lambda_{n - 1} = \frac{1}{n + 1}(\lambda_1 + \lambda_2 + \cdots + \lambda_n) + 1. $$
Subtracting these two equations gives for $n \geq 2$, $$ (n + 1)(\lambda_n - \lambda_{n + 1}) = \lambda_{n + 1} - \lambda_n + 1. $$
The next step is the crucial step which allows the recurrence relation to be solved (and I have to admit that I needed to peek into the solutions manual for this hint). Let $v_{n + 1} = (\lambda_{n + 1} - \lambda_n) / (n + 1)!$. Then,
\begin{align} v_{n + 1} - v_n &= \frac{\lambda_{n + 1} - \lambda_n}{(n + 1)!} - \frac{\lambda_n - \lambda_{n - 1}}{n!}, \\ &= -\frac{1}{(n + 1)!}. \end{align}
Adding $v_{n + 1} - v_n$ from $n = 2$ to $\infty$ gives,
\begin{align} -v_2 &= -\sum_{i = 3}^{\infty} \frac{1}{i!} \\ \implies v_2 &= -\frac{1}{0!} - \frac{1}{1!} - \frac{1}{2!} + \sum_{i = 0}^{\infty} \frac{1}{i!} \\ \implies v_2 &= -\frac{5}{2} + e. \end{align}
But $v_2 = \frac{1}{2!}(\lambda_2 - \lambda_1)$ and $\lambda_1 = \frac{1}{3}(\lambda_1 + \lambda_2 + 3)$. Solving for $\lambda_2$ gives $\lambda_2 = 2 \lambda_1 - 3$. Therefore,
\begin{align} v_2 = \frac{\lambda_2 - \lambda_1}{2} &= -\frac{5}{2} + e \\ \implies \frac{2 \lambda_1 - 3 - \lambda_1}{2} &= -\frac{5}{2} + e \\ \implies \lambda_1 &= 2 e - 2. \end{align}