# Finding general term for a given sequence

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.

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)$$.
• Thank You for your help, S.Dolan. I understood the proof by generating functions. Can you please help me in the inductive step, if I try mathematical induction (Even in the original recursion for Catalan numbers will do $C_{n+1}=\sum_{r=0}^nC_rC_{n-r}$). There is no proof by induction given on wikipedia – Martund Jan 11 at 15:52