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.
 A: 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.

A: The start of a proof i demonstrated in the OP it seems like you can finish it and prove that $A_n = C_n$ the $n$th catalan number. I got a handout from my professor saying it can be done.
$A_0 = C_0 = 1$. It suffices to prove 
$$A_n = \sum_{m=1}^{n} A_{m-1}A_{n-m} \:\:\:\:\:\:\:\:\:(1)$$
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\:\:\:\:\:\:\:\:\:(2)$$
And let $A(n,n)$ be the number of sequences of length $n$ for which
$$a_i > 0 \:\:\text{for all}\:\: i = 2,...,n \:\:\:\:\:\:\:\:\:(3)$$
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 \:\:\:\:\:\:\:\:\:(4)$$
First suppose $1 \leq m \leq n-1$ and let $a_1...a_n$ be one of the $A(n,m)$ sequences satisfying $(2)$. The subsequence $a_{m+1}...a_n$, of length $n-m$, satisfies exactly the same condition as at the outest, hence there are $A_{n-m}$ possibilities for it. 
Since $a_2 > 0$ and $a_2 \leq a_1 + 1$, we must have $a_2 = 1$. We also know that $a_i \geq 1$ for $i = 2,...,m$. So if we let $b_i = a_i - 1$ for $i = 2,...,m$, then the subsequence $b_2...b_m$, of length $m-1$, satisfies exactly the same conditions as at the outset. Hence there are $A_{m-1}$ possibilities for it, and hence in turn for the subsequence $a_2...a_m$. Finally, an application of the multiplication principle verifies $(4)$.
There remains the case $m=n$. We must verify that $A(n,n)=A_{n-1}A_0 = A_{n-1}$. 
Let $a_1...a_n$ be one of the $A(n,n)$ sequences satisfying $(3)$. Since $a_2 > 0$ and $a_2 \leq a_1 + 1$, we must have $a_2 = 1$. We also know that $a_i \geq 1$ for $i = 2,...,n$. Hence, letting $b_i := a_i -1$ for $i = 2,...,n$ the sequence $b_2...b_n$, of length $n-1$, satisfies exactly the same conditions as at the outset. Hence there are $A_{n-1}$ possibilities for it, hence so also for the sequence $a_2...a_n$.
$$\tag*{$\Box$}$$
