# Finding the number of monotonic paths not crossing the diagonal

For great diagrams relating to the Catalan number and the number of monotonic paths not crossing the diagonal, see this: http://en.wikipedia.org/wiki/Catalan_number#Second_proof

So why is the number of monotonic paths not crossing the diagonal the Catalan number?

I understand that through the "reflection method", we arrive at $2n \choose n$ - $2n \choose n-1$ which is indeed the definition of the Catalan number.

However, a definition of the Catalan number is also given by the recurrence relation: $C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0$

Can anyone point out a way to intuitively visualize the solution for the number of monotonic paths not crossing the diagonal in terms of this recurrence relation instead of the explicit formula of the "reflection method" above?

-

Lets put good paths to the sets according to their points $C(m,m)$. We have $C(0,0),\dots,C(n-1,n-1)$. How many paths belong to the set of point $C(m,m)$?
There are $P_m$ ways to go to the point $C(m,m)$. We know that for the rest part of the path we wont touch the diagonal anymore, so that means that our path lies under the line DE. Which means, that for the rest part of the path we have $P_{n-(m+1)}$ ways to do that. So the group of $C(m,m)$ consists of $P_m\cdot P_{n-(m+1)}$ good paths. We may take $m=0,\dots,n-1$ and then the sum of all possible paths is $\sum_{m=0}^{n-1}P_m\cdot P_{n-m-1}=P_n$