# Find a closed form for a generating function and recurrence

Find a closed form for the generating function $R(x) = \sum_{n=0}^\infty r_nx^n$, where $r_n$ is given by the recurrence $r_n = 3r_{n-1} + 5r_{n-2} + 6n$ for $n \geq 2$ and initial conditions $r_0 = 1$ and $r_1 = 2$.

-
What have you tried? –  Pedro Tamaroff Apr 6 '13 at 16:52
[APPARENTLY THIS IS A PART OF AN EXAM] ${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$ –  Pedro Tamaroff Apr 6 '13 at 16:56
This is a question from a take-home exam which is in-progress. I kindly ask that all well-meaning respondents wait until after 6pm on Monday April 8th to answer this question. –  DrBaxter Apr 6 '13 at 22:30

Hint Your recurrence is $$r_n=3r_{n-1}+5r_{n-2}+6n$$

This means $$\sum_{n=2}^\infty r_nx^n=3\sum_{n=2}^\infty r_{n-1}x^n+5\sum_{n=2}^\infty r_{n-2}x^n+6\sum_{n=2}^\infty nx^n$$

which can be put after some index shifting as $$\sum\limits_{n = 0}^\infty {{r_n}} {x^n} - {r_1}x - {r_0} = 3\sum\limits_{n = 1}^\infty {{r_n}} {x^{n + 1}} + 5\sum\limits_{n = 0}^\infty {{r_n}} {x^{n + 2}} + 6\sum\limits_{n = 2}^\infty n {x^n}$$

so calling $$R(x) =\sum\limits_{n = 0}^\infty {{r_n}} {x^n}$$ $$R\left( x \right) - {r_1}x - {r_0} = 3{x}\left( {R\left( x \right) - {r_0}} \right) + 5{x^2}R\left( x \right) + 6\sum\limits_{n = 2}^\infty n {x^n}$$

Can you continue?

SPOILER I got

$\displaystyle R\left( x \right) = \frac{{1 - x}}{{1 - 3x - 5{x^2}}} + \frac{{6{x^3}}}{{1 - 3x - 5{x^2}}}{\left( {\frac{1}{{1 - x}}} \right)^2} + \frac{{12{x^2}}}{{1 - 3x - 5{x^2}}}\frac{1}{{1 - x}}$

-
/* i'm new at this site, sorry for the format. Question for 3 summation from n=2 to infinity rn-1*x^(n) when i shifted i get 3x[R(x)-r0] i could be wrong can you clarify how you obtained yours thanks!*/ –  Carlos Apr 6 '13 at 17:46
@Carlos Yes, I wrote $x^{n+2}$ when it should have been $x^{n+1}$. –  Pedro Tamaroff Apr 6 '13 at 18:10
Thanks a lot your steps were very useful! –  Carlos Apr 6 '13 at 18:35