How to solve this recurrence$f(n)=A\cdot f(n-1)+B\sum{f(i)f(n-i)},\;1\leq i\leq n-1,$ and $f(1)=K$?

Question

$f(n)=A\cdot f(n-1)+B\sum{f(i)f(n-i)} , \;1\leq i\leq n-1,$ and $f(1)=K$.

Is $f(n)$ similar to Catalan number equation $C(n+1)=\sum{C(k)\cdot C(n-k)}$?

If yes then how to solve above recurrence?

Answer 1

For $f(n)=a f(n-1)+b\sum_{i=1}^{n-1}f(i)f(n-i) $ for $n \ge 2$, using generating functions seems appropriate.

Let $F(x) =\sum_{n=0}^{\infty} f(n)x^n $ with $f(0) = 0$.

$\begin{array}\\ F^2(x) &=\sum_{n=0}^{\infty} f(n)x^n\sum_{m=0}^{\infty} f(m)x^m\\ &=\sum_{n=0}^{\infty} x^n\sum_{k=0}^n f(k)f(n-k)\\ &=\sum_{n=1}^{\infty} x^n\sum_{k=1}^{n-1} f(k)f(n-k)\\ \end{array} $

Also, $xF(x) =\sum_{n=0}^{\infty} f(n)x^{n+1} =\sum_{n=1}^{\infty} f(n-1)x^{n} =\sum_{n=2}^{\infty} f(n-1)x^{n} $.

Therefore $F(x)-xf(1) =axF(x)+bF^2(x) $. Letting $F(x) =xG(x) $, this is $xG(x)-xf(1) =ax^2G(x)+bx^2G^2(x) $ or $bxG^2(x)+(ax+1)G(x)+f(1) =0 $.

(Note - I mistakenly had $ax-1$.)

Solving for $G$, $G(x) =\dfrac{1-ax\pm\sqrt{(ax+1)^2-4bxf(1)}}{2bx} =\dfrac{1-ax\pm\sqrt{a^2x^2+2(a-2bf(1))x+1}}{2bx} $.

I'll stop here and let someone else get the coefficients.

(But see below where I go a little further.)

Note that if $a=0$, this is $G(x) =\dfrac{1\pm\sqrt{-4bf(1)x+1}}{2bx} $, so if $a=0, b=1$ this is $G(x) =\dfrac{1\pm\sqrt{-4f(1)x+1}}{2x} $ which gets us into Catalan land.

---

We have $G(x) =\dfrac{1-ax\pm\sqrt{a^2x^2+2(a-2bf(1))x+1}}{2bx} $.

Expanding just the first term, $G(x) =\dfrac{1-ax\pm(1+(a-2bf(1))x+O(x^2))}{2bx} $. For this have $G(0)$ exist, we have to take the negative sign, so $G(x) =\dfrac{1-ax-(1+(a-2bf(1))x+O(x^2))}{2bx} =\dfrac{x(-2a+2bf(1))+O(x^2))}{2bx} =\dfrac{(-a+bf(1))+O(x))}{b} =\dfrac{-a}{b}+f(1)+O(x) $.

To see why the full expansion is so messy, consider that $\sqrt{1+y} =\sum_{k=0}^{\infty} \dfrac{(-1)^{k+1}}{4^k(2k-1)}\binom{2k}{k}y^k $.

Then

$\begin{array}\\ \sqrt{1+ux+vx^2} &=\sum_{k=0}^{\infty} \dfrac{(-1)^{k+1}}{4^k(2k-1)}\binom{2k}{k}(ux+vx^2)^k\\ &=\sum_{k=0}^{\infty} \dfrac{(-1)^{k+1}}{4^k(2k-1)}\binom{2k}{k}x^k(u+vx)^k\\ &=\sum_{k=0}^{\infty} \dfrac{(-1)^{k+1}}{4^k(2k-1)}\binom{2k}{k}x^k\sum_{j=0}^k \binom{k}{j}v^jx^ju^{k-j}\\ &=\sum_{k=0}^{\infty} \sum_{j=0}^k\dfrac{(-1)^{k+1}}{4^k(2k-1)}\binom{2k}{k}x^{k+j} \binom{k}{j}v^ju^{k-j}\\ &=\sum_{n=0}^{\infty} x^n\sum_{j=0}^n\dfrac{(-1)^{n-j+1}}{4^{n-j}(2(n-j)-1)}\binom{2(n-j)}{n-j} \binom{n-j}{j}v^ju^{n-2j} \qquad(k = n-j)\\ \end{array} $

This is what you need (assuming no mistakes on my part) to get the expansion of $f(n)$.

Now I'll really stop.