A Skip Free Negative Random Walk Suppose $\{X_{n}|n\geq 1\}$ is independent, identically distributed distribuited. Define $S_{0}=X_{0}=1$ and for $n\geq 1$
$$S_{n}=X_{0}+X_{1}+\cdots+X_{n}.$$
For $n\geq 1$ the distribution of $X_{n}$ is specified by
$$\mathbb{P}[X_{n}=j-1]=p_{j},\qquad j=0,1,\ldots$$
where
$\sum_{j=0}^{\infty}p_{j}=1$ and we defined
$$f(s):= \sum_{j=0}^{\infty}p_{j}s^{j}\quad \mbox{for}\quad 0\leq s\leq 1.$$
Let  $$N:=\inf\{n|S_{n}=0\}.$$
If $P(s):=\mathbb{E}[s^{N}]$, show $P(s)=sf(P(s))$.
My attempt: The only thing that I have been able to show is the following relationship: Note that $\mathbb{P}[N=0]=0$ y $\mathbb{P}[N=1]=p_{0}$, and for $k\geq 2$ we have
\begin{align}
\mathbb{P}[N=k]&=\sum_{j=1}^{k-1}\mathbb{P}[N=k,X_{1}=j-1]\\
&= \sum_{j=1}^{k-1}p_{j}\sum_{i_{1}=1}^{k-j}\mathbb{P}[N=i_{1}]\sum_{i_{2}=1}^{k-j-i_{1}+1}\mathbb{P}[N=i_{2}]\sum_{i_{3}=1}^{k-j-i_{1}-i_{2}+2}\mathbb{P}[N=i_{3}]\cdots\cdots\cdots\\
&\cdots \sum_{i_{k-j-1}=1}^{k-j-\sum_{r=1}^{k-j-2}i_{r}+k-j-2}\mathbb{P}[N=i_{k-j-1}]\sum_{i_{k-j}=1}^{k-j-\sum_{r=1}^{k-j-1}i_{r}+k-j-1}\mathbb{P}[N=i_{k-j}] \mathbb{P}[N=k-j-\sum_{r=1}^{k-j-1}i_{r}+(k-j-1)-i_{k-j}+1].  
\end{align}
I do not like this formula, I think that to go from $\sum_{k=0}\mathbb{P}[N=k]s^{k}$ to $sf(P(s))$ with this formula it will be very difficult, I feel that there must be an easier way to prove that $P(s)=sf(P(s))$.
 A: You can solve the problem with this outline:

*

*$P(s)$ is the probability generating function for $N$.


*When $X,Y$ are independent random variables, the probability generating function for $X+Y$ is product of the pgf's for $X$ and $Y$.


*We can think of $N$ as $N_{1\to 0}$, meaning the time it takes to move from $1$ to $0$. Conditional on $X_1=j-1$, then $N_{1\to 0}$ is one plus the time it takes to move from $j$ to $0$. The walk is skip free, meaning it must hit all levels between $j$ and $j-1$. Breaking up the walk based on the first time it hits each level, we see that
$$
E[N_{1\to 0}|X_1=j-1]=1+N_{j\to (j-1)}+N_{(j-1)\to (j-2)}+\dots+N_{1\to 0}
$$
All summands (except the $1$ out front) are independent, with the same distribution equal to that of $N_{1\to 0}=N$, so using points $1$ and $2$,  the probability generating function for their sum is just $P(s)^j$. Furthermore, the pgf for the constant $1$ is just $s$.


*Therefore,
$$
E[s^N]=\sum_j P(X_1=j-1)E[s^N|X_1=j-1]=\sum_j p_j sP(s)^j=sf(P(s))
$$
