Three-term Motzkin recurrence On Wikipedia, it says that the Motzkin numbers are given by the recurrence
$$M_n = M_{n-1} + \sum_{k=0}^{n-2} M_kM_{n-2-k} = \frac{2n+1}{n+2}M_{n-1}+\frac{3n-3}{n+2}M_{n-2},$$
with $M_0 = M_1 = 1$. While I was able to convince myself via a program that this is true, I am not quite seeing how the formula with the sum equals the formula on the right. Any help would be appreciated!
 A: I do not know of a simple reason why the first recurrence relation implies the second, but I do have a proof.
The recurrence
$$
\begin{align}
M_0&=1,\\
M_n&=M_{n-1}+\displaystyle\sum_{n=0}^{n-2}M_iM_{n-2-i}\qquad (n\ge1)\tag1
\end{align}
$$
implies the generating function equation
$$
M(x)=1+xM(x)+x^2M(x)^2\tag2
$$
where $M(x)=\sum_{n\ge 0}M_nx^n$. This allows you to determine $M(x)$:
$$
M(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}\tag3
$$
You can then show that $M(x)$ satisfies the differential equation
$$
(3x^3+2x^2-x)M'(x)+(3x^2+3x-2)M(x)=-2\tag4
$$
by plugging $M(x)$ into the above. Finally, plugging the power series representation $M(x)=\sum_{n\ge 0}M_nx^n$ into that differential equation, and rearranging, you can prove that
$$
(n+2)M_n=(2n+1)M_{n-1}+(3n-3)M_{n-2},\qquad (n\ge 1)\tag5
$$
which is exactly the second recurrence.

The only mysterious step in this proof is $(3)\implies (4)$. Where did that differential equation come from? I found it by working backwards, knowing that it is exactly the differential equation which would imply $(5)$. I imagine that there must be a way to show that $(2)$ implies $(4)$ directly, perhaps using the Lagrange inversion formula, but I do not know.
A: I can't fit this into a comment, so I will use this answer to fill the gap of getting from $(3)$ to $(4)$ in Mike Earnest's proof. Let $M=M(x)$ for more compact notation. Starting from
$$
M=1+xM+x^2M^2, \tag{1} \label{fe}
$$
we can either add $xM$ to both sides or subtract $3xM$ from both sides to get
$$
(1+x)M=(1+xM)^2, \quad (1-3x)M=(1-xM)^2,
$$
and therefore,
$$
\left(\frac{1+xM}{1-xM}\right)^2=\frac{1+x}{1-3x}.
$$
Taking logarithmic derivative of both sides, we get
$$
\frac{1}{(1-3x)(1+x)}=\frac{(xM)'}{1-(xM)^2}.
$$
But $(xM)'=xM'+M$ and $1-x^2M^2=2-M+xM$ from \eqref{fe}. Thus, we have
$$
(1-3x)(1+x)(xM'+M)=2-M+xM,
$$
which, after a bit of algebra, yields Mike's equation $(4)$.
