Three-term Motzkin recurrence

Question

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!

Answer 1

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.

Answer 2

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)$.