>>200
■問題1









a^nのうち末尾0の個数をa^n(0)、末尾1の個数をa^n(1)としたとき

a^n = a^n(0) + a^n(1)

ここで、a^n-1に含まれる数列の末尾が1と0のどちらでも、その後に1を付加した数列は
a^nに含まれる。一方、0を付加することができるのは末尾が1の場合のみ。
このことから、

a^n(0) = a^n-1(1)
a^n(1) = a^n-1

つまり

a^n
= a^n(1) + a^n(0)
= a^n-1 + a^n-1(1)
= a^n-1 + a^n-2