$g(n)=\sum_{i=0}^{n-1}g(i)g(n-i-1)$, and $g(0) = 1$, so which is $g(n)$?

Question

I have an equation that:

$g(n) = g(0)g(n-1)+g(1)g(n-2) + ... + g(n-2)g(1)+g(n-1)g(0)$

And I also know that $g(0)=1$.

How can I derive the close form of function $g(n)$ ?

Answer 1

If we have two power-series $f(x) = \sum a_n x^n$ and $g(x) = \sum b_n x^n$ then the product has the power-series $f(x)g(x) = \sum c_n x^n$ where $c_n = \sum_{i=0}^{n}a_ib_{n-i}$. Now if $a_n = b_n \equiv g_n$ then the defining relation for $g_n$ gives us $c_n = g_{n+1}$.

This motivates us to define the generating function

$$G(x) = \sum_{k=0}^\infty g_k x^k$$

since then

$$G^2(x) = \sum_{k=0}^\infty a_k x^k = \sum_{k=0}^\infty g_{k+1} x^k = \frac{1}{x}(G(x) - 1)$$

which gives us a quadratic equation for $G(x)$ with solution

$$G(x) = \frac{1 - \sqrt{1-4x}}{2x}$$

We can now go back again by expanding $G(x)$ in a power-series using $$\sqrt{1-4x} = \sum_{k=0}^{\infty}{1/2\choose k}(-4x)^k$$ and read off the expression for $g_k$:

$$g_k = -\frac{1}{2}{1/2 \choose k + 1}(-4)^{k+1}=\frac{1}{k+1}{2k\choose k}$$.