Let $P_{n}$ denote the number of paths in the coordinate plane traveling from $(0, 0)$ to $(n, 0)$ with three kinds of moves: upstep $u = [1, 1]$, downstep $d = [1,-1]$, and flatstep $f = [1, 0]$ with the path always staying above the line $y = 0.$ Let $C_{n}= \frac{1}{n+1}\binom{2n}{n}$ be the $n^{th}$ Catalan number. Prove that $P_{n}= \sum_{i = 0}^\infty \binom{n}{2i}C_{i}$ and $C_{n}= \sum_{i = 0}^{2n}(-1)^{i}\binom{2n}{i}P_{2n-i}.$

HIDE: Solution to Part 1 Let a path string, $S_{k}$, denote a string of $u, d, f$ corresponding to upsteps, downsteps, and flatsteps of length $k$ which successfully travels from $(0, 0)$ to $(n, 0)$ without passing below $y = 0.$ Also, let each entry of a path string be a slot. Lastly, denote $u_{k}, d_{k}, f_{k}$ to be the number of upsteps, downsteps, and flatsteps, respectively, in $S_{k}.$ Note that in our situation, all such path strings are in the form $S_{n},$ so all our path strings have $n$ slots. Since the starting and ending $y$ values are the same, the number of upsteps must equal the number of downsteps. Let us observe the case when there are $2k$ downsteps and upsteps totally. Thus, there are $\binom{n}{2k}$ ways to choose the slots in which the upsteps and the downsteps appear. Now, we must arrange the downsteps and upsteps in such a way that $d_{n}= u_{n}$ and a greater number of upsteps preceed downsteps, as the path is always above $y = 0$. Note that a bijection exists between this and the number of ways to binary bracket $k$ letters. The number of binary brackets of $k$ letters is just the $k^{th}$ Catalan number. We then place the flatsteps in the rest of the slots. Thus, there are a total of $\sum_{k = 0}^\infty \binom{n}{2k}C_{k}$ ways to get an $S_{n}.$