# Formula for Lattice Paths from $(0,0)$ to $(n,n)$ entirely contained in the half-plane $y ≥ x − 2$

We want to find a formula (not involving $$\prod$$ or $$\sum$$) for the number of lattice paths between $$(0, 0)$$ and $$(n, n)$$ which are entirely contained in the half-plane $$y ≥ x − 2$$. For example, for $$n = 3$$ the number of such lattice paths is 19.

I started by noticing that this contains all of the paths that are contained in the upper half-plane $$y ≥ x$$ which is simply the Catalan number $$C_n$$. By rigorously finding the number of lattice paths subject to this condition for a few for $$n$$, I am fairly confident that the formula is $$C_n+C_{n+1}$$, but I am unsure how to get this extra term. I've tried using Dyck paths but nothing is coming to me. Any help would be great!

I find it easier to think in terms of paths from $$\langle 0,0\rangle$$ to $$\langle 2n,0\rangle$$ up-steps $$\langle 1,1\rangle$$ and down-steps $$\langle 1,-1\rangle$$. In those terms we want the number of paths that do not drop below the line $$y=-2$$. Consider a ‘bad’ path $$\pi$$, one that does drop below that line. There is a first point $$\langle k,-3\rangle$$ at which it does so. Reflect the rest of $$\pi$$ in the line $$y=-3$$ to get a path $$\pi'$$. If the last $$n-k$$ steps of $$\pi$$ consist of $$r$$ up-steps and $$s$$ down-steps, then $$r-s=3$$, and $$r+s=n-k$$. The last $$n-k$$ steps of $$\pi'$$ will consist of $$s$$ up-steps and $$r$$ down-steps, so $$\pi'$$ will terminate at $$\langle 2n,-6\rangle$$, and if $$\pi'$$ is any path from $$\langle 0,0\rangle$$ to $$\langle 2n,-6\rangle$$, we can recover a unique bad path $$\pi$$ that gives rise to it in this way. A path from the origin to $$\langle 2n,-6\rangle$$ must have $$n-3$$ up-steps and $$n+3$$ down-steps, so there are $$\binom{2n}{n-3}$$ of them and therefore $$\binom{2n}{n-3}$$ bad paths. Since there are $$\binom{2n}n$$ paths altogether, there are
$$\binom{2n}n-\binom{2n}{n-3}$$
paths that never drop below the line $$y=-2$$.