×が横に並ぶことがないのだから、
n段目の組み合わせは○○、○×、×○の３通り。
最後が○○になる組み合わせをx_n通り
最後が○×になる組み合わせをy_n通り
最後が×○になる組み合わせをz_n通り
とすると
a_n=x_n+y_n+z_n

そして、×が縦に並ぶこともないから、
○×の前は○○か×○だし、×○の前は○○か○×、○○の前は何でもよい
よって
x_(n+1)=x_n+y_n+z_n
y_(n+1)=x_n+z_n
z_(n+1)=x_n+y_n

この３つの式を足し合わせて
x_(n+1)+y_(n+1)+z(n+1)=3x_n+2y_n+2z_n
x_(n+1)+y_(n+1)+z(n+1)=2(x_n+y_n+z_n)+x_n
x_(n+1)+y_(n+1)+z(n+1)=2(x_n+y_n+z_n)+x_(n-1)+y_(n-1)+z_(n-1)
x_(n+1)+y_(n+1)+z(n+1)=2a_n+a_(n-1)