Solving recursion of a complex function

Question

I am trying to find a closed form formula for the following recursive function: $$f_n(h)= \sum_{i=1}^{n-1} \binom{n-2}{i-1} \cdot (0.5)^{n-2} \cdot [ (f_{n-i}(h-1)\cdot \sum_{j=0}^{h-1}f_i(j)) + (f_{i}(h-1)\cdot \sum_{j=0}^{h-2} f_{n-i}(j))] $$ The base cases are the following: $$ f_1(h)= \begin{cases} 1 & h=0 \\ 0 & otherwise \end{cases} \\ f_2(h)= \begin{cases} 1 & h=1\\ 0 & otherwise \end{cases} $$ I have been trying to use the generating functions technique, but I have been unsuccessful so far and I was wondering if anyone has suggestions into how to solve this problem. Thank you for your help in advance

Edit: I added the base cases

Answer 1

Define $g_k(m) := \sum_{j=0}^m f_k(j)$. Then the given recurrence becomes \begin{split} g_n(h)-g_n(h-1) &= 0.5^{n-2} \sum_{i=1}^{n-1}\binom{n-2}{i-1} [(g_{n-i}(h-1)-g_{n-i}(h-2))g_i(h-1)+(g_{i}(h-1)-g_{i}(h-2))g_{n-i}(h-2)] \\ &=0.5^{n-2} \sum_{i=1}^{n-1}\binom{n-2}{i-1} [(g_{n-i}(h-1)g_i(h-1)-g_{i}(h-2)g_{n-i}(h-2)]. \end{split}

Consider the generating function $$G_h(x) := \sum_{n\geq 1} g_n(h) \frac{x^{n-1}}{(n-1)!}.$$ The initial conditions imply that $G_1(x)=1+x$ and $G_2(x)=1+x+\frac{x^2}2+\frac{x^3}{12}$.

Then the recurrence takes form: $$G_h'(x) - G_{h-1}'(x) = G_{h-1}(x/2)^2 - G_{h-2}(x/2)^2$$ or $$G_h'(x) - G_{h-1}(x/2)^2 = G_{h-1}'(x) - G_{h-2}(x/2)^2.$$ Unrolling the last recurrence, we get that for any $h\geq 2$ $$G_h'(x) - G_{h-1}(x/2)^2 = G_{2}'(x) - G_{1}(x/2)^2=0.$$ That is, $$G_h'(x) = G_{h-1}(x/2)^2.$$ It seems that there is no simple expression for the solution to this recurrence, although we may notice that $\lim_{h\to\infty} G_h(x)=e^x$.

P.S. For a fixed $h$, the generating function for $f_n(h)$ can be expressed as $$\sum_{n\geq 1} f_n(h) \frac{x^{n-1}}{(n-1)!} = G_h(x)-G_{h-1}(x).$$