Solving Recurrence with Generating Function

Question

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?

Answer 1

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.

Answer 2

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)$.