Proof of Motzkin numbers recurrence

Question

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?

Answer 1

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.