Probability of being back at the origin in an unbiased, bounded random walk Suppose I start at $x=0$ and I walk for $n$ steps, where each step I move left or right with equal probability, but if a step would take me left of $x=0$ I stay put instead (this still counts as taking a step).
What is the probability $p(n)$ I am back at the origin after the $n$ steps?
Counting the number $c(n)$ of such paths is equivalent to counting the number of Dyck words where extraneous ] are allowed; this leads to the recurrence
\begin{align}
c(-1) &= 1\\
c(n) &= \sum_{i=0}^{\lfloor n/2 \rfloor } C_i\, c(n - 2 i - 1)\\
p(n) &= c(n) / 2^n
\end{align}
where $C_i$ is the $i$th Catalan number.
After some long calculations with generating functions I was able to get the following closed-form formula:
\begin{equation}
p(2k+1) = p(2k+2) = \frac{(2k+1)!!}{(2k+2)!!}, \tag{*}
\end{equation}
so that the first few terms of $p(n)$ are $\frac{1}{2}, \frac{1}{2},\frac{3}{8},\frac{3}{8},\frac{5}{16},\frac{5}{16}$,and so on.
The strikingly simple formula (*) suggests there must be a nice combinatorial proof. Is there a way to see this formula without passing through generating functions?
 A: Answer:
$$
p(n)=2^{-n}\binom{n}{\lfloor n/2\rfloor}
$$
To see this, consider a different random walk. This time it is a simple random walk on the integers, so there is no barrier. We label the integers as follows:
$$
\cdots \quad 3\quad 2\quad 1\quad 0\quad 0\quad 1\quad 2 \quad 3\quad\cdots
$$
So there are two copies of the nonnegative integers back to back. I claim that the the probability distribution for the random walk on these labeled integers is exactly the same as the distribution for your random walk with boundary. Indeed, looking at the above, you can see that from either copy of any nonzero integer $j$, you are equally likely to move to $j-1$ or $j+1$, and from either of the zeroes, you are equally likely to move to $0$ or $1$.
For my simple random walk, it is easy to calculate the probability of returning of returning to one of the zeroes after $n$ steps; it is just the formula given at the beginning. Since the two random walks are equal in distribution, this applies to your problem as well.
I guess this can also be written as $(2k+1)!!/(2k+2)!!$ in the case where $n=2k+1$ or $2k+2$, which you should be able to prove by using these formulae for the double-factorial:
$$
(2k)!!=2^k\cdot k!,\qquad (2k+1)!!=\frac{(2k+1)!}{(2k)!!}=\frac{(2k+1)!}{2^k\cdot k!}
$$
