<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] 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.
</s>