「今週のまどかマギカに出てきた数学の問題を復元してみた。誰か解いてね。」より。
【問題】
により定義される数列
をフィボナッチ数列といい、その一般項は
で与えられる。 この事実を踏まえて以下の問に答えよ。
各桁の数字が0か1である整数の列
を次の規則により定める。
(A)
(B)のある桁の数字
が0ならば
を1で置き換え、
が1ならば
を10で置き換える。
の各行ごとにこのような置き換えを行って得られる自然数を
とする。 例えば、
となる。
(1)の桁数
を求めよ。
(2)の中に "01" という並びが現れる回数
を求めよ。
(例)
【解答】
(1)
の桁数
を求めよ。
また、規則 (B) より以下の漸化式が成り立つ
☆
の一般項を求める☆
(1), (2), (3) より
また、(3), (4) より
よって
これはフィボナッチ数列 の初項、第2項、漸化式に等しいので、
はフィボナッチ数列に等しい。 つまり
☆
の一般項を求める☆
(4) より n≧2 のとき
また (2) より
よって*1
☆
を求める☆
と書ける。 上記で求めた ,
の一般項の表式より、n≧2 のとき
ここで
より、この表式は n=1 のときも成り立つ。 よって、 は
となる。
(2)
の中に "01" という並びが現れる回数
を求めよ。
☆n≧2 の場合☆
規則 (B) より、この規則を適用して "01" となる数字の並びは "10", "11" のいずれか。 つまり1の後に0もしくは1が続いていれば、規則 (B) を適用して "01" が現れる。 したがって、- (1) より
の1の個数は
の一番右の位が1となるのは n が偶数のとき
よって
☆n = 1の場合☆