# Solving recursion of a complex function

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

• If we start with $f_i(0)=1=g(0)$ we get all $f_i(h)=g(h)$. Then we get a simpler recurrence relation $$g(h+1)=2g(h)[\sum_{i=0}^{h} g(i)]$$. From this we can make a differential equation $\frac{\text{d}^2\text{ln}(g(x))}{\text{d}x^2}=2g(x)$. May 20, 2020 at 4:26
• Sorry, I forgot to add the base cases when I posted the question. May 20, 2020 at 5:35

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

• Thank you for your time and clear explanation. I just have a question regarding $$G_h'(x) - G_{h-1}'(x) = G_{h-1}(x/2)^2 - G_{h-2}(x/2)^2.$$ From the lhs I get $$\sum_{n\geq 1} (g_n(h)-g_n(h-1) ) \frac{x^{n-2}}{(n-2)!}$$ assuming $$G_h'(x) = \frac{d(G_h(x))}{dx}$$ and I am not too sure how this equals to $$G_{h-1}(x/2)^2 - G_{h-2}(x/2)^2$$. May 20, 2020 at 18:16
• Not sure if this is usable, but for the generating function ${\mathcal G}(x,z):=\sum_hG_h(x)z^h$ from a formula for Hadamard product your relations give$$\frac\partial{\partial x}{\mathcal G}(x,z)=z\int_0^1{\mathcal G}(\frac x2,\sqrt ze^{2\pi it}){\mathcal G}(\frac x2,\sqrt ze^{-2\pi it})dt$$ May 20, 2020 at 19:50
• @KokoNanahji: This is just an application of the formula for the product of two exponential generating functions. May 20, 2020 at 23:53
• Ok, sounds good. Thank you very much for your help May 21, 2020 at 0:57
• @მამუკაჯიბლაძე: Good point, thanks! May 21, 2020 at 3:05