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

例題

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

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

    で与えられる。この事実を用いて、次の問いに答えよ。

問題

  • 各桁の数字が0か1であるような自然数の列X_n\left(n=1,2,\cdots\right)を次の規則により定める.
  1. X_1=1
  2. X_nのある桁を\alphaが0ならば\alphaを1で置き換え,\alphaが1ならば\alphaを'10'で置き換える.X_nの各桁ごとにこのような置き換えを行って得られる自然数をX_{n+1}とする.
  • たとえばX_1=1X_2=10X_3=101X_4=10110X_5=10110101,……となる.

問題(1)

  • X_nの桁数a_nを求めよ

問題(2)

  • X_nの中に'01'という数字の配列が現れる回数b_nを求めよ.
  • (たとえばb_1=0b_2=0b_3=1b_4=1b_5=3,……)

解法

問題(1)

X_nの中の1の数をI_n,0の数をO_nと置く.

問題文より

a_n=I_n+O_n

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

\left{\begin{array}{l}I_n=I_{n-1}+O_{n-1}\\O_n=I_{n-1}\end{array}

が成り立つ. 今,O_{n-1}I_nで置き換えると

\left{\begin{array}{l}I_n=I_{n-1}+I_{n-2}\\O_n=I_{n-1}\end{array}

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

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\}

となる.よって,

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\}

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

a_n=I_n+O_n=p_n+p_{n-1}=p_{n+1}

となる.よって

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)

b_nとフィボナッチ数列p_nをいくつか書いてみる

nb_np_nX_n
1011
20110
312101
41310110
53510110101
6481011010110110
7813101101011011010110101

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

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

よって,次式が言える

b_n=\left\{\begin{array}{lcl}b_{n-1}+b_{n-2}+1&:&n=odd\\b_{n-1}+b_{n-2}&:&else\end{array} ただし(n\ge3)

ここで,上記の式をまとめるために,数列c_nを導入する.

c_n=\left\{\begin{array}{ccl}1&:&n=odd\\0&:&else\end{array}

これにより,b_nは次式で表される.

b_n=b_{n-1}+b_{n-2}+c_n ただし(n\ge3)

一般項

b_nP_nを一つズラして表をつくってみる.

nb_np_{n-1}X_n
10-1
20110
311101
41210110
53310110101
6451011010110110
788101101011011010110101

表を眺めると,b_nの一般項として,次の式が浮かぶ.

b_n=\left\{\begin{array}{lcl}p_{n-1}-1&:&n=even\\p_{n-1}&:&else\end{array} ただし(n\ge2)

ここでc_nを使ってさらに完結にし,

b_n=p_{n-1}-1+c_n ただし(n\ge2)

と表記する.さらにd_n=1-c_nと定義して,

b_n=p_{n-1}-d_n ただし(n\ge2)

と仮定する.

n=1の時

b_1=0(定義)

n=2の時

b_2=p_1-d_2=1-(1-c_n)=1-1+0=0(成り立つ)

n=3の時

b_3=p_2-d_3=1-(1-c_n)=1-1+1=1(成り立つ)

nが成立するときのn+1

b_n=p_{n-1}-d_nかつb_{n-1}=p_{n-2}-d_{n-1}の時,b_{n+1}は定義より以下のように表せる

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}

=(p_{n-1}+p_{n-2})+(-d_n-d_{n-1}+c_{n+1})=p_n+(-d_n-d_{n-1}+c_{n+1})

ここで,定義より,-d_n-d_{n-1}=-1となるため,

b_{n+1}=p_n+(-d_n-d_{n-1}+c_{n+1})=p_n+(-1+c_{n+1})

となる.また,d_n=1-c_nであるため,

b_{n+1}=p_n+(-1+c_{n+1})=p_n+(-d_{n+1})=p_n-d_{n+1}

となる.この式はb_n=p_{n-1}-d_nnn+1で置き換えた物である. よって,数学的帰納法により証明された.

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

ただし

b_n=p_{n-1}-d_n (n\ge2)

である.

コメント

見滝原中学校の授業で出題されていた1992年の東大入試問題である.

ジャンル:数学


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-03-28 (月) 17:39:24 (2433d)