Form a recurrence relation for catalan numbers, which is the number of ways to paranthesis a product of n+1 matrices.
I know the proof for this using Dyck Paths as a defintion of Catalan Numbers. I got stuck with the idea of solving this question using the above definition of catalan numbers. I was using generating functions to find the a formula for it. Any help in this regard is highly appreciated.
HINT: Any fully parenthesized product of $n+1$ matrices will have exactly one ‘outermost’ multiplication, one that must be done last. For instance, in $(A(BC))(DE)$, it’s the multiplication of $A(BC)$ and $DE$. Another way to say this is that it for some $k$ it must have the form $(X)(Y)$, where $X$ is a product of $k$ matrices, and $Y$ is a product of $n+1-k$ matrices. Thus, if there are $a_k$ ways to parenthesize a product of $k$ matrices, there are $a_ka_{n+1-k}$ ways to parenthesize a product of $n+1$ matrices so that it splits as $(X)(Y)$ for some product $X$ of $k$ matrices and some product $Y$ of $n+1-k$ matrices. Use this observation to express $a_{n+1}$ as a sum of products of the form $a_ia_j$ for suitable $i$s and $j$s, and then use the fact in your first sentence, i.e., that $C_n=a_{n+1}$.