I was playing around with this interesting recurrence relationship $(n+1)a_{n+1} = 3a_n + 1$ with $a_0 = 1$, but I couldn't get the final answer $f' = 3f + \frac{1}{1-x}$.
I have attempted with two rules.
- $ n \cdot f = x \frac{df}{dx}$
- $ f_{n+1} = \frac{f-1}{x} $
I do recognize the part $\frac{1}{1-x}$ is just the geometric series but I couldn't see the connection.
The best that I got was $f' = 3f + \frac{x+1-f}{x}$ but still haven't got the desired answer.
Can anyone please explain this to me? Very appreciated!!
Take the recurrence relation $(n+1)a_{n+1}=3a_n+1$, multiply both sides by $x^n$, and sum over all $n\ge 0$. $$ \sum_{n\ge 0} (n+1)a_{n+1}x^n=\sum_{n\ge 0}3a_nx^n+\sum_{n\ge 0} x^n $$ It should be clear that $\sum_n 3a_nx^n=3f$, while $\sum_{n\ge 0}x^n=\frac1{1-x}$. For the sum on the left, we use the fact that $({n+1})x^n=\frac{d}{dx}[ x^{n+1} ]$ to write the sum as a derivative of $f$: $$ \begin{align} \sum_{n\ge 0} (n+1)a_{n+1}x^n &= \sum_{n\ge 0} a_{n+1} \frac{d}{dx}[x^{n+1}] \\&= \frac{d}{dx}\left[\sum_{n\ge 0} a_{n+1} x^{n+1}\right] \\&\stackrel1= \frac{d}{dx}\left[\sum_{n\ge 1} a_{n} x^{n}\right] \\&\stackrel2= \frac{d}{dx}\left[-a_0+\sum_{n\ge 0} a_{n} x^{n}\right] \\&= \frac{d}{dx}\left[-a_0+f\right] \\&= f'. \end{align} $$ Explanations:
Here, we re-index the summation. The idea is that for any summation $\sum_{n=0}^\infty b_n$, we can define a new variable $m=n+1$, and use $m$ as the summation variable instead of $m$. As $n$ goes from $0$ to infinity, $m$ goes from $1$ to infinity, so $\sum_{n=0}^\infty b_n =\sum_{m=1}^\infty b_{m-1}=\sum_{n=1}^\infty b_{n-1}$. Apply this with $b_n=a_{n+1}x^{n+1}$.
Note that $\sum_{n\ge 1} a_{n} x^{n}$ is almost equal to the definition of $f$, except we are only summing over $n\ge 1$ instead of all $n\ge 0$. To fix this, we add and subtract the first term, $a_0$, hence the $-a_0$ out front.