Generating Functions of 1D Random Walk 
Define $\displaystyle F(s) = \sum_{n=0}^\infty
 f_ns^n$, where $f_n= P($ the first return to the origin at time $n)$.
  Suppose $F^{(n)}(s) = \displaystyle \sum_{k=0}^\infty f_k^{(n)} s^k$,
  where $f_k^{(n)}$ denotes the probability of the $n$th return to the
  origin at time $k$, prove that $F^{(n)}(s)=[F(s)]^n$

We defined the notation $F^{(n)}$ as $F$ composed with itself $n$ times.
Here are some results that I have proved that may or may not be helpful (not in order):


*

*Let $u_n = P ($the walk returns to the origin at time $ n)$ and $U(s), s \in [0,1)$ be the generating function corresponding to $u_n$. Then $U(s) = (1-s^2)^{-\frac{1}{2}}$

*For any $n \in \mathbb{N}$, we have ${{2n \choose n} \cdot (\frac{1}{2})^{2n}} = (-1)^n {-\frac{1}{2} \choose n}$

*$U(s) = \frac{1}{1-F(s)}=1- \frac{1}{F(s)}$

*If the random walk is asymmetric with forward probability $p$ and backward probability $q$ and $p+q=1$, then the probability of a return to the origin in finite time is $1-|p-q|$.

*$F'(1)=\infty$ when $p=q=\frac{1}{2}$. That is, the expected waiting time until the first return to the origin is infinite.
 A: Without using facts about generating functions (since it wasn't covered in 251).
$$
\textbf{Base case: n=1}
$$
This follows directly from definition. So assume the proposition is true for n.
$$
\textbf{Induction step: n+1}
$$
First note that the probability of the $n+1$th return to the origin at time $k$ is equal to the probability of first return to the origin at time $k-2$ times the probability of $n$th return to the origin at time $2$, and so on. In other words,
$$
   f_k^{(n+1)} = \sum_{i=0}^{k} f_i^{(n)}f_{k-i}
$$
Therefore,
$$
   \begin{aligned}
   F^{(n+1)}(s) &= \sum_{k=0}^{\infty} f_k^{(n+1)}s^k \\
   &= \sum_{k=0}^{\infty}\sum_{i=0}^{k}f_i^{(n)}f_{k-i} s^k \\
   &= \sum_{i=0}^{\infty}\sum_{k=i}^{\infty}f_i^{(n)}f_{k-i} s^k \\
   &= \sum_{i=0}^{\infty} f_i^{(n)}s^i\sum_{k=0}^{\infty} f_k s^{k} \\
   &= \left[F(s)\right]^{n}\left[F(s)\right]
   \end{aligned}
$$
By induction, we prove that our proposition is true for all $n+1\in \mathbb{N}$ given that it is true for $n$.
Useful tips:
For changing the order of summation, it is often useful to first set it up as an inequality, e.g. for the above example, we notice that:
$0\leq i\leq k\leq \infty$.
That means we can split it up into:
$0\leq i\leq k$ and $i\leq k\leq \infty$
but also
$0\leq i\leq \infty$ and $i\leq k\leq \infty$
which still fully describes the relationship between the 4 numbers.
Let me know if there are any issues or errors with this answer.
A: If $T_1,T_2,...$ are return times to the origin then (it is well known that) $T_1,T_2-T_1,...,T_{n+1}-T_n,...$ are independent and identically distributed. The sum of the first $n$ of these i.i.d. random variables is $T_n$. Now use the following basic fact:
If $U$ and $V$ are independent then the generating function of $U+V$ is the product of the generating functions of $U$ and $V$. 
