#contents

まどか☆マギカ第9話でクラスメイトが解いていた,ホワイトボード書かれていた数学の問題.「答えよ」と書かれていたので,答えてみた.

*例題 [#y1d19b65]
-&mimetex(p_1=1);,&mimetex(p_2=1);,&mimetex(p_{n+2}=p_{n+1}+p_n\left(n \ge 1\right));によって定義される数列&mimetex(\left{p_n\right});をフィボナッチ数列といい,その一般項は&br(); &br();
&mimetex(p_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}); &br(); &br();
で与えられる。この事実を用いて、次の問いに答えよ。

*問題 [#d90a5eb8]
-各桁の数字が0か1であるような自然数の列&mimetex(X_n\left(n=1,2,\cdots\right));を次の規則により定める.
+&mimetex(X_1=1);
+&mimetex(X_n);のある桁を&mimetex(\alpha);が0ならば&mimetex(\alpha);を1で置き換え,&mimetex(\alpha);が1ならば&mimetex(\alpha);を'10'で置き換える.&mimetex(X_n);の各桁ごとにこのような置き換えを行って得られる自然数を&mimetex(X_{n+1});とする.

-たとえば&mimetex(X_1=1);,&mimetex(X_2=10);,&mimetex(X_3=101);,&mimetex(X_4=10110);,&mimetex(X_5=10110101);,……となる.

**問題(1) [#l90cf3c1]
-&mimetex(X_n);の桁数&mimetex(a_n);を求めよ
**問題(2) [#ff95473d]
-&mimetex(X_n);の中に'01'という数字の配列が現れる回数&mimetex(b_n);を求めよ.
-(たとえば&mimetex(b_1=0);,&mimetex(b_2=0);,&mimetex(b_3=1);,&mimetex(b_4=1);,&mimetex(b_5=3);,……)

*解法 [#ib22b930]
**問題(1) [#f2017cd6]
&mimetex(X_n);の中の1の数を&mimetex(I_n);,0の数を&mimetex(O_n);と置く.

問題文より

&mimetex(a_n=I_n+O_n);

である.(自明)&br();
規則2より

&mimetex(\left{\begin{array}{l}I_n=I_{n-1}+O_{n-1}\\O_n=I_{n-1}\end{array});

が成り立つ.
今,&mimetex(O_{n-1});を&mimetex(I_n);で置き換えると

&mimetex(\left{\begin{array}{l}I_n=I_{n-1}+I_{n-2}\\O_n=I_{n-1}\end{array});

と変わり,&mimetex(I_n);がフィボナッチ数列と同じになる.
&mimetex(I_1=1);,&mimetex(I_2=1);より,

&mimetex(I_n=p_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\});

となる.よって,

&mimetex(O_n=I_{n-1}=p_{n-1}=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\right\});

となる.&br();
ここで,&mimetex(a_n);を書き換えると,フィボナッチ数列の定義より,

&mimetex(a_n=I_n+O_n=p_n+p_{n-1}=p_{n+1});

となる.よって

&mimetex(a_n=p_{n+1}=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right\});

となる.


**問題(2) [#c039c09c]
#stub

&mimetex(b_n=b_{n-2}+b_{n-1}+c_n);
&mimetex(b_n);とフィボナッチ数列&mimetex(p_n);をいくつか書いてみる

となる.ここで&mimetex(c_n);は
|n|&mimetex(b_n);|&mimetex(p_n);|&mimetex(X_n);|
|1|0|1|1|
|2|0|1|10|
|3|1|2|101|
|4|1|3|10110|
|5|3|5|10110101|
|6|4|8|1011010110110|
|7|8|13|101101011011010110101|

&mimetex(b_n);と&mimetex(P_n);を一つズラして表をつくってみる.

|n|&mimetex(b_n);|&mimetex(p_{n-1});|
|1|0|-|
|2|0|1|
|3|1|1|
|4|1|2|
|5|3|3|
|6|4|5|
|7|8|8|

どうやら,何か関係が見えてきた.

各&mimetex(X_n);は必ず1から始まり,&mimetex(X_{n-1});の後ろに&mimetex(X_{n-2});をつなげた形になっている.

また,先頭が必ず1であるため,&mimetex(X_{n-1});の最後が0の場合は,'01'の数がさらに1つ増える.規則より,最後の数字は0と1が交互に現れる.

ここで,

&mimetex(b_n=p_{n-1}-c_n);(ただし&mimetex(n \ge 2);において)

と仮定する.ここで&mimetex(c_n);は

&mimetex(c_n=\left\{\begin{array}{ccl}1&:&n=even\\0&:&else\end{array});

よって,(to be written)
とする.

&mimetex(b_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}+1-c_n);
***n=1の時 [#jf979cb8]

&mimetex(b_1=0);(定義)

***n=2の時 [#w078baad]

&mimetex(b_2=p_1-c_2=1-1=0);(成り立つ)

***n=3の時 [#j48d0104]

&mimetex(b_3=p_2-c_3=1-0=1);(成り立つ)

***nが成立するときのn+1 [#rfa6c27c]

&mimetex(b_n=p_{n-1}-c_n);の時,&mimetex(b_{n+1});は以下のように表せる

&mimetex(b_{n+1}=(b_n)+(b_{n-1})+1-c_{n+1}=(p_{n-1}-c_n)+(p_{n-2}-c_{n-1})+1-c_{n+1});
&br();
&br();
&mimetex(=(p_{n-1}+p_{n-2})+(-c_n-c_{n-1}+1-c_{n+1})=p_n-c_{n+1}+(-c_n-c_{n-1}+1));

ここで,定義より,&mimetex(-c_n-c_{n-1}+1=0);となるため,

&mimetex(b_{n+1}=p_n-c_{n+1});

となる.よって,数学的帰納法により証明された.

&mimetex(b_n=p_{n-1}-c_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\right\}-c_n);

ただし

&mimetex(c_n=\left\{\begin{array}{ccl}1&:&n=even\\0&:&else\end{array});

である.

*コメント [#l93b0a09]
見滝原中学校の授業で出題されていた1992年の東大入試問題である.

ジャンル[[:数学]]



トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS