How can I go solving the recurrence relation $T(n) = \sum_{i=1}^{n-1} T(i)T(n-i)$.
Base Case: $T(1) = 1$, $T(2) = 1$
First few terms look like so:
$T(3) = T(1)T(2) + T(2)T(1) = 1 + 1 = 2$
$T(4) = T(1)T(3) + T(2)T(2) + T(3)T(1) = 2 + 1 + 2 = 5$
$T(5) = 14$ $\hspace{1cm}$ $T(6) = 42$ $\hspace{1cm}$ $T(7) = 132$
First order difference where $\Delta T(i) = T(i+1) - T(i)$
$\Delta T(1) = 0$ $\hspace{1cm}$ $\Delta T(2) = 1$ $\hspace{1cm}$ $\Delta T(3) = 3$$\hspace{1cm}$ $\Delta T(4) = 9$
$\Delta T(5) = 28$ $\hspace{1cm}$$\Delta T(6) = 90$
First order differences seem to be growing roughly quicker than $3^n$, which may give a rough lower bound.
Is there a way to solve this relation exactly or produce a rough upper bound. Also after computationally playing with the relation it seems $4^n$ may be one such upper bound.