Number of parenthesizations and Catalan numbers I read in CLRS that the number of possible parenthesizations for a product of $n$ matrices is given by the recursive formula:

$$
    P(n)= 
\begin{cases}
    1 &amp; \text{if } n = 1,\\
    \sum^{n-1}_{k=1} P(k)P(n-k)              &amp; \text{if } n \ge2.
\end{cases}
$$

This comes from the following two facts:


For $n=1$ there is only only item, so only one way to fully parenthesize a matrix product.
For $n\geq2$ a fully parenthesized matrix product is the product of two fully parenthesized subproducts, and the split between the two subproducts may occur between the $k$th and $(k+1)$st matrices for any $k=1,2,\ldots, n-1$.


So far so good. 

Now, I know that $\sum^{n-1}_{k=1} P(k)P(n-k)$ has a strong relationship with Catalan numbers, and I'm hoping to establish that relationship with precision. 

For background, Catalan numbers are defined as a sequence of the following form:

$${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0,}$$

where a term in the sequence is also known to follow the alternative expression: $C_n={\tfrac {1}{n+1}}{\tbinom {2n}{n}}.$



Expressing the original recurrence in terms of Catalan numbers shouldn't be hard, but the differences in summation and sequence indices are making it difficult for me. What's a good way to rearrange these types of Eqs. to re-express e.g. the first Eq. as a function of the second one?
Define function $Q:\mathbb N\to\mathbb N$  such that $Q(n)=P(n+1)$ for all $n\ge 0$. Or, what is equivalent, $P(n)=Q(n-1)$ for all $n\ge 1$.

We have $$Q(0)= P(0+1)=P(1)=1.\quad\quad\quad\quad\quad\quad\quad\quad$$

Also, for $n\ge0$,
$$\begin{aligned}
  Q(n+1)&amp;=P(n+2)\\
   &amp;=\sum^{(n+2)-1}_{k=1} P(k)P((n+2)-k)\\
   &amp;=\sum^{n+1}_{k=1} Q(k-1)Q(n+1-k)\\
   &amp;\stackrel{k=i+1}{=\!=\!=\!=}\sum^{n}_{i=0} Q((i+1)-1)Q(n+1-(i+1))\\
   &amp;=\sum^{n}_{i=0} Q(i)Q(n-i).\\
\end{aligned}$$

We see that $Q(\cdot)$ and the Catalan numbers $C(\cdot)$ share the same initial condition and the same recurrence relation. So, we have, for all $n\ge0$,
$$ Q(n) = C(n).$$
So, for all $n\ge 1,$
$$P(n)=Q(n-1)=C(n-1)={\tfrac {1}{n}}{\tbinom {2(n-1)}{n-1}}$$

Exercise. Define function $D$ such that $D(n)=C(n-1)$ for $n\ge1$. Show that $D(n)=P(n)$ for $n\ge1$, assuming that you have not seen the deduction above.