How to find a degree 2 homogeneous linear recurrence relation given a formula

Question

Given the formula $a_n = (-1)^n + 2^{n+1}$, how do you find a degree 2 homogeneous linear recurrence relation?

Answer 1

$$a_n-(-1)^n=2^{n+1}$$ so $$a_{n+1}-(-1)^{n+1}=2^{n+2}=2a_n-2(-1)^n$$ Therefore $$a_{n+1}-2a_n=-3(-1)^n$$ so $$a_{n+2}-2a_{n+1}=-3(-1)^{n+1}=-(a_{n+1}-2a_n)$$ etc.

Answer 2

Hint: $\;\require{cancel} a_{n+1} + a_{n} = \bcancel{(-1)^{n+1}} + 2^{n+2} + \bcancel{(-1)^{n}} + 2^{n+1}=3 \cdot 2^{n+1} =3 \cdot 2 \cdot \frac{1}{3}(a_n+a_{n-1})$.

Answer 3

Hint: The characteristic equation of the sequence has two roots: $-1$ and $2.$

Answer 4

Let $a_{n+2} = a_{n+1}x + a_ny$. This gives $$ (-1)^{n+2} + 2^{n+3} = ((-1)^{n+1} + 2^{n+2})x + ((-1)^n + 2^{n+1})y $$ Separating this into two equations, one for the $-1$ term and one for the $2$ term, we get $$ \cases{(-1)^{n+2} = (-1)^{n+1}x + (-1)^{n}y\\2^{n+3} = 2^{n+2}x + 2^{n+1}y} $$ Dividing the first equation by $(-1)^n$ and the second by $2^{n+1}$, we get $$ \cases{1 = -x+y\\4 = 2x + y} $$ which may be solved for $x$ and $y$.