解説要約

• 方針・初手
• 文字列の長さは $n$ とともに指数的に増加するため、直接すべての文字列を書き下して行列を計算することは不可能です。そこで、文字列 $z_n$ の構成規則から、$z_n$ に関する漸化式を導き出すことを考えます。
• 「規則に従って文字を置き換える」という操作は、文字列を分割してからそれぞれ置き換えて結合しても結果が変わらないという性質を持っています。これを利用して $z_{n+2}$ を $z_{n+1}$ と $z_n$ で表す関係式を見つけ、それを行列の漸化式に翻訳して数学的帰納法を用います。