Let $\{X_{n},n\geq 1\}$ independent and identically distributed random variables with $P\left[X_{1}=1 \right]=p=1-P\left[X_{1}=0\right]$. Let $S_{n}=\sum_{k=1}^{n}X_{k}$ be a random walk on $\{0,1,2,..\}$ that can either make one step to the right or stay in its current state and that it starts at state 0. For $n\geq 0$ and $1\geq k \geq n+1$, $$P[S_{n+1}=k]=pP[S_{n}=k-1]+(1-p)P[S_{n}=k].$$ Solve the recursion equation using generating functions.
Hello, I am trying to solve this class example as my professor said and he mentioned that the solution is the binomial distribution. Can someone explain why?
Hint: Multiplying your recurrence relation by $\ x^k\ $, and summing from $\ k=1\ $ to infinity gives \begin{align} \sum_{k=1}^\infty x^kP\left[S_{n+1}=k\right]&= \sum_{k=1}^\infty px^k P\left[S_n=k-1\right]+ \sum_{k=1}^\infty (1-p)x^k P\left[S_n=k\right]\\ &=px \sum_{k=1}^\infty x^{k-1}P\left[S_n=k-1\right]+ (1-p)\sum_{k=1}^\infty x^kP\left[S_n=k\right]\\ &= px \sum_{k=0}^\infty x^kP\left[S_n=k\right]+ (1-p)\sum_{k=1}^\infty x^kP\left[S_n=k\right]\ . \end{align} Definining $\ \phi_n(x)= \sum_\limits{k=0}^\infty x^kP\left[S_n=k\right]\ $, this equation can be written as $$ \phi_{n+1}(x)-P\left[S_{n+1}=0\right]=px\phi_n(x)+(1-p)\left(\phi_n(x)-P\left[S_n=0\right]\right)\ , $$ or $$ \phi_{n+1}(x)=\left(px+1-p\right)\phi_n(x)\ , $$ because $\ P\left[S_{n+1}=0\right]=(1-p)^{n+1}=(1-p) P\left[S_n=0\right]\ $. This recursion has the solution $\ \phi_n(x)=(1-p+px)^{n-1}\phi_1(x)\ $, and since $\ \phi_1(x)=(1-p) +px\ $, we end up with $$ \phi_n(x)= (1-p+px)^n\ . $$ What is the coefficient of $\ x^k\ $ in $\ (1-p+px)^n\ $?