Find a closed formula for the generating function that counts the number of lattice paths from $(0, 0)$ to $(n, 0)$ which never dip below $y=0$ and consist of the moves $(1, 0)$, $(1, 1)$, and $(1, -1)$.
I have been stuck trying to solve this problem and I am not making any progress.
I would prefer hints and outlines about how to solve this problem, rather then a complete solution.
My idea so far is to sum over the possible number of $(1,0)$ moves. Removing these $i (1,0)$ moves would create a situation similar to Dyck paths of length $n-i$ counted by the $(n-i)/2$th Catalan number. The $i (1,0)$ moves can be reinserted in $\binom ni$ ways. However, this results in a formula where the index $i$ must be the same parity as $n$ and I do not know how to continue this idea to a generating function in closed form.
Recall how the generating function for Catalan paths is derived. You look at the first time the path returns to zero. This uniquely factorizes $C_{n}$ as $(\nearrow, C_k,\searrow, C_{n-1-k})$ for some $k$ between $0$ and $n-1$, so that $$ C_n=\sum_k C_kC_{n-1-k}\text{ for }n\ge 1,C_0=1\implies C(x)=1+xC(x)^2 $$ Now let us try to do the same thing with your paths. Let $M_n$ denote the set of paths to $(n,0)$. We almost still have the factorization $$ M_n\stackrel{?}=\bigcup_{k=0}^{n-2}(\nearrow, M_k,\searrow, M_{n-2-k}) $$ by looking at the first time the path returns to zero. However, this only accounts for paths which start with a $\nearrow$. What remains are paths which start with a horizontal step. But in that case, what follows is a legal path of length $n-1$. Therefore, the actual equation is $$ M_n=\;\;(\to, M_{n-1})\;\;+\;\;\bigcup_{k=0}^{n-2}(\nearrow ,M_k,\searrow, M_{n-2-k}) $$
Combined with the base case $M_0=1$, this translates to the generating function equation $$ M(x) = 1+xM(x)+x^2M(x)^2. $$