Finding the closed-form formula to a recurrence with summation of terms

Question

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.

Answer 1

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

Answer 2

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.