Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Do anyone have any idea how to solve this recurrence?$$T(k) = \sum_{i=1}^{k/2} {k \choose i}T(i)T(k-i)$$
I am working with this kind of recurrence for the first time and don't have much idea of how to proceed. But, for beginning I was trying to guess the solution and use substitution method. But, in the guessing part itself I am stuck. It seems like the solution should be exponential to $k$.
Everything becomes much simpler if when $n$ is odd we stop the sum at $\lfloor n/2 \rfloor$, and when $k$ is even we discount the term corresponding to $k/2$ by a half. In that case you can write $$ 2T(k) = \sum_{i=1}^{k-1} \binom{k}{i} T(i) T(k-i) $$ and so, putting $T(0) = 0$, we get that for $k \geq 2$, $$ 2T(k) = \sum_{i=0}^k \binom{k}{i} T(i) T(k-i). \tag{1}$$ (When $k = 1$ this reads $2T(1) = 0$.)
Now define the exponential generating function $$ P = \sum_{n \geq 0} T(n) \frac{x^n}{n!}. $$ Put $T(1) = c$. The identity (1) implies the equation $$ 2(P-cx) = P^2. $$ Solving the quadratic, we obtain $$ P = 1 - \sqrt{1 - 2cx} = 1 - \sum_{n \geq 0} \frac{(2n)!}{(1-2n)(n!)^24^n} (2cx)^n = \sum_{n \geq 1} \frac{(2n)!(c/2)^n}{(2n-1)n!} \frac{x^n}{n!}. $$ We conclude that for $n \geq 1$, $$ T(n) = \frac{(2n)!(c/2)^n}{(2n-1)n!} \sim \frac{1}{\sqrt{2} n} \left( \frac{2c}{e} n \right)^n. $$ The first few terms (starting with $T(1)$) are $$ c,c^2,3c^3,15c^4,105c^5,\ldots $$
