Proof of Motzkin numbers recurrence I know the Motzkin numbers are given as $$M_n=\sum_{k=0}^{\lfloor n/2\rfloor}{n \choose 2k}C_k,$$ where $$C_k=\frac{1}{1+k}{2k\choose k}.$$
The recurrence relation is given as $M_n=M_{n-1}+\sum_{k=0}^{n-2}M_kM_{n-2-k}$. Is there a direct way to prove this recurrence using either Pascal's identity or summation by parts?
 A: One possible approach starts from
$$M_n = \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} C_k.$$
This is
$$\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose n-2k} C_k
\\ =  \sum_{k=0}^{\lfloor n/2\rfloor} C_k [z^{n-2k}] (1+z)^n C_k
= [z^n] (1+z)^n  \sum_{k=0}^{\lfloor n/2\rfloor} C_k z^{2k}.$$
Now  when  $2k\gt n$  there  is  no  contribution to  the  coefficient
extractor and hence we may extend the sum to infinity:
$$[z^n] (1+z)^n  \sum_{k\ge 0} C_k z^{2k}.$$
Using the generating function of the Catalan numbers this becomes
$$[z^n] (1+z)^n  \frac{1-\sqrt{1-4z^2}}{2z^2}$$
which is
$$\mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
(1+z)^n  \frac{1-\sqrt{1-4z^2}}{2z^2}.$$
With $z/(1+z) = w$ we have $z = w/(1-w)$ and $dz = 1/(1-w)^2 \; dw$
and obtain
$$\mathrm{Res}_{w=0}
\frac{1}{w^n} \frac{(1-w)^3}{2w^3} (1-\sqrt{1-4w^2/(1-w)^2})
\frac{1}{(1-w)^2}
\\ = \mathrm{Res}_{w=0}
\frac{1}{w^{n+1}} \frac{1-w-\sqrt{1-2w-3w^2}}{2w^2}.$$
This shows that
$$M_n = [w^n] \frac{1-w-\sqrt{1-2w-3w^2}}{2w^2},$$
which is also the LHS of the recurrence. We get for the RHS
$$[w^{n-1}] \frac{1-w-\sqrt{1-2w-3w^2}}{2w^2}
+ [w^{n-2}] \frac{(1-w-\sqrt{1-2w-3w^2})^2}{4w^4}
\\ = [w^{n}] \frac{2w-2w^2-2w\sqrt{1-2w-3w^2}}{4w^2}
+ [w^{n}] \frac{(1-w-\sqrt{1-2w-3w^2})^2}{4w^2}.$$
The numerator is
$$2w-2w^2-2w\sqrt{1-2w-3w^2} + 2 - 4w - 2w^2
- 2(1-w)\sqrt{1-2w-3w^2}
\\ = 2 - 2w - 4w^2 - 2 \sqrt{1-2w-3w^2}.$$
We therefore conclude that the RHS is
$$[w^n] \left(-1 + \frac{1-w-\sqrt{1-2w-3w^2}}{2w^2}\right),$$
which is the same as the LHS when $n\ge 2,$ as claimed.
