Cheap and Secure Web Hosting Provider : See Now

# [Answers] Solution of complex recurrence relation

, ,
Problem Detail:

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

#### Answered By : Yuval Filmus

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$$