# Solution of complex recurrence relation

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$$
Can you explain how did you get $2(P-cx)=P^2$ from identity 1. And, what is the intuition behind choosing this generating function? – Sayan Bandyapadhyay May 10 '14 at 17:08
For my first question, in particular I can't see why you are subtracting $cx$. As $T(0)=0$, I am getting $2P=P^2$. – Sayan Bandyapadhyay May 10 '14 at 17:51
I am subtracting $cx$ since identity (1) fails for $k = 1$, which in fact produces $0$ instead of $T(1)$. For further information, I suggest checking out the book generatingfunctionology. I'm using an exponential generating function since then $P^2$ corresponds to the convolution in (1) with the weights $\binom{k}{i}$. If identity (1) didn't have these weights, I would use ordinary generating functions. – Yuval Filmus May 11 '14 at 0:10