Prove that $A_n = C_n$, the $n$th Catalan number. 
Problem:
For each $n \geq 0$ let $A_n$ be the number of sequences
$a_1a_2...a_n$ of non-negative integers that satisfy
$$0 \leq a_{i+1} \leq a_i + 1, \:\:\: i = 0,...,n-1, \:\:\: a_1 = 0$$
Prove that $A_n = C_n$, the $n$th Catalan number, for each $n \geq 0$.


Proof:
$A_0 = C_0 = 1$. It suffices to prove
$$A_n = \sum_{m=1}^{n} A_{m-1}A_{n-m}$$
for each $n > 0$.
For each $m = 1,...,n-1$, let $A(n,m)$ be the number of sequences
$a_1...a_n$ of length $n$ for which
$$a_{m+1} = 0, \:\:\: a_i > 0 \:\:\text{for}\:\: i = 2,...,m$$
And let $A(n,n)$ be the number of sequences of length $n$ for which
$$a_i > 0 \:\:\text{for all}\:\: i = 2,...,n$$
Now
$$A_n = \sum_{m=1}^{n} A(n,m)$$
So we are done if we can prove that
$$A(n,m) = A_{m-1}A_{n-m} \:\:\text{for}\:\: m = 1,...,n$$
Here i am stuck.

You have a reasonable idea, but that way of decomposing the sequences doesn’t seem to work. Instead of simply telling you what will work, I’m going to try to point you in the right direction with a hint that mimics the way I thought about the problem just now.
I’ve made a table of the sequences of lengths $0,1,2,3$ and $4$ that satisfy the conditions (ignore the colors for now):
$$\begin{align*}
&n=0:\lambda\\
&n=1:0\\
&n=2:0\color{red}0\mid0\color{blue}1\\
&n=3:0\color{red}{00},0\color{red}{01}\mid0\color{blue}1\color{red}0\mid0\color{blue}{11},0\color{blue}{12}\\
&n=4:0\color{red}{000},0\color{red}{001},0\color{red}{010},0\color{red}{011},0\color{red}{012}\mid 0\color{blue}1\color{red}{00},0\color{blue}1\color{red}{01}\mid 0\color{blue}{11}\color{red}0,0\color{blue}{12}\color{red}1\mid0\color{blue}{111},0\color{blue}{112},0\color{blue}{120},0\color{blue}{122},0\color{blue}{123}
\end{align*}$$
Here $\lambda$ is the empty sequence. You’ll notice that for $n=2,3,4$ I’ve broken the list of sequences into groups separated by vertical strokes; take a look at the lengths of those groups. For $n=4$ we have groups of $5,2,2$, and $5$, and 
$$\begin{align*}
C_4&=C_3C_0+C_2C_1+C_1C_2+C_0C_3\\
&=5\cdot1+2\cdot1+1\cdot2+1\cdot5\\
&=5+2+2+5\;.
\end{align*}$$
You can check that something similar happens when $n=2$ and $n=3$. The problem now is to see how I made the divisions into groups. The colors are the key here. I would concentrate first on the $n=4$ case, since it shows most clearly what’s going on. Here is a first
HINT:


*

*Ignore the black leading $0$.  

*Read red digits exactly as they are.  

*Subtract $1$ from each blue digit.  

*It may help to think of $0\color{red}{001}$ and $0\color{blue}{112}$ as $0\color{blue}{\lambda}\color{red}{001}$ and $0\color{blue}{112}\color{red}\lambda$, respectively.

