How to get to Catalan numbers recurrence relation from couting lattice paths

Question

I'm currently taking a probability theory class and I've been stuck on a problem where I can find the solution using one method but I dont get how my TA got to the catalan numbers from counting, so heres how it goes (I didn't find any awnsers on HOW you get the recurrence relation i.e the reasonning that gets to it):

Suppose we place someone on a lattice $\mathbb{Z}^2_{\geq0}$ and we want to count how many ways he can get to$ (n,n)$, such that $n\in \mathbb{N}_{\geq 1}$ and the the person cant pass trough the diagonal $y=x$ and he can only walk northward or westward on that lattice.

And here's my thoughts so far:

Attempt on a solution using recurrence relation

Let $C_k$ be the numbers of valid path from $(0,0)$ to $(k,k)| k\in \mathbb{N}_{\geq 1}$

Then $C_0 = 1$ (because there's only one way to stay where you are... you stay)

Moreover, if the person touch the diagonal at $(k,k)$, then he has $C_{n-k}$ ways to get to $(n,n)$ if he doesn't touch the diagonal again (because its as if (k,k) was the new origin... I'm not sure from here).

So by the product principle of counting, for every $C_k$ ways he can get to $(k,k)$ he has $C_{n-k}$ implies that he has $(C_{n-k})( C_k)$ ways to get to $(n,n)$.

However, my TA only wrote,

"let's consider the first time he touches the diagonal, then he has

$(C_0)(C_n) + (C_1)(C_{n-1}) + ... + (C_n)(C_0) = C_{n+1}$

So is my way of reasonning a good beginning and how do we get from his first sentence to that relation with a sum and $C_{n+1}$

Thank you so much

Answer 1

Take any valid catalan path $P$ from $(0,0)$ to $(n+1,n+1)$. Any such path has exactly $2(n+1)$ steps. This path ultimately must hit the diagonal at time $2(n+1)$. We're going to split these paths based on the times at which they touch the diagonal, prior to $2(n+1)$.

Let $t=t(P)$ denote the index of the last-time prior to $2n+1$ that $P$ touches the diagonal, with the convention that $t=0$ if the path never touched the diagonal. It's easy to see that $t$ must be even, i.e. $t=2k$. This partitions all possible paths $P$ into $n$ classes: $k=0,2,4,\cdots 2n$

Then any path can be mapped to such a $t$, hence it suffices to count the number of paths by figuring out how many paths belong to each class $t$. You found that for $t=2k$, it's $C_kC_{n-k}$, hence:

$$C_{n+1}=\sum_{k=0}^{n} C_kC_{n-k}.$$

Answer 2

Total Catalan paths from $(0,0)$ to $(n+1,n+1)$ is equal to $C_{n+1}$

Let us split all Catalan paths in some mutually exclusive paths based on the first time, they meet diagonal $y=x$ after $(0,0).$

Let use take a Catalan path meeting $y=x$ after $(0,0)$ first time at $(r,r),\,r$ can be $1,2,,3\cdots,n+1.$ This path can be thought as starting from $(1,0)$ going to $(r,r-1)$ and never crossing $y=x-1$ then from $(r,r-1)$ to $(r,r)$ and finally from $(r,r)$ to $(n+1,n+1)$

Number of paths from $(1,0)$ to $(r,r-1)$ and not crossing $y=x-1$ is equal to $ C_{r-1}$

Number of paths from $(r,r-1)$ to $(r,r)$ is $1$

Number of paths from $(r,r)$ to $(n+1,n+1)$ is $C_{n+1-r}$

$\implies$ Number of paths meeting y=x after $(0,0)$ first time at $(r,r)$ is $C_{r-1}\times 1\times C_{n+1-r}$

$\implies C_{n+1}=\sum_{r=1}^{n+1} C_{r-1}C_{n+1-r}$