Use generating functions to solve $a_n = 6a_{n-1} - 8a_{n-2} + 3 $ and...

Question

Use generating functions to solve:

$$a_n = 6 a_{n - 1} - 8 a_{n - 2} + 3$$

With initial condition: $a_0 = 1$ and $a_1 = 0$

$$a_n = 3 a_{n - 1} + 4 a_{n - 2}$$

With initial conditions: $a_0 = 1$

Have done recurrence relation problems before but am struggling with these two problems, any help is appreciated.

Answer 1

writing $∑_1 := \sum_{n=1}^∞$, \begin{align} A(x) &= \sum_{n=1}^∞ a_n x^n \\&= a_1x + a_2x^2 + \sum_{n=1}^∞ a_{n+2}x^{n+2} \\&= 0 + a_2x^2 + x^2∑_1\left(6a_{n+1}-8a_n+3\right)x^n \\&= a_2x^2 + x^2\left[ 6∑_1 a_{n+1}x^n - 8A(x) + 3∑_1x^n \right] \\&= a_2x^2 + x^2\Big[ 6\frac{A(x)-\color{red}{\overbrace{\color{black}{a_1x}}^{=0}}}{x} - 8A(x) + \frac{3x}{1-x}\Big] \\&= a_2x^2 + 6xA(x) - 8x^2A(x) + \frac{3x^3}{1-x} \end{align} So that

$$A(x) = \frac{a_2x^2 + \frac{3x^3}{1-x}}{8x^2-6x+1} = \frac{a_2x^2-a_2x^3 + 3x^3}{(8x^2-6x+1)(1-x)}$$

Expanding the right hand side as a Taylor series will give the answer. Alternatively, finish using the partial fraction decomposition (if you aren't a masochist, try W|A.)

Answer 2

Shift indices of the first one to get:

$\begin{align} a_{n + 2} = 6 a_{n + 1} - 8 a_n + 3 \end{align}$

Define the generating function $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get:

$\begin{align} \sum_{n \ge 0} a_{n + 2} z^n &= 6 \sum_{n \ge 0} a_{n + 1} z^n - 8 \sum_{n \ge 0} a_n z^n + 3 \sum_{n \ge 0} z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= 6 \frac{A(z) - a_0}{z} - 8 A(z) + 3 \frac{1}{1 - z} \end{align}$

Solving for $A(z)$, as partial fractions:

$\begin{align} A(z) &= \frac{1 - 7 z + 9 z^2}{1 - 7 z + 14 z^2 - 8 z^3} \\ &= \frac{1}{1 - z} + \frac{1}{2} \frac{1}{1 - 2 z} - \frac{1}{2} \frac{1}{1 - 4 z} \end{align}$

This is just a bunch of geometric series:

$\begin{align} a_n = 1 + \frac{1}{2} \cdot 2^n - \frac{1}{2} \cdot 4^n \end{align}$