Question

G identify the solution of the recurrence relation an = 6an − 1 – 8an − 2 for n ≥ 2 together with the initial conditions a0 = 4, a1 = 10.

Answer 1

Via the generating function method, let

$G(x)=\displaystyle\sum_{n\ge0}a_nx^n$

Then take the recurrence,

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

multiply everything by $x^n$ and sum over all $n\ge2$:

$\displaystyle\sum_{n\ge2}a_nx^n=6\sum_{n\ge2}a_{n-1}x^n-8\sum_{n\ge2}a_{n-2}x^n$

Re-index the sums or add/remove terms as needed in order to be able to express them in terms of $G(x)$:

$\displaystyle\sum_{n\ge2}a_nx^n=\sum_{n\ge0}a_nx^n-(a_0-a_1x)=G(x)-4-10x$

$\displaystyle\sum_{n\ge2}a_{n-1}x^n=\sum_{n\ge1}a_nx^{n+1}=x\sum_{n\ge1}a_nx^n=x\left(G(x)-a_0\right)=x(G(x)-4)$

$\displaystyle\sum_{n\ge2}a_{n-2}x^n=\sum_{n\ge0}a_nx^{n+2}=x^2\sum_{n\ge0}a_nx^n=x^2G(x)$

So the recurrence relation is transformed to

$G(x)-4-10x=6x(G(x)-4)-8x^2G(x)$
$(1-6x+8x^2)G(x)=4-14x$
$G(x)=\dfrac{4-14x}{1-6x+8x^2}=\dfrac{4-14x}{(1-4x)(1-2x)}=\dfrac1{1-4x}+\dfrac3{1-2x}$

For appropriate values of $x$, we can express the RHS in terms of geometric power series:

$G(x)=\displaystyle\sum_{n\ge0}(4x)^n+3\sum_{n\ge0}(2x)^n=\sum_{n\ge0}\bigg(4^n+3\cdot2^n\bigg)x^n$

which tells us that

$a_n=4^n+3\cdot2^n$