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

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.

• Why do you have an $(n+1)$ in front of the sum of $g(i)$s in the second line expressing $g(n)$?
– Gary
Dec 1, 2021 at 5:34
• To clarify: are you trying to determine the sequence $\{g(1), g(2), \dots \}$? Or does the indexing begin at $n=0$? Dec 1, 2021 at 5:35
• Concern: In order to solve a recurrence, you have to have initial value(s). What is $g(0)$ or $g(1)$ or wherever this sequence begins? Dec 1, 2021 at 5:36
• Another concern: Did you mean to express $g(n)$ in terms of itself (as the last term in the sum on the right)? Dec 1, 2021 at 5:37
• @gary that was a mistake it should be $(n-1)$ edited the original post to reflect that. I also added $g(1)$ which starts the indexing. Dec 1, 2021 at 6:32

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}