lattice paths with maximum vertical height

Question

what are the number of lattice paths consisting of $n$ moves of the form $(x+1, y+1)$ or $(x+1, y-1)$ starting from $(0, 0)$ where the distance between vertical extremes is $<4$?

Answer 1

For any $k,l>0$, let $$ P_{k,l}(n)=\{\text{paths with $n$ steps which never hit $y=-k$ or $y=l$}\} $$ I will sometimes suppress the dependence on $n$ for readability. You want to compute $$ |P_{1,4}\cup P_{2,3}\cup P_{3,2}\cup P_{1,4}| $$ This can be computed in terms of the individual terms $P_{k,l}$ using the principle of inclusion-exclusion. This turns out to be $$ |P_{1,4}|+|P_{2,3}|+|P_{3,2}|+|P_{4,1}|-|P_{1,3}|-|P_{2,2}|-|P_{3,1}|\tag{*} $$ Now, $P_{2,2}(n)$ and $P_{3,1}(n)$ are pretty easy to calculate. For example, $P_{2,2}(n)=2^{\lceil n/2\rceil}$, since a valid path simply bounces from the $y$ axis to either $y=-1$ or $y=1$ a total of $\lceil n/2\rceil$ times. Similarly, $P_{3,1}(n)=P_{1,3}(n)=2^{\lfloor n/2\rfloor}$.

Strangely enough, $P_{2,3}(n)$ can be expressed in terms of the Fibonacci numbers! The key insight is this:

• If a path in $P_{2,3}(n)$ starts with a down-step, then it must be followed by an up-step, else it would hit $y=-2$. Afterwards, there are $n-2$ steps starting from the same starting position, which can be completed in $P_{2,3}(n-2)$ ways.

• If a path in $P_{2,3}(n)$ starts with an up-step, then what follows thereafter is a path staying between $y=2$ and $y=-1$ starting at $y=1$. Reflecting through the line $y=1/2$, this is equivalent to starting at $y=0$ and staying between $y=-1$ and $y=2$; the number of ways to do this is counted by $P_{2,3}(n-1)$.

Therefore, $P_{2,3}(n)=P_{2,3}(n-1)+P_{2,3}(n-2)$, which together with the base cases $P_{2,3}(0)=1$ and $P_{2,3}(1)=2$ implies $P_{2,3}(n)=F_{n+2}$.

Since it is easy to see $P_{1,4}(n)=P_{2,3}(n-1)$, we can use all of this work to fill in $(*)$, obtaining $$ 2F_{n+1}+2F_{n+2}-2\cdot 2^{\lfloor n/2\rfloor}-2^{\lceil n/2\rceil}=\boxed{2F_{n+3}-2\cdot 2^{\lfloor n/2\rfloor}-2^{\lceil n/2\rceil}} $$

---

As an afterthought, I think there is a way to generalize to where the forbidden difference is any positive number $d$, where in your case $d=4$. Using the inclusion-exclusion idea in this post, and the formula in my other answer, I bet you can write the number of paths as a complicated linear combination of many binomial coefficients. Maybe this can also yield a compact expression without summations, I do not know.