$n$ elements. We plot the points $(n,S_n)$, then connect $(n,S_n)$ and $(n+1,S_{n+1})$ with a straight line segment. For example, the random walk that corresponds to the characteristic sequence (0 1 0 1 0 0 -1 0 -1 0 0 0) is in the following Figure \[ran\].

![The random walk that corresponds to the characteristic sequence (0 1 0 1 0 0 -1 0 -1 0 0 0).[]{data-label="ran"}](random.eps){width="10cm"}

We say that there is a **return to the origin** at time $n$, if $S_n=0$.

A random walk is said to have a **first return to the origin** at time $n$, if $n>0$, and $S_{m}\neq 0$ for all $m<n$.

In Figure \[ran\], the first return occurs at time $n=9$.

### Master recursion $1$

First, we start with $f_m(k)$. Suppose the first return occurs at time $i$ and $\max_{0\leq n\leq i} S_n=s$, which means that in the corresponding characteristic sequence, the number of “1” is $s$. For the reason that the length of the subsequence structures list in (5) are all multiplicity of four and condition (2), all the possibilities of $i$ are $i=5,7, \cdots, 4k-3, 4k-1$, we divide it into two cases: $$\begin{aligned}
  \begin{array}{lll}
    \text{Case ~1}: & i_1=4j-3 & 2 \leq j\leq k~,\\
    