#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]
&mimetex(b_n);とフィボナッチ数列&mimetex(p_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(X_n);は必ず1から始まり，&mimetex(X_{n-1});の後ろに&mimetex(X_{n-2});をつなげた形になっている．
また，先頭が必ず1であるため，&mimetex(X_{n-1});の最後が0の場合は，'01'の数がさらに1つ増える．規則より，最後の数字は0と1が交互に現れる．
よって，次式が言える
&mimetex(b_n=\left\{\begin{array}{lcl}b_{n-1}+b_{n-2}+1&:&n=odd\\b_{n-1}+b_{n-2}&:&else\end{array}); ただし&mimetex((n\ge3));
ここで，上記の式をまとめるために，数列&mimetex(c_n);を導入する．
&mimetex(c_n=\left\{\begin{array}{ccl}1&:&n=odd\\0&:&else\end{array});
これにより，&mimetex(b_n);は次式で表される．
&mimetex(b_n=b_{n-1}+b_{n-2}+c_n); ただし&mimetex((n\ge3));
**一般項 [#a3e2f70b]
&mimetex(b_n);と&mimetex(P_n);を一つズラして表をつくってみる．
|n|&mimetex(b_n);|&mimetex(p_{n-1});|&mimetex(X_n);|
|1|0|-|1|
|2|0|1|10|
|3|1|1|101|
|4|1|2|10110|
|5|3|3|10110101|
|6|4|5|1011010110110|
|7|8|8|101101011011010110101|
表を眺めると，&mimetex(b_n);の一般項として，次の式が浮かぶ．
&mimetex(b_n=\left\{\begin{array}{lcl}p_{n-1}-1&:&n=even\\p_{n-1}&:&else\end{array}); ただし&mimetex((n\ge2));
ここで&mimetex(c_n);を使ってさらに完結にし，
&mimetex(b_n=p_{n-1}-1+c_n); ただし&mimetex((n\ge2));
と表記する．さらに&mimetex(d_n=1-c_n);と定義して，
&mimetex(b_n=p_{n-1}-d_n); ただし&mimetex((n\ge2));
と仮定する．
***n=1の時 [#jf979cb8]
&mimetex(b_1=0);(定義)
***n=2の時 [#w078baad]
&mimetex(b_2=p_1-d_2=1-(1-c_n)=1-1+0=0);(成り立つ)
***n=3の時 [#j48d0104]
&mimetex(b_3=p_2-d_3=1-(1-c_n)=1-1+1=1);(成り立つ)
***nが成立するときのn+1 [#rfa6c27c]
&mimetex(b_n=p_{n-1}-d_n);かつ&mimetex(b_{n-1}=p_{n-2}-d_{n-1});の時，&mimetex(b_{n+1});は定義より以下のように表せる
&mimetex(b_{n+1}=(b_n)+(b_{n-1})+c_{n+1}=(p_{n-1}-d_n)+(p_{n-2}-d_{n-1})+c_{n+1});
&br();
&br();
&mimetex(=(p_{n-1}+p_{n-2})+(-d_n-d_{n-1}+c_{n+1})=p_n+(-d_n-d_{n-1}+c_{n+1}));
ここで，定義より，&mimetex(-d_n-d_{n-1}=-1);となるため，
&mimetex(b_{n+1}=p_n+(-d_n-d_{n-1}+c_{n+1})=p_n+(-1+c_{n+1}));
となる．また，&mimetex(d_n=1-c_n);であるため，
&mimetex(b_{n+1}=p_n+(-1+c_{n+1})=p_n+(-d_{n+1})=p_n-d_{n+1});
となる．この式は&mimetex(b_n=p_{n-1}-d_n); の&mimetex(n);を&mimetex(n+1);で置き換えた物である．
よって，数学的帰納法により証明された．
&mimetex(b_n=p_{n-1}-d_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\}-d_n);
ただし
&mimetex(b_n=p_{n-1}-d_n); &mimetex((n\ge2));
である．
*コメント [#l93b0a09]
見滝原中学校の授業で出題されていた1992年の東大入試問題である．
ジャンル[[:数学]]
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
