Finding the closed-form formula to a recurrence with summation of terms I am currently trying to work through this recurrence problem but am having a hard time coming up with the solution:
$g\left(n\right)=\left(\sum_{i=1}^{n-1}g\left(i\right)g\left(n-i\right)\right)+1$
Where the base $g(0)=0$.
One thing I noticed was that the values involved in the summation are sort of symmetrical, there would be a $g(2)g(3)$ as well as a $g(3)g(2)$ and this duplicate value would exist for each value of i except for when $i=n-i$, which I wanted to take advantage of. I typically approach closed-form recurrences by creating a polynomial in which I would take a guess for a function and solve for its constants but Im not sure how to extend this idea to something like this.
 A: We can obtain a generating function for your sequence. First we modify the recurrence relation to state $$g(n) = 1 + \sum_{i=0}^ng(i)g(n-i).$$ Note that this gives the same relation because $g(0)=0$. Also note that this equality does not hold for $n=0$ (that gives $g(0) = g(0)^2 + 1$). Now we define the generating function.
Let
$$f(x) = \sum_{n=0}^\infty g(n) \cdot x^n.$$
Then, by taking the Cauchy product of $f$ with itself we see:
\begin{align*}
f(x)^2 &= \sum_{n=0}^\infty \left(\sum_{i=0}^n g(n-i)g(i)\right)x^n\\
&= \sum_{n=1}^\infty \left(\sum_{i=0}^n g(n-i)g(i)\right)x^n\\
&= \sum_{n=1}^\infty \left(g(n) - 1\right)x^n\\
&= \sum_{n=1}^\infty g(n)x^n - \sum_{n=1}^\infty x^n\\
&= f(x) - \frac{x}{1-x}.
\end{align*}
We obtain that the generating function satisfies the relation 
$$f(x)^2 = f(x) - \frac{x}{1-x}.$$ There are two functions satisfying this relation. Namely:
$$f(x) = \frac{1}{2} \left(1-\frac{\sqrt{1-5 x}}{\sqrt{1-x}}\right) \quad\text{ or }\quad f(x) = \frac{1}{2} \left(\frac{\sqrt{1-5 x}}{\sqrt{1-x}}+1\right).$$ 
Only the first choice has its zeroth term equal to zero and thus we conclude that our generating function is $$f(x) = \frac{1}{2} \left(1-\frac{\sqrt{1-5 x}}{\sqrt{1-x}}\right) = x + 2x^2 + 5x^3 + 15x^4 + \cdots.$$ As to a closed form of your sequence. We have now shown that your sequence (up to a different zeroth term because they record the coefficients of $f(x)+1$) is sequence A181768 in the OEIS. You can proceed your research there. The site gives several other ways to calculate the terms of the sequence (see also A007317). A simple formula might be a bit much to ask.
A: More general approach is to use generating functions. In this case, this means finding $$f(x)=g(0)+g(1)x+g(2)x^2+\dots.$$ Then perhaps from the form of $f(x)$ we could extract the coefficients in some way. To find the $f(x)$, first notice that your recurrence definition looks very similar to convolution of two series, i.e. if you multiply $\sum_{n \geq 0} a_nx^n \cdot \sum_{n \geq 0} b_nx^n=\sum_{n \geq 0} c_nx^n$, then 
$$c_n=a_0b_n+a_1b_{n-1}+\dots+a_nb_0=\sum_{i=0}^{n}a_ib_{n-i},$$ 
which suggests we should take something like $f(x)f(x)$ to get $f(x)$. To see it, notice that since $g(0)=0$, we can write the recurrence as $g(n)-1=\sum_{i=0}^{n}g\left(i\right)g\left(n-i\right)$ for $n\geq 1$. Also notice for $n=0$ the equality does not hold (left side is $-1$, right side $0$), we can correct for this by adding $1$. This means that 
$$
1+(g(0)-1)+(g(1)-1)x+(g(2)-1)x^2+\dots=f(x)f(x)=f(x)^2.
$$
Left side is now equal to $1+f(x)-(1+x+x^2+\dots)=1+f(x)-\frac{1}{1-x}=f(x)-\frac{x}{1-x}$, and so we have found out
$$
f(x)-\frac{x}{1-x}=f(x)^2.
$$
By solving this as a quadratic equation in $f$, we have
$$
f(x)=\frac{1\pm \sqrt{1-4\frac{x}{1-x}}}{2}=\frac{1}{2}\pm\frac{1}{2}\frac{\sqrt{1-5x}}{\sqrt{1-x}}.
$$
Now we expect $f(0)=g(0)=0$, so from this we see 
$$f(x)=\frac{1}{2}-\frac{1}{2}\frac{\sqrt{1-5x}}{\sqrt{1-x}}.$$
Having a generating function, we can try and deduce the coefficients in a non-recursive way. To do this, we will use series expansions that we already know, in this case binomial series is very useful since we can write $f(x)=\frac{1}{2}-\frac{1}{2}(1-5x)^{1/2}(1-x)^{-1/2}$. So by the binomial series we get
$$
(1-5x)^{1/2}=\sum_{k=0}^{\infty}\binom{1/2}{k}(-1)^k5^kx^k=1-\frac{1}{2}5x+\frac{1/2\cdot -1/2}{2}5^2x^2+\dots\\
(1-x)^{-1/2}=\sum_{k=0}^{\infty}\binom{-1/2}{k}(-1)^kx^k=1+\frac{1}{2}x+\frac{-1/2\cdot -3/2}{2}x^2+\dots\\
$$ 
and so 
\begin{align}
f(x)&=\frac{1}{2}-\frac{1}{2}\sum_{n=0}^{\infty}\sum_{i=0}^{n}\binom{1/2}{i}(-1)^i5^i\cdot \binom{-1/2}{n-i}(-1)^{n-i} x^n\\
&=-\frac{1}{2}\sum_{n=1}^{\infty}\sum_{i=0}^{n}5^i\binom{1/2}{i}(-1)^i\cdot \binom{-1/2}{n-i}(-1)^{n-i} x^n\\
&=\sum_{n=1}^{\infty}\frac{(-1)^{n+1}}{2}\sum_{i=0}^{n}5^i\binom{1/2}{i}\binom{-1/2}{n-i}x^n.\\
\end{align}
Now we can read off the coefficient at $x^n$ to get $g(n)$, so 
$$
\bbox[#ffd,10px]{g(n)=\frac{(-1)^{n+1}}{2}\sum_{i=0}^{n}5^i\binom{1/2}{i}\binom{-1/2}{n-i}.}
$$
You can possibly further simplify this writting out the generalized binomial coefficients inside the sum, but I wouldn't expect a closed form without the sum involved. For example, you should be able to arrive at 
$$
g(n)=\sum_{k=0}^{n-1}(-1)^k3^{n-k-1}\binom{n-1}{k}\binom{k}{\lfloor k/2 \rfloor}
$$
as mentioned in https://oeis.org/A007317, which has the additional benefit that all its terms are integers (and so might be for example more suitable for investigating divisibility properties of the sequence).
