Finding a generating function for a recursion

Question

Let $a_1=2, a_2=10$ and $a_n=2a_{n-1}+3a_{n-2}$.

I want to find the generating function, $F(x)$ for this recursion:

$$F(x) = 2 + 10x + \sum\nolimits_{n \ge 2} {(2{a_{n + 1}} + 3{a_n}) \cdot {x^n}} $$

$$F(x) = 2 + 10x + 2 \cdot \sum\nolimits_{n \ge 2} {{a_{n + 1}}{x^n} + 3} \cdot \sum\nolimits_{n \ge 2} {{a_n}{x^n}} $$

$$F(x) = 2 + 10x + 2 \cdot \sum\nolimits_{n \ge 2} {{a_{n + 1}}{x^n} + 3} \cdot \left( {F(x) - 2 - 10x} \right)$$

How to treat this expression?
$$\sum\nolimits_{n \ge 2} {{a_{n + 1}}{x^n}} $$

Answer 1

This is even simpler than your previous question; so if you've understood the answer you accepted there, then you shouldn't have any trouble with this.

Anyway, to answer your final question, just note that $$\sum_{n \ge 2} a_{n+1} x^n = \frac{1}{x} \sum_{n \ge 2} a_{n+1} x^{n+1} = \frac1x \sum_{m \ge 3} a_m x^m = \frac1x (F(x) - a_0 - a_1x - a_2 x^2)$$

(But note that there is an error in your calculation: when $\displaystyle F(x) = \sum_{n \ge 0}a_n x^n$, you must write either $$F(x) = 2 + 10x + \sum_{n \ge 2} a_n x^n$$ or $$F(x) = 2 + 10x + \sum_{n \ge 0} a_{n+2} x^{n+2},$$ not $$\displaystyle F(x) = 2 + 10x + \sum_{n \ge 2} a_{n+2} x^{n+2}$$ as you have.)

---

If you do it correctly, you get $$\begin{align} F(x) &= 2 + 10x + \sum_{n \ge 0} a_{n+2} x^{n+2} \\ &= 2 + 10x + \sum_{n \ge 0} (2a_{n+1} + 3a_n) x^{n+2} \\ &= 2 + 10x + 2x\sum_{n \ge 0} a_{n+1} x^{n+1} + 3x^2 \sum_{n \ge 0} a_n x^n \\ &= 2 + 10x + 2x(F(x) - a_0) + 3x^2 F(x) \\ \end{align}$$ giving $$F(x)(1 - 2x - 3x^2) = 2 + 6x $$ or $$F(x) = \frac{2 + 6x}{1 - 2x - 3x^2} = \frac{2 + 6x}{(1 + x)(1 - 3x)} = \frac{3}{1-3x} - \frac{1}{1+x}$$ and therefore $$a_n = 3^{n+1} - (-1)^n$$

Answer 2

Define $F(z) = \sum_{n \ge 0} a_n z^n$ (starting indices at 0 is more comfortable), and write your recurrence as: $$ a_{n + 2} = 2 a_{n + 1} + 3 a_n \qquad a_0 = 2, a_1 = 2 $$ (the value for $a_0$ comes from running the recurrence backwards).

Multiply the recurrence by $z^n$, sum over $n \ge 0$, and recognize: \begin{align} \sum_{n \ge 0} a_{n + 2} z^n &= \frac{F(z) - a_0 - a_1 z}{z^2} \\ \sum_{n \ge 0} a_{n + 1} z^n &= \frac{F(z) - a_0}{z} \end{align} to get: $$ \frac{F(z) - 2 - 2 z}{z^2} = 2 \frac{F(z) - 2}{z} + 3 F(z) $$ I.e., $$ F(z) = 2 \frac{1 - z}{(1 + z) (1 - 3 z)} = \frac{1}{1 - 3 z} + \frac{1}{1 + z} $$ This is just two geometric series: $$ a_n = 3^n + (-1)^n $$ This agrees with the initial values given.