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


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.)

| cite | improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – Martund Jan 11 at 15:52
  • $\begingroup$ I'll have a go now. $\endgroup$ – S. Dolan Jan 11 at 15:57
  • $\begingroup$ I've now had a go and cannot see a way of proving this directly by induction.You could try posting this again asking only for an inductive proof and you might also like to check math.stackexchange.com/questions/3304415 $\endgroup$ – S. Dolan Jan 11 at 16:23
  • $\begingroup$ That answers it, thank you. $\endgroup$ – Martund Jan 11 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.