1
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Why do you have an $(n+1)$ in front of the sum of $g(i)$s in the second line expressing $g(n)$? $\endgroup$
    – Gary
    Dec 1, 2021 at 5:34
  • $\begingroup$ To clarify: are you trying to determine the sequence $\{g(1), g(2), \dots \}$? Or does the indexing begin at $n=0$? $\endgroup$ Dec 1, 2021 at 5:35
  • $\begingroup$ 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? $\endgroup$ Dec 1, 2021 at 5:36
  • $\begingroup$ Another concern: Did you mean to express $g(n)$ in terms of itself (as the last term in the sum on the right)? $\endgroup$ Dec 1, 2021 at 5:37
  • $\begingroup$ @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. $\endgroup$ Dec 1, 2021 at 6:32

1 Answer 1

0
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.