How to calculate the time complexity of a Catalan-like recurrence by substitution?

Question

I was given the following problem:

Calculate the computational time complexity of the recurrence $$P(n) = \begin{cases} 1 & \text{if } n = 1 \\ \sum_{k=1}^{n-1} P(k) P(n-k) & \text{if } n \geq 2 \end{cases}$$ using the substitution method. Answer: $\Omega(2^n)$.

I have seen there is a closed-form for this recurrence but I am unsure whether it can be used out of the blue or not. I don't know if I have to prove it by deriving it from the recurrence or if there are simpler ways of solving such a problem by mere substitution.

On the other hand, I think substitution is not the right tool to use here. I have tried with both reverse and forward substitution, but in neither approach I could determine the function as with other problems (e.g. QuickSort).

Is it possible to solve this problem with only substitution at all? If so, how can I devise it?

Answer 1

You can use induction. First, check directly that $P(n) \geq 2^{n-2}$ for all $n \leq 4$ (the relevant values are $1,1,2,5$). Now suppose that $P(n) \geq 2^{n-2}$ holds for all $n \leq m$, where $m \geq 4$. Then $$ P(m+1) = \sum_{k=1}^m P(k) P(m+1-k) \geq \sum_{k=1}^m 2^{k-2} 2^{m+1-k-2} \geq m 2^{m+1-4} \geq 2^{m+1-2}, $$ since $m \geq 4$.

Answer 2

For the record, I'll describe here the procedure that I was looking for (after being oriented by my instructor).

1. A closed form was indeed needed to solve the problem. From here, I took this recurrence:

$$P(0) = 1, P(n+1) = \frac{2(2n+1)}{n+2} \cdot P(n)$$

2. Using reverse substitution, and then letting $j = (n-k)+2$, I ended up with

$$P(n) = 2^n \prod_{k=1}^{n} \frac{2(n-k)+1}{(n-k)+2} = 2^n \prod_{j=2}^{n+1} \frac{2j-3}{j} = 2^n \prod_{j=2}^{n+1} \left( 2 - \frac{3}{j} \right)$$

3. I proved by induction that $P(n) \geq 2^n\ \forall\ n \geq 5$, in order to use $n_0 = 5$ in the formal definition of $\Omega[f(n)]$, which for completeness, is

$$\Omega[f(n)] = \{g(n) \mid \exists\ c > 0, n_0 > 0 : 0 \leq cg(n) \leq f(n)\ \forall\ n \geq n_0\}$$

4. Finally, using $n_0 = 5$ and the formal definition, it is shown $P(n) \in \Omega(2^n)$.

If my reasoning is flawed, please leave a comment and I'll edit accordingly.