倭算数理研究所

科学・数学・学習関連の記事を、「倭マン日記」とは別に書いていくのだ！

トップ > 高校数学 > 魔法少女になるための教養

魔法少女になるための教養

高校数学 サブカルチャ

「今週のまどかマギカに出てきた数学の問題を復元してみた。誰か解いてね。」より。

【問題】

{ p_1 = 1,\, p_2 = 1,\, p_{n+2} = p_{n+1} + p_n \,(n \ge 1) } により定義される数列 { \{p_n\} } をフィボナッチ数列といい、その一般項は

　　{ \displaystyle p_n = \tfrac{1}{\sqrt{5}}\left\{\left(\tfrac{1+\sqrt{5}}{2}\right)^n-\left(\tfrac{1-\sqrt{5}}{2}\right)^n\right\} }

で与えられる。　この事実を踏まえて以下の問に答えよ。

各桁の数字が0か1である整数の列 { X_n\,(n=1,\,2,\,\cdots) } を次の規則により定める。
　(A) { X_1 = 1 }
　(B) { X_n } のある桁の数字 { \alpha } が0ならば{ \alpha } を1で置き換え、{ \alpha } が1ならば { \alpha } を10で置き換える。
{ X_n } の各行ごとにこのような置き換えを行って得られる自然数を { X_{n+1} } とする。　例えば、

　　{ \displaystyle X_1 = 1,\,X_2 = 10,\,X_3 = 101,\,X_4 = 10110,\, X_5 = 10110101,\,\cdots }

となる。
　(1) { X_n } の桁数 { a_n } を求めよ。
　(2) { X_n } の中に "01" という並びが現れる回数 { b_n } を求めよ。
（例） { b_1 = 0,\, b_2 = 0,\, b_3 = 1 }

【解答】

(1) { X_n } の桁数 { a_n } を求めよ。

{ X_n } に含まれている1の個数を { x_n }、0の個数を { y_n } とする。　(A) { X_1 = 1 } より

　　{ \displaystyle \begin{align*} x_1 &= 1 & \cdots(1) \\ y_1 & = 0 & \cdots(2) \end{align*} }

また、規則 (B) より以下の漸化式が成り立つ

　　{ \displaystyle \begin{align*} x_{n+1} &= x_n + y_n & \cdots(3) \\ y_{n+1} & = x_n & \cdots(4) \end{align*} }

☆{ x_n } の一般項を求める☆
(1), (2), (3) より

　　{ \displaystyle \begin{align*} x_2 &= x_1 + y_1 \\ &= 1 \end{align*} }

また、(3), (4) より

　　{ \displaystyle \begin{align*} x_{n+2} &= x_{n+1} + y_{n+1} \\ &= x_{n+1} + x_n \end{align*} }

よって

　　{ \displaystyle \begin{cases} x_1 = 1 \\ x_2 = 1 \\ x_{n+2} = x_{n+1} + x_n \end{cases} }

これはフィボナッチ数列 { p_n } の初項、第2項、漸化式に等しいので、{ x_n } はフィボナッチ数列に等しい。　つまり

　　{ \displaystyle x_n = p_n }

☆{ y_n } の一般項を求める☆
(4) より n≧2 のとき

　　{ \displaystyle \begin{align*} y_n &= x_{n-1} \\ & = p_{n-1} \end{align*} }

また (2) より

　　{ \displaystyle y_1 = 0 }

よって*1

　　{ \displaystyle y_n = \begin{cases}1 & (n = 1) \\ p_{n-1} & (n \ge 2)\end{cases} }

☆{ a_n } を求める☆
{ a_n } は { x_n }, { y_n } を使って

　　{ \displaystyle a_n = x_n + y_n }

と書ける。　上記で求めた { x_n }, { y_n } の一般項の表式より、n≧2 のとき

　　{ \displaystyle \begin{align*} a_n &= x_n + y_n \\ &= p_n + p_{n-1} \\ &= p_{n+1} \end{align*} }

ここで

　　{ \displaystyle \begin{align*} a_1 &= x_1 + y_1 \\ &= 1 \\ p_2 &= 1 \end{align*} }

より、この表式は n=1 のときも成り立つ。　よって、{ a_n } は

　　{ \displaystyle a_n = p_{n+1} }

となる。

(2) { X_n } の中に "01" という並びが現れる回数 { b_n } を求めよ。

☆n≧2 の場合☆
規則 (B) より、この規則を適用して "01" となる数字の並びは "10", "11" のいずれか。　つまり1の後に0もしくは1が続いていれば、規則 (B) を適用して "01" が現れる。　したがって、{ b_n } は { X_{n-1} } の1の個数（ただし一番右の位の1は除く）に等しい。

  • (1) より { X_{n-1} } の1の個数は { x_{n-1} = p_{n-1} }
  • { X_{n-1} } の一番右の位が1となるのは n が偶数のとき

よって

　　{ \displaystyle b_n = \begin{cases}p_{n-1} & (n:{\rm odd}) \\ p_{n-1}-1 & (n:{\rm even})\end{cases} }

☆n = 1の場合☆
{ X_1 = 1 } より

　　{ \displaystyle b_1 = 0 }

☆{ b_n } の一般項☆
以上の結果をまとめると*2
　　{ \displaystyle b_n = \begin{cases} 0 & (n=1) \\ p_{n-1} & (n:{\rm odd},\, n\ne1) \\ p_{n-1}-1 & (n:{\rm even})\end{cases} }

*1:pn の表式を n=0 に拡張して考えればまとめて書けますが、断り書き書くのは、それはそれで面倒。

*2:yn 同様、pn の表式を n=0 に拡張すればまとめて書けます。