二つずつ掛けるときのパターンは以下の通り
AA=A,BC=A,CA=C,DC=C
AB=B,BD=B,CB=D,DD=D
その他の組み合わせではO
(A-D)^nとしてあり得るものは、A,B,C,D,Oとなる
(A-D)^nがA,B,C,Dとなる場合の数をそれぞれA(n),B(n),C(n),D(n)とする
これからn=kのときと、n=k-1のときの場合の数の関係を調べていくとする

(A-D)^(k-1)がO以外のとき
A〜Dになる、それぞれの場合に対して(A-D)^kがOとなるために掛けるべき行列のパターンは2通りある
よって、場合の数2{A(k-1)+B(k-1)+C(k-1)+D(k-1)}

(A-D)^(k)がOとなるとき
何をかけてもOになるから
場合の数 4E(k-1)
故にE(k)=2{A(k-1)+B(k-1)+C(k-1)+D(k-1)}+4E(k-1)
ところで、(A-D)^nとしてあり得る全ての場合の数は4^nであり、これはA(n)+B(n)+C(n)+D(n)+E(n)に等しいから
A(k-1)+B(k-1)+C(k-1)+D(k-1)=4^(k-1)-E(k-1)

E(k)=2*4^(k-1)+2E(k-1)
あとは漸化式を解いて終わり