Question

Identify the solution to an = 2an − 1 + an − 2 − 2an − 3 for n = 3, 4, 5, . . . , with a0 = 3, a1 = 6, and a2 = 0.

Answer 1

Here's one way of solving via the generating function method.

$\begin{cases}a_0=3\\a_1=6\\a_2=0\\a_n=2a_{n-1}+a_{n-2}-2a_{n-3}&\text{for }n\ge3\end{cases}$

For the sequence $a_n$, denote its generating function by $G(x)$ with


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


In the recurrence relation, multiply all terms by $x^n$ and sum over all non-negative integers larger than 2:


$\displaystyle\sum_{n\ge3}a_nx^n=2\sum_{n\ge3}a_{n-1}x^n+\sum_{n\ge3}a_{n-2}x^n-2\sum_{n\ge3}a_{n-3}x^n$


The goal is to rewrite everything we can in terms of $G(x)$ and (possibly) its derivatives. For example, the term on the LHS can be rewritten by adding and subtracting the the first three terms of $G(x)$:


$\displaystyle\sum_{n\ge3}a_nx^n=\sum_{n\ge0}a_nx^n-(a_0+a_1x+a_2x^2)=G(x)-3-6x$


For the other terms on the RHS, you need to do some re-indexing of the sum:

$\displaystyle\sum_{n\ge3}a_{n-1}x^n=\sum_{n\ge2}a_nx^{n+1}=x\sum_{n\ge2}a_nx^n=x\left(\sum_{n\ge0}a_nx^n-(a_0-a_1x)\right)=x\bigg(G(x)-3-6x\bigg)$

$\displaystyle\sum_{n\ge3}a_{n-2}x^n=\sum_{n\ge1}a_nx^{n+2}=x^2\sum_{n\ge1}a_nx^n=x^2\left(\sum_{n\ge0}a_nx^n-a_0\right)=x^2\bigg(G(x)-3\bigg)$

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

So in terms of the generating function, the recurrence can be expressed as

$G(x)-3-6x=2x\bigg(G(x)-3-6x\bigg)+x^2\bigg(G(x)-3\bigg)-2x^3G(x)$
$(1-2x-x^2+2x^3)G(x)=3-15x^2$
$G(x)=\dfrac{3-15x^2}{1-2x-x^2+2x^3}=\dfrac{3-15x^2}{(1-x)(1+x)(1-2x)}$

Decomposing into partial fractions, we get

$G(x)=\dfrac6{1-x}-\dfrac2{1+x}-\dfrac1{1-2x}$

and we recognize that for appropriate values of $x$, we can write these as geometric power series:

$G(x)=\displaystyle6\sum_{n\ge0}x^n-2\sum_{n\ge0}(-x)^n-\sum_{n\ge0}(2x)^n$

Or, more compactly,

$G(x)=\displaystyle\sum_{n\ge0}\bigg(6-2(-1)^n-2^n\bigg)x^n$


which suggests that the solution to the recurrence is

$a_n=6-2(-1)^n-2^n$