Consider a type of lattice paths starting at $(0,0)$ where each step consists of moving either north, east, or northeast and never goes below the line $y=x$. The path ends at $(n,n)$. We use $a_n$ to denote the number of such paths. I'm trying to find a recurrence relation for $a_n$.
If we let $P(x,y)$ be the number of paths to $(x,y)$, we can write $a_n$ as the sum of $a_{n-1}$ and $P(n-1,n)$ [remember that $P(n,n-1)$ is 0 since it's under $y=x$]. I thought about continuing to expand $P(n-1,n)$ into a sum of $P(0,k)$ where $k \leq n$ which is a function of $n$, and a sum of smaller $a_i$ but that just seems messy and kind of defeats the purpose of a recurrence relation. Is there any other way to do this?
Best Answer
Hint
The basic idea is to use the same strategy which leads to the recurrence $$ C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k} $$ for the Catalan numbers, defined to be the number of orthogonal paths from $(0,0)$ to $(n,n)$ which stay at or above the diagonal. The idea for that proof is explained in this answer. I encourage you to try to understand that answer, and then try to derive the recurrence for your problem by modifying the strategy there, before reading the solution below.
Solution
Let $A_n$ be the number of paths. Each path will either start with a north step, or a northeast step. The number of paths starting with a northeast step is clearly $A_{n-1}$, so we just need to deal with the north step paths.
The key idea is to consider the first time this path returns to the line $y=x$. Say that this point is $(k,k)$, for some $k\in \{1,\dots,n\}$. This implies that the point right before $(k,k)$ was $(k-1,k)$. That is, we can break the path into these pieces:
An initial north step.
A walk from $(0,1)$ to $(k-1,k)$, which never even touches the diagonal.
An east step from $(k-1,k)$ to $(k,k)$.
A walk from $(k,k)$ to $(n,n)$ which stays at or above the diagonal.
Since points $2$ and $4$ are smaller versions of the same problem, this gives the following recurrence for $A_n$: