✨ ベストアンサー ✨
まず、(i)のキです。
A,Bで作られるn文字の文字列には次の2種類があります。
[1]Aから始まるもの [2]Bから始まるもの
この２つで場合分けをします。
[1]1文字目がAなので、2文字目はBでないと条件を満たしません。そして、3文字目はA,Bどちらでもいいです。いま、1文字目と2文字目が決まっていて、残りのn-2文字は何から始まってもいいようなAが連続しない文字列です。よってこの場合の総数はc_{n-2}と同じです。
[2]は[1]と同様に、1文字目がBなので2文字目はA,Bどちらでもいいです。よって[1]と同じ理由で、残りn-1個の並べ方はc_{n-1}通りです。
[1][2]を合わせて、c_n = c_{n-1} + c_{n-2}です。
次に(ii)です。
基本的に同じ解き方です。A,B,C,D,Eを並べるので、最初になる文字は5通りあります。なので、5通り場合分けが必要です(ですが、ほぼ2通りです)。
[1]Aで始まる場合。母音が連続しないので、2文字目はB,C,Dの3通りとなります。そして、残りのn-2文字は条件を満たすように並べられるのでd_{n-2}通りです。よって、3×d_{n-2} = 3d_{n-2}通りです。
[2]Bで始まる場合。2文字目はA,B,C,D,Eどれでもいいので、残りのn-1文字は条件を満たすように並べればいいのでd_{n-1}通り
[3]Cで始まる場合。Bのときと同じでd_{n-1}通り
[4]Dで始まる場合。Bのときと同じでd_{n-1}通り
[5]Eで始まる場合。Aのときと同じで3d_{n-2}通り
以上より、
d_n = 3d_{n-2} + d_{n-1} + d_{n-1} + d_{n-1}
+ 3d_{n-2}
= 3d_{n-1} + 6d_{n-2}
この漸化式を使って(iii)は得られます。
ありがとうございます！
丁寧な噛み砕いた説明で、よくわかりました！