Recurrence equation solution I have the following equation that I need to solve (just find its form and replace numbers with $A,B$,...
$a_{n} = 8a_{n-2} - 16a_{n-4}$
My problem is that there is no $a_{n-1} , a_{n-3}$. 
Do I just imagine they exist with a $0$ in front of them? Like this:
$0a_{n-1} + 0a_{n-3}$
Finally my request is that you solve this for me step by step so I can understand. 
 A: Note that $$a_n=0\cdot a_{n-1}+8a_{n-2}+0\cdot a_{n-3}-16a_{n-4}$$
$$\iff a_n+2a_{n-1}-4a_{n-2}-8a_{n-3}=2(a_{n-1}+2a_{n-2}-4a_{n-3}-8a_{n-4})$$
$$\iff b_n=2b_{n-1}$$
where $b_n=a_n+2a_{n-1}-4a_{n-2}-8a_{n-3}$. Since $b_n=b_1\cdot 2^{n-1}$, one has
$$a_n+2a_{n-1}-4a_{n-2}-8a_{n-3}=b_1\cdot 2^{n-1}.$$
Here, setting $c_n=\frac{a_n}{2^n}$ gives you
$$\frac{a_n+2a_{n-1}-4a_{n-2}-8a_{n-3}}{2^n}=\frac{b_1\cdot 2^{n-1}}{2^n}$$
$$\iff \frac{a_n}{2^n}+\frac{2a_{n-1}}{2^n}-\frac{4a_{n-2}}{2^n}-\frac{8a_{n-3}}{2^n}=\frac{b_1}{2}$$
$$\iff c_n+c_{n-1}-c_{n-2}-c_{n-3}=\frac{b_1}{2}$$
Now setting $d_n=c_n-c_{n-2}$ gives you
$$d_n=-d_{n-1}+\frac{b_1}{2}.$$
Can you take it from here?
A: $a_n = 8a_{n−2} − 16a_{n−4}$
Let $a_n = x^n$
Then $x^n = 8x^{n-2} - 16x^{n-4}$
Hence $x = 2, -2$
So $a_n = (c_1+c_2n)2^n+(c_3+c_4n)(-2)^n$
You can solve $c_1, c_2, c_3, c_4$ from initial conditions.
A: To your recurrence associate the algebraic equation $x^4 = 8x^2 - 16$. This is equivalent to $(x^2-4)^2=0$, which has the roots $\pm 2$, each one counted twice (i.e. they are double roots). Therefore, the general term will be $x_n = a 2^n + b n 2^n + c (-2)^n + d n (-2)^n$, and you get $a,b,c,d$ from the first $4$ terms.
