Note that a product
may be parenthesized in two different ways:
and
. Similarly, there are several different ways to parenthesize
. Two such ways are
and
. Let
be the number of different ways to parenthesize the product
. Show that if
, then
for all integers .
Keep in mind that the sequence is the same as the sequence of Catalan numbers.
I am entirely lost. Please can someone offer some hint or direction of where to begin? I humbly thank you so very much.
The idea is pretty simple: $k$-th summand in $\sum_{k=1}^{n-1} P_k P_{n-k}$ corresponds to the number of parenthesizations of the product $x_1 \cdots x_n$ like this: $(x_1 \cdots x_k)\cdot(x_{k+1} \cdots x_n)$. There are $P_k$ ways to parenthesize the first parenthese, and $P_{n-k}$ to parenthesize the other, so they both give $P_k P_{n-k}$. Try to proceed from here yourself.