Solving Recurrence with Generating Function I have the following recurrence:
$r_n = 4r_{n-1} + 6r_{n-2} \text{ where } r_0 = 1 \text{ and } r_1 = 3$

Next, I write my generating function, $R(x)$:
$$
\begin{align}
R(x)*(1 - 4x - 6x^2) &= r_0 + (r_0 -4*r_1)x + 0*x^2 + ...\\
R(x)*(1 - 4x - 6x^2) &= 1 + (1 - 4*3)x = 1 - 11x
\end{align}
$$
Then, I find my roots...and they are ridiculous.  I've done it 4 times now, and I'm convinced my error lies in the setup.  
Either way, I wind up with the following generating function, which is wrong at $n=1$ and thereafter, but seems to be off by a factor of $-5$ at $n=1$ and $11$ at $n=2$, yielding $\{1,-15,66,...\}$ (so there seems to be some correspondence...):
$$
(\frac{1}{2} + \frac{3}{2\sqrt{10}}) \sum_{n=0}^{\infty}(\frac{6}{2-\sqrt{10}})^n x^n + (\frac{1}{2} - \frac{3}{2\sqrt{10}})\sum_{n=0}^{\infty}(\frac{6}{2+\sqrt{10}})^n
$$
I'm not sure where the mistake is.  I am pretty sure about the roots (inverse of the coefficients in the sums) at least (maybe there is some other error, but I double checked them with Wolfram Alpha)...

Where might I be going wrong?
 A: One way to proceed is by the characteristic polynomial to yield a general solution: $r_n=4r_{n-1}+6r_{n-2}$ is analogous to solving
$r^n=4r^{n-1}+6r^{n-2}$
or better yet:
$r^2=4r+6$
etc. etc.
But explicitly for your purposes:
$r_0=1$ and $r_1=3$. So we take the linear recurrence and consider the formal power series:
$$r(x)=\sum_{n=0}^{\infty} r_nx^n=1+\sum_{n=1}^{\infty}r_nx^n=1+3x+\sum_{n=2}^{\infty}r_nx^n$$
But we have a particular recurrence to satisfy! So:
$$1+3x+\sum_{n=2}^{\infty}r_nx^n=1+3x+\sum_{n=2}^{\infty}(4r_{n-1}+6r_{n-2})x^n=1+3x+\sum_{n=2}^{\infty}4r_{n-1}x^n+\sum_{n=2}^{\infty}6r_{n-2}x^n$$
However, we have that: $\sum_{n=2}^{\infty}4r_{n-1}x^n=3x\cdot4\cdot\sum_{n=2}^{\infty}r_{n-1}x^{n-1}=12x\cdot r(x)$.
Can you express the following in terms of $r(x)$?: $\sum_{n=2}^{\infty}6r_{n-2}x^n$
Once you have this, it will require only elementary algebra to solve for $r(x)$.
A: More generally,
suppose
$r_n = ar_{n-1} + br_{n-2}
$
with
$r_0$ and $r_1$ given.
Let
$R(x)
=\sum_{n=0}^{\infty} r_n x^n
$.
Then
$\begin{array}\\
xR(x)
&=x\sum_{n=0}^{\infty} r_n x^n\\
&=\sum_{n=0}^{\infty} r_n x^{n+1}\\
&=\sum_{n=1}^{\infty} r_{n-1} x^{n}\\
\end{array}
$
and
$\begin{array}\\
x^2R(x)
&=x^2\sum_{n=0}^{\infty} r_n x^n\\
&=\sum_{n=0}^{\infty} r_n x^{n++2}\\
&=\sum_{n=2}^{\infty} r_{n-2} x^{n}\\
\end{array}
$
Therefore
$\begin{array}\\
R(x)-axR(x)-bx^2R(x)
&=\sum_{n=0}^{\infty} r_n x^n
-a\sum_{n=1}^{\infty} r_{n-1} x^{n}
-b\sum_{n=2}^{\infty} r_{n-2} x^{n}\\
&=(r_0+r_1x+\sum_{n=2}^{\infty} r_n x^n)
-a(r_0x+\sum_{n=2}^{\infty} r_{n-1} x^{n})
-b\sum_{n=2}^{\infty} r_{n-2} x^{n}\\
&=r_0+r_1x-ar_0x+\sum_{n=2}^{\infty}  x^n(r_n-ar_{n-1}-br_{n-2})\\
&=r_0+x(r_1-ar_0)
\qquad\text{since }r_n-ar_{n-1}-br_{n-2}=0\\
\text{or}\\
R(x)(1-ax-bx^2)
&=r_0+x(r_1-ar_0)\\
\text{or}\\
R(x)
&=\dfrac{r_0+x(r_1-ar_0)}{1-ax-bx^2}\\
\end{array}
$
Write
$1-ax-bx^2
=(1-ux)(1-vx)
$,
then use partial fractions
to get $R(x)$.
(added later)
We have
$\begin{array}\\
R(x)
&=\dfrac{r_0+x(r_1-ar_0)}{1-ax-bx^2}\\
&=\dfrac{p+xq}{(1-ux)(1-vx)}
\qquad\text{where } p = r_0, q = r_1-ar_0\\
&=\dfrac{p+qx}{u-v}\left(-\dfrac{v}{1-v x}+\dfrac{u}{1-u x}\right)\\
&=\dfrac{p}{u-v}\left(-\dfrac{v}{1-v x}+\dfrac{u}{1-u x}\right)
+\dfrac{qx}{u-v}\left(-\dfrac{v}{1-v x}+\dfrac{u}{1-u x}\right)\\
\end{array}
$
We have
$\dfrac{u}{1-u x}
=u\sum_{n=0}^{\infty} u^nx^n
$
and similarly for $v$.
This will enable you
to get the $r_n$.
(end of addition)
This generalizes immediately
to a general linear recurrence,
with the usual caveats about
repeated roots.
As is often the case
in my answers,
absolutely nothing here
is original.
