>>780
漸化式立てよう

n を自然数とし、2行n列のマス目に A,B を記入するとき、
B が縦横に隣り合わない並べ方が M[n] 通りあるとする

2行n列での B が縦横に隣り合わない並べ方のうち、第 n 列が、
ともにAのとき a[n] 通り、上がAで下がBのとき b[n] 通り、上がBで下がAのとき c[n] 通り
M[n]=a[n]+b[n]+c[n]
a[1]=1, b[1]=1, c[1]=1

第 n 列の右側に2マス付け加えて、2行(n+1)列を考える
a[n+1]=a[n]+b[n]+c[n],
b[n+1]=a[n]+c[n],
c[n+1]=a[n]+b[n]