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$
    – Sammy Black
    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$
    – Sammy Black
    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$
    – Sammy Black
    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$
    – Krystian Wojcicki
    Dec 1, 2021 at 6:32

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .