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.
 A: Generating Function Approach
$
\begin{array}{cl}
\text{function}&\text{meaning}\\
x&\text{blue}\\
\frac{x^2}{1-x}&\text{blue followed by one or more red}\\
\frac{x^2}{1-x}&\text{blue followed by one or more white}\\
\frac1x&\text{remove initial blue}
\end{array}
$
The generating function is
$$
\begin{align}
\frac1x\sum_{k=1}^\infty\left(x+\frac{x^2}{1-x}+\frac{x^2}{1-x}\right)^k
&=\frac1x\sum_{k=1}^\infty\left(\frac{x+x^2}{1-x}\right)^k\\
&=\frac1x\frac{\frac{x+x^2}{1-x}}{1-\frac{x+x^2}{1-x}}\\[3pt]
&=\frac{1+x}{1-2x-x^2}
\end{align}
$$
This generating function says
$$
a_0=1\quad a_1=3
$$
and for $n\ge2$,
$$
a_n=2a_{n-1}+a_{n-2}
$$
Solving the linear recurrence relation for $a_n$, we get
$$
a_n=\frac{2+\sqrt2}{2\sqrt2}\left(1+\sqrt2\right)^n-\frac{2-\sqrt2}{2\sqrt2}\left(1-\sqrt2\right)^n
$$

Decomposition By The Terminal Element
Let $r_n$ be the number of strings of length $n$ that end in red.
Let $w_n$ be the number of strings of length $n$ that end in white.
Let $b_n$ be the number of strings of length $n$ that end in blue.
Then we have the recursions  
$
\begin{align}
&\text{recursion}&&\text{reason}\\\hline
r_n&=r_{n-1}+b_{n-1}&&\begin{array}{l}\text{ }\\\text{remove the last from a string that ends}\\\text{in red and it ends in red or blue}\end{array}\\
w_n&=w_{n-1}+b_{n-1}&&\begin{array}{l}\text{ }\\\text{remove the last from a string that ends}\\\text{in white and it ends in white or blue}\end{array}\\
b_n&=r_{n-1}+w_{n-1}+b_{n-1}&&\begin{array}{l}\text{ }\\\text{remove the last from a string that ends}\\\text{in blue and it ends in red, white, or blue}\end{array}
\end{align}
$
Therefore, we have
$$
\begin{align}
a_n
&=r_n+w_n+b_n\\
&=2r_{n-1}+2w_{n-1}+3b_{n-1}\\
&=2r_{n-1}+2w_{n-1}+2b_{n-1}+r_{n-2}+w_{n-2}+b_{n-2}\\
&=2a_{n-1}+a_{n-2}
\end{align}
$$
Thus, we get the same recursion as before.
We can count $a_1=3$ and $a_2=7$ (because we have to leave out red-white and white-red) and solve the linear recurrence relation as above.

Method Similar To That In Natash1's Answer
$$
\begin{align}
a_n
&=\overbrace{\ \ \ a_{n-1}\ \ \ \vphantom{1}}^{\text{one blue}}+\overbrace{\ \ \ \ \ \ 1\ \ \ \ \ \ }^{\text{all red}}+\sum_{k=1}^{n-1}\overbrace{\ \ a_{n-k-1}\ \ \vphantom{1}}^{\text{$k$ red, one blue}}+\overbrace{\ \ \ \ \ \ 1\ \ \ \ \ \ }^{\text{all white}}+\sum_{k=1}^{n-1}\overbrace{\ \ a_{n-k-1}\ \ \vphantom{1}}^{\text{$k$ white, one blue}}\\
&=a_{n-1}+2+2\sum_{k=0}^{n-2}a_k\tag1
\end{align}
$$
Subtracting $(1)$ for $n-1$ from $(1)$ for $n$ gives
$$
a_n-a_{n-1}=a_{n-1}-a_{n-2}+2a_{n-2}\tag2
$$
which is equivalent to
$$
a_n=2a_{n-1}+a_{n-2}\tag3
$$
which is the same recurrence gotten above.
A: 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.
