I'm trying to find a closed form formula for the following recurrence problem but I'm having some difficulty:
\begin{align}
g(n) &= -\frac{1}{n+1} – \sum_{i=1}^{n} \frac{1}{n+1}g(i) \\
&= \frac{1}{n+1} \biggl( -1 – n\sum_{i=1}^{n} g(i) \biggr)
\end{align}
With $$g(0) = -\frac{1}{3}$$
I've seen several other posts use generator functions which I've attempted to use but got stuck relatively quickly.
\begin{align}
f(x) &= \sum_{n=0}^{\infty}g(n)\,x^n \\
&= \sum_{n=0}^{\infty} \biggl( \frac{1}{n+1}
\Bigl( -1 – (n) \sum_{i=1}^{n}g(i) \Bigr)x^n \biggr) \\
&= \sum_{n=0}^{\infty} \biggl( \frac{x^n}{n+1}
\Bigl( -1 – (n) \sum_{i=1}^{n}g(i) \Bigr) \biggr) \\
&= \sum_{n=0}^{\infty} – \frac{x^n}{n+1}
– \sum_{n=0}^{\infty}
\biggl( \frac{x^n(n)}{n+1} \sum_{i=1}^{n} g(i) \biggr) \\
&= \frac{\log(1-x)}{x} – \sum_{n=0}^{\infty} \biggl( \frac{x^n(n)}{n+1}
\sum_{i=1}^{n}g(i) \biggr)
\end{align}
But I'm not too sure where to go from there.
Best Answer
I think you need to be careful with the writing of the problem as mentioned in the comments. You also mention the value of $g(0)$ to be $-\frac{1}{3}$ but I think you mean $g(1)$. Therefore, I will solve the problem so it is consistent with $g(1)=-\frac{1}{3}$ and using the definition $$ g(n)=-\frac{1}{n+1}\left(1+\sum_{i=1}^ng(i)\right) $$ which is the same as the first line you have written.
Let $s(n)=\displaystyle\sum_{i=1}^n g(i)$. Then, we have $$ g(n)=-\frac{1}{n+1}(1+s(n)) $$ On the other hand, note that $g(n)=s(n)-s(n-1)$, and hence we can plug this into the above to get $$ s(n)-s(n-1)=-\frac{1}{n+1}(1+s(n)) $$ or after simplifying a bit $$ (n+2)s(n)-(n+1)s(n-1)=-1. $$ One can guess that $s(n)=-\frac{n}{n+2}$ solves such equation and satisfies $s(1)=g(1)=-\frac{1}{3}$. Hence, we have $$ \begin{align} g(n)&=s(n)-s(n-1)\\ &=-\frac{n}{n+2}+\frac{n-1}{n+1}\\ &=-\frac{2}{(n+1)(n+2)}. \end{align} $$