Consider the set of all walks with $2k$-many steps on the integer grid starting from the point $n \in \mathbb{Z}$ and turning back to this specific point. Let each walk is of lenght $\pm 2$ and do not allow them to pass through $ n$ unless it is the last step. What is the total number of such walks?
I draw a diagram and count the number of walks through cases when $k$ is small and I claim as a generality that there are $2^{k-1}$ such walks but I cannot prove it. Can you help me?
Without loss of generality, consider starting at $n = 0$, and suppose we take a step of $+1$ to the number $1$. Then the last step will necessarily be a $-1$ from $1$ to $0$, and the remainder of the walk has to take place on the numbers $1, 2, \ldots$. So for these $2k - 2$ steps in the middle, you are actually counting Dyck words:
In this case, you are counting paths of length $2k - 2$, starting and ending at $1$, which are always positive. Since the numbers that count these Dyck paths are the Catalan numbers $C_n$, there are $C_{k-1}$ such paths. And since we could have started with a $+1$ or a $-1$, the answer is $2 \cdot C_{k-1}$.
(For $k = 1, 2, \ldots$ this is the sequence $(2, 2, 4, 10, 28, \ldots)$.)