How can I prove $\sum_{i=0}^{n-2} B_iB_{n-i-2} = \sum_{i=1}^{n-1} M_iM_{n-i}$?

Question

I have a recursion $B$ below:

$$\begin{align} B_{n-1} &= \sum_{i=0}^{n-2} B_iB_{n-i-2} \\ B_1 &= 1 \\ B_0 &= 1 \end{align}$$

And another $M$ below:

$$\begin{align} M_n &= \sum_{i=1}^{n-1} M_iM_{n-i} \\ M_2 &= 1 \\ M_1 &= 1 \end{align}$$

How can I show that these two recursions are equal??

Answer 1

It’s just an induction on $n$. Suppose that $M_k=B_{k-1}$ for $k=1,\ldots,n-1$. Then

$$\begin{align*} M_n&=\sum_{k=1}^{n-1}M_kM_{n-k}\\ &=\sum_{k=1}^{n-1}B_{k-1}B_{n-1-k}\\ &=\;...\;. \end{align*}$$

Now just shift the indices. I’ve finished it off in the spoiler-protected block below.

$\sum_\limits{k=0}^{n-2}B_kB_{n-2-k}=B_{n-1}$