<s>[INST] Justify the recurrence relation $a_{n+2}=2a_{n+1}+a_n$ and find $a_n$ Let $a_n$ be the number of ways to color the squares of a $1$ x $n$ chessboard using the colors red, white, and blue, so that no red square is adjacent to a white square. Justify the relation $a_{n+2}=2a_{n+1}+a_n$ (for certain $n$), and then find $a_n$.
My Attempt:
.If the first square is blue, then the number of ways of coloring the other $n-1$ squares is $a_{n-1}$
.If the first square is red, then the next square must be blue (1 option), and the rest can be filled in $a_{n-2}$ ways
.If it is white, then it is also $a_{n-2}$ 
This means the recurrence relation is $a_n=a_{n-1}+2a_{n-2}$ for $n\ge2$
By inspection, $a_0=1$ and $a_1=3$
Not sure where to go from here.
 [/INST] I'm also learning recurrence relations as well so here's my take on it :) (please let me know if this makes sense)   
I got a recurrence relation of $$a_n = a_{n-1} + 2a_{n-2} + 2\times 3^{n-2}$$
for $n\geq 2$ with $a_0 = 1, a_1 = 3$.   
Here's how I derived it:
Case 1: The first block is blue. The remaining board is filled up in $a_{n-1}$ ways.
Case 2: The first block is red.
Case 2.1: If the second block is blue, then the remaining is filled in $a_{n-2}$ ways.
Case 2.2: The second block is also red. We count the number of ways the first block is red, the second block is red by counting the total number of unrestricted ways, less the number of ways the second block is not red.
The total number of ways is $3^{n-1}$.
The number of ways the second block is not red is $2\times 3^{n-2}$.
So, this case has $3^{n-1} - 2\times 3^{n-2} = 3^{n-2}$ ways.
So case 2 has $a_{n-2} + 3^{n-2}$ ways
Case 3: The first block is white.
This is the same as case 2.
 So the number of ways is also $a_{n-2} + 3^{n-2}$ ways.  
So,
$$a_n = a_{n-1} + 2a_{n-2} + 2\times 3^{n-2}.$$

To solve this, we can use the Method of Undetermined Coefficients. Basically, educated guessing.
The solution will be in the form of
$$a_n = h_n + p_n$$
where $h_n$ is the homogenous solution and $p_n$ is the particular solution.
For the homogenous solution:
$$h_n - h_{n-1} - 2h_{n-2} = 0,$$
the characteristic equation is
$$r^2 - r - 2 = 0$$
which has roots $r=2,-1$.
So $$h_n = A(2)^n + B(-1)^n$$
for arbitrary constants $A,B$.  
The particular solution $p_n$ will be in the form
$$p_n = a\times 3^{n-2}$$
for some constant $a$.
So
$$p_n - p_{n-1} - 2p_{n-2} = a(3^{n-2} - 3^{n-3} - 2\times 3^{n-4}) = 3^{n-2} \\ a(9 - 3 - 2) = 9 \\ a = \frac{9}{4}.$$
So, $$p_n = \frac{9}{4} \times 3^{n-2}$$
So,
$$a_n = A(2)^n + B(-1)^n + \frac{9}{4} 3^{n-2}$$
which you can solve for $A,B$ using the initial conditions.
</s>