Consider the sequence defined by $a_0 = a_1 = 1$ and $a_{n+2 } = a_{n+1} + \sum_{k=0}^n a_k a_{n-k}$ for $n\ge 0$. Prove that $a_n = \sum_{k=0}^{\lfloor n/2\rfloor} 1/(k+1) {2k\choose k} {n\choose 2k}$.
The $\sum_{k=0}^n a_k a_{n-k}$ term in the recurrence relation for $a_{n+2}$ reminds me of the Catalan numbers, as does the ${2k\choose k}/(k+1)$ term in the proposed formula for $a_n$. So I think it might be useful to use properties of Catalan numbers to solve this problem (e.g. the generating function for the Catalan numbers $f(x)$ satisfies $xf(x)^2 - f(x)+1=0$). It might be useful to find an explicit formula for the generating function $f(x) = \sum_{n\ge 0} a_n x^n$, and this may be related to that of the Catalan numbers in some way. But the given recurrence seems very hard to work with, as well as the stated formula. Is there some way to simplify the formula? To simplify the recurrence, one trick that's used is to substitute $n+1$ for n in the recurrence relation for a given sequence and then subtract common terms. But there don't appear to be a lot of common terms in $a_{n+1} + \sum_{k=0}^n a_k a_{n-k}$ and $a_{n+2} + \sum_{k=0}^{n+1} a_k a_{n+1-k}$. I'm not sure if induction is useful.
Starting from the recurrence we have for the generating function $M(z)$ that
$$[z^{n+2}] M(z) = [z^{n+1}] M(z) + [z^n] M(z)^2.$$
Multiply by $w^n$ and sum to infinity to get
$$\sum_{n\ge 0} w^n [z^{n+2}] M(z) = \sum_{n\ge 0} w^n [z^{n+1}] M(z) + M(w)^2$$
or
$$w^{-2} \sum_{n\ge 0} w^{n+2} [z^{n+2}] M(z) = w^{-1} \sum_{n\ge 0} w^{n+1} [z^{n+1}] M(z) + M(w)^2$$
which is
$$w^{-2} (M(w) - w - 1) = w^{-1} (M(w)-1) + M(w)^2.$$
Solve this to obtain
$$M(w) = \frac{1-w-\sqrt{1-2w-3w^2}}{2w^2}$$
which is indeed OEIS A001006, Motzkin numbers. Note that we get
$$\frac{1}{M(w)} = \frac{2w^2}{1-w-\sqrt{1-2w-3w^2}} \\ = 2w^2 \frac{1-w+\sqrt{1-2w-3w^2}}{(1-w)^2-(1-2w-3w^2)} = - w^2 \frac{-1+w-\sqrt{1-2w-3w^2}}{2w^2} \\ = - w^2 \left(M(w) - \frac{1}{w^2} + \frac{1}{w}\right) = 1-w-w^2 M(w).$$
On the other hand we have working with
$$\overset{\sim}{M}(w) = \sum_{n\ge 0} w^n \sum_{k=0}^{\lfloor n/2\rfloor} \frac{1}{k+1} {2k\choose k} {n\choose 2k}$$
that
$${n\choose 2k} {2k\choose k} = \frac{n!}{(n-2k)! \times k! \times k!} = {n\choose k} {n-k\choose n-2k}$$
and obtain
$$\overset{\sim}{M}(w) = \sum_{n\ge 0} w^n \sum_{k=0}^{\lfloor n/2\rfloor} \frac{1}{k+1} {n\choose k} {n-k\choose n-2k} \\ = \sum_{n\ge 0} w^n [z^n] (1+z)^n \sum_{k\ge 0} \frac{1}{k+1} {n\choose k} (1+z)^{-k} z^{2k}.$$
Here we have extended to infinity due to the coefficient extractor in $z$. Continuing,
$$\overset{\sim}{M}(w) = \sum_{n\ge 0} \frac{w^n}{n+1} [z^n] (1+z)^n \sum_{k\ge 0} {n+1\choose k+1} (1+z)^{-k} z^{2k} \\ = \sum_{n\ge 0} \frac{w^n}{n+1} [z^n] (1+z)^{n+1} z^{-2} \sum_{k\ge 0} {n+1\choose k+1} (1+z)^{-k-1} z^{2(k+1)} \\ = \sum_{n\ge 0} \frac{w^n}{n+1} [z^{n+2}] (1+z)^{n+1} \left(-1 + \left[ 1 + \frac{z^2}{1+z} \right]^{n+1}\right).$$
The contribution from the minus one term is zero and we find for the inner term
$$[z^{n+2}] (1+z)^{n+1} \left[ 1 + \frac{z^2}{1+z} \right]^{n+1} = [z^{n+2}] [1+z+z^2]^{n+1}.$$
The contribution from $z$ is
$$\;\underset{z}{\mathrm{res}}\; \frac{1}{z^2} \frac{1}{z^{n+1}} [1+z+z^2]^{n+1}.$$
Now put $z= v M(v)$ so that $z/(1+z+z^2) = v$ and $dz = ( M(v) + v M'(v)) \; dv$ to get
$$\;\underset{v}{\mathrm{res}}\; \frac{1}{v^2 M(v)^2} \frac{1}{v^{n+1}} (M(v)+vM'(v)) = - \;\underset{v}{\mathrm{res}}\; \frac{1}{v^{n+1}} \left(\frac{1}{v M(v)}\right)'.$$
We thus have
$$\overset{\sim}{M}(w) = - \sum_{n\ge 0} \frac{w^n}{n+1} \;\underset{v}{\mathrm{res}}\; \frac{1}{v^{n+1}} \left(\frac{1}{v M(v)}\right)'$$
so that
$$w \overset{\sim}{M}(w) = - \sum_{n\ge 0} \frac{w^{n+1}}{n+1} [v^n] \left(\frac{1}{v M(v)}\right)' \\ = - \sum_{n\ge 0} \frac{w^{n+1}}{n+1} [v^n] \left(\frac{1}{v}-1-vM(v)\right)' = w M(w)$$
and we finally have
$$\overset{\sim}{M}(w) = M(w)$$
as desired.