The number of cases $(0, 0)$ moves by either $(1,1)$ or $(1,-1)$, in $2n$ steps, without touching $x$-axis again. I was solving combinatorics problems when I ran into this shady statement:
The number of cases $(0, 0)$ moves by either $(1, 1)$ or $(1, -1)$, in $2n$ steps, without touching $x$-axis again is $\binom{2n}{n}$.
I tried in vain to understand this result. It produces a modified Pascal's triangle and it gives the right answer. How to prove this statement using a combinatorical proof?
 A: Let's focus on the scenario where $Y_1=1$. The key is to use refection principle on the next $2n-1$ moves.
There will be 4 all inclusive and mutually exclusive scenarios:


*

*$Y_i>0$ for all $i$

*$Y_n=0$, of course x-axis must have been touched

*$Y_n<0$, of course x-axis must have been touched

*$Y_n>0$ and $\exists i$ s.t. $Y_i=0$, i.e. x-axis is touched


Let $N_i$ be the number of paths that fall in scenario i. 
$N_2=C_{2n-1}^n$
$N_3=\sum_{k=n+1}^{2n-1}C_{2n-1}^k$
With reflection principle, we have $N_3=N_4$.
Since $N_1+N_2+N_3+N_4=2^{2n-1}$, 
$N_1=2^{2n-1}-C_{2n-1}^n-2\sum_{k=n+1}^{2n-1}C_{2n-1}^k=\sum_{k=1}^{2n-1}C_{2n-1}^k-C_{2n-1}^n-\sum_{k=n+1}^{2n-1}C_{2n-1}^k-\sum_{k=1}^{n-2}C_{2n-1}^k=C_{2n-1}^{n-1}=\frac{(2n-1)!}{(n-1)!n!}=\frac{(2n)!}{2(n!)^2}=\frac{C_{2n}^n}{2}$
Now adding the part where $Y_1=-1$, the total is $C_{2n}^n$.
A: It can be done with generating functions, if one knows the generating functions for the Catalan numbers and central binomial coefficients.
Consider first paths that begin with $\langle 1,1\rangle$ and do hit the $x$-axis. Let $k\le n$ be the smallest positive integer such that the path hits the $x$-axis after $2k$ steps. Then the $2k$-th step was $\langle 1,-1\rangle$, and the $2k-2$ steps between the first and the $2k$-th steps form a Dyck path of length $2(k-1)$. There are $C_k$ such paths, where $C_k$ is the $k$-th Catalan number, and there are $2^{n-1-k}$ ways to continue the path after it first returns to the $x$-axis, so there are $2^{n-1-k}C_k$ paths that start with $\langle 1,1\rangle$ and first return to the $x$-axis after $2k$ steps. Doubling this to account for ‘bad’ paths that start with $\langle 1,-1\rangle$, and summing over the possible values of $k$, we find that there are
$$b_n=2\sum_{k=0}^{n-1}2^{2(n-1-k)}C_k$$
bad paths of length $2n$.
Let
$$f(x)=\sum_{n\ge 0}C_nx^n=\frac{1-\sqrt{1-4x}}{2x}\;,$$
the generating function for the Catalan numbers, and
$$g(x)=2\sum_{n\ge 0}4^nx^n=\frac2{1-4x}\;.$$
Then
$$\begin{align*}
\sum_{n\ge 0}b_nx^n&=2\sum_{n\ge 0}\sum_{k=0}^{n-1}4^{n-1-k}C_kx^n\\\\
&=xf(x)g(x)\\\\
&=\frac{1-\sqrt{1-4x}}{1-4x}\\\\
&=\frac1{1-4x}-\frac1{\sqrt{1-4x}}\\\\
&=\sum_{n\ge 0}4^nx^n-\sum_{n\ge 0}\binom{2n}nx^n\\\\
&=\sum_{n\ge 0}\left(2^{2n}-\binom{2n}n\right)x^n\;,
\end{align*}$$
so
$$b_n=2^{2n}-\binom{2n}n\;.$$
Since there are $2^{2n}$ paths of length $2n$ altogether, there must be $\dbinom{2n}n$ that don’t return to the $x$-axis.
