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

  • $\begingroup$ 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)$. $\endgroup$
    – Alapan Das
    May 20, 2020 at 4:26
  • $\begingroup$ Sorry, I forgot to add the base cases when I posted the question. $\endgroup$ May 20, 2020 at 5:35

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

  • $\begingroup$ 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$$. $\endgroup$ May 20, 2020 at 18:16
  • 1
    $\begingroup$ 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$$ $\endgroup$ May 20, 2020 at 19:50
  • $\begingroup$ @KokoNanahji: This is just an application of the formula for the product of two exponential generating functions. $\endgroup$ May 20, 2020 at 23:53
  • $\begingroup$ Ok, sounds good. Thank you very much for your help $\endgroup$ May 21, 2020 at 0:57
  • $\begingroup$ @მამუკაჯიბლაძე: Good point, thanks! $\endgroup$ May 21, 2020 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.