I am solving a combinatoric question in which I am getting this recurrence relation $$\color{red} {P(n) = 2P(n-1)+\sum_{k=3}^{n-2}P(k)P(n+1-k)}\ \ \ \ \ \ \ \ \ \ \forall n>3$$ $$P(3)=1$$ It is to be shown that the general term is $$P(n)=\dfrac{\binom{2n-3}{n-1}}{2n-3}\ \ \ \ \ \ \ \ \ \forall n\ge3$$ My attempts:
I tried induction but the sum is creating problem. Also, the sum suggests using generating functions (because it is like the coefficient of $x^{n+1}$ when multiplying two polynomials) but I failed here also.
Please help
EDIT
As suggested by S.Dolan in the answer, $P(n)=C_{n-2}$. The post on Wikipedia about Catalan number aptly explains the proof by generating functions. So the question now reduces to
How to prove the formula for Catalan numbers by using induction? Catalan numbers are defined using $C_0=1 $ and $$C_{n+1}=\sum_{r=0}^nC_iC_{n-i}$$
These are Catalan numbers, where your $P(n)$ is $C(n-2)$.
There are a number of proofs of the result you want given in https://en.wikipedia.org/wiki/Catalan_number.
(Including one using generating functions, which is, as you so rightly say, is suggested by the form of the sum.)