着想メトロ

アイデアとは、世界の捉え方を再構成することで新たな価値を獲得し、さらにそれを経験によって持続させる、一連のプロセスのこと。

ゴールデンナンバー

数列とは

 いまここにある一変数写像があるとしよう:\[ y=f(x). \]これはこちらがある入力\( \; x \; \)を選んだとき、出力\( \; y \; \)を定めるアルゴリズム\( \; f \; \)を表している。

 では次に似ているが次のような写像を考えてみよう:\[ x_{n+1}=f(x_{n}). \]入力と出力の下に添え字\( \; n \; \)が付けられている。

 おおざっぱに言ってしまうとこれは「時間」を意味する。「ステップ」と言ってもいい。つまり「ある時間の入力」に対して、「その次の時間での出力」を決めるアルゴリズムを表している。最初の例との違いは順序づけられているかいないかである。

 前者はこちらの入力に対して出力がポンと出てきて終わりだが、後者は出力が出てくるとそれが次の入力になって、その次の出力が出てきて……というふうにドミノ倒しのように出力の系列が得られる。例を挙げよう。

 「数える」というアルゴリズムを表してみると以下のようになる:\[ x_{n+1}=x_{n}+1, \;\;\; n=1, \; 2, \; 3, \ldots \]これはある時点での入力と、それに対応する出力を抽象的に結びつける関係だから、たったひとつの式で無限個の関係式が得られる。それを見てみよう。まだ数えていない状態は\( \; 0 \; \)個だから、これを最初の状態として採用する:\[ x_{1}=0. \]この数を入力してみると、出力としてその次の値が得られる。つまり上記のアルゴリズムに\( \; n=1 \; \)を入れてみると、\[ x_{2}=x_{1}+1=1. \]こうして新たな出力が得られたので、今度はこれを入力する:\[ x_{3}=x_{2}+1=2. \]このようにして無限個の数の系列\( \; \{ 0, \;1, \;2, \;3, \;4, \ldots \} \; \)が得られるわけだ。

 だから初期値を決めると(最初のドミノを倒すと)、アルゴリズムに従った出力の無限系列が自動的に生成される。このように、\( \; n \; \)番目の入力と\( \; n+1 \; \)番目の出力を結びつける関係を「漸化式」という。上の「数える」場合は「二項間漸化式」となる。漸化式によって得られる出力の系列を「数列」と呼ぶ。

漸化式から「ある時間での出力値」をその時間を用いて表したい

 「漸化式があるならそんなもん求めなくたっていいだろ」と思われるかもしれないが、実はそうでもないのだ。例えば100番目の出力値を求めたいのなら初期値から愚直に計算してもなんとかなる。では10億番目の出力値を求めたいときはどうだろう。一般に時間が先にいくにつれ、出力値の計算にかかる手間は増していくのだ。

 「だったら任意の時点での出力値を時点の関数として表しちまえばいい」これが動機である。これを「一般項」という。つまりいまある漸化式\[ x_{n+1}=f(x_{n}) \]があるとして、もし\[x_{n}=g(n)\]というふうに、一般項のかたちで時間の関数として第\( \; n \; \)番目の出力値を求められたなら、どの時点の値も即座に知ることができる。

 一般に数列が目の前にあるときは、漸化式のほうを見抜くほうが易しい。逆に数列からその一般項を求めるのは往々にして困難である。そこで次なる課題は、「漸化式がわかっているとして、そこから一般項をどう求めるか」となる。

「等差数列」「等比数列」そしてそれらの応用

 一般項がちゃんと求まる漸化式として、ここではもっとも重要なものを取り上げる。すなわち「等差数列」と「等比数列」だ。等差数列は\[ x_{n+1}=x_{n}+\Delta \]と表される漸化式から生成される数列のことだ。これをちょっと変形すると、\[ x_{n+1}-x_{n}=\Delta=\mathrm{(con st.)} \]となる。つまり二項間の差が一定値だから「等差」数列なわけだ。ここで(const.)は「一定」であることを表す。差が時間に関して不変なのだから、これをうまく利用しようと思うのは普通だろう。いつでも不変量は問題の本質を見抜くのに大切だ。

 すべての\( \; n \; \)に関して隣り合う項の差が等しいことから、次のような一連の漸化式を得る:\[ \begin{eqnarray*} \Delta &=& x_{n}-x_{n-1} \\ &=& x_{n-1}-x_{n-2} \\ &\vdots& \\  &=& x_{3}-x_{2} \\ &=& x_{2}-x_{1}. \end{eqnarray*} \] これらをダイナミックに辺々足してしまうと中間の項がうまく打ち消し合って、\[ (n-1)\Delta=x_{n}-x_{1} \]となる。よく見ると一般項が求まっているではないか!\[ x_{n}=x_{1}+(n-1)\Delta. \]

これでどんな等差数列の一般項も求まる公式が得られたので、早速最初の「数える」例に適用してみよう。この場合一定である差の部分が1なので、\[ x_{n}=0+(n-1) \cdot 1=n-1. \]

 では次に等比数列を見てみよう。それは\[ x_{n+1}=rx_{n} \]と表される漸化式から生成される数列だ。これは比較的簡単に一般項が求まる。番号がひとつ増えるごとに\( \; r \; \)が一回掛かるのだから、隣り合う項で比をとるとそれは\( \; r \; \)に等しい:\[ x_{n+1}/x_{n}=r. \]今度はこの比が時間に関係のない不変量だ。ところで\[ x_{n}=\dfrac{x_{n}}{x_{n-1}}\cdot\dfrac{x_{n-1}}{x_{n-2}}\ldots\dfrac{x_{3}}{x_{2}}\cdot\dfrac{x_{2}}{x_{1}}\cdot x_{1} \]なのでここにさきほどの不変量を代入すれば、\[ x_{n}=r^{n-1}x_{1}. \]

 最後にこの二つの代表的な漸化式を組み合わせた、次のような漸化式を考えよう:\[ x_{n+1}=rx_{n}+\Delta. \]これは前のやり方を繰り返せば一般項を求めることができる。まずは不変量となっている差の部分から同様にして新たな漸化式をつくる:\[ \Delta = x_{n+2}-rx_{n+1}=x_{n+1}-rx_{n}. \]これから\[  y_{n+1}=ry_{n}, \;\;\; n=1, \; 2, \; 3, \ldots\]を得る。ここで\[ y_{n}=x_{n+1}-x_{n} \]とおいた。このようにある漸化式があるとき、あらたな数列を定義することでより簡単な漸化式へと変形することは今度重要なテクニックになる。数列\( \; \{y_{n}\} \; \)は等比数列となっているからさきほど求めた公式を適用すれば、\[ \begin{eqnarray*} x_{n+1}-x_{n} &\equiv& y_{n}=r^{n-1}y_{1} \\ &=& r^{n-1}(x_{2}-x_{1}). \end{eqnarray*} \] さて、ここから一般項を捻り出すには、等比数列の和の公式を導いておくとよい。つまり等比数列を\( \; n \; \)番目まで足し合わせた和を、\( \; n \; \)の関数として表すのである。この和を第\( \; n \; \)部分和と呼び\( \; S(n) \; \)とおく。すると\[ S(n)=x_{1}+x_{2}+\ldots+x_{n}=x_{1}(1+r+r^{2}+\ldots+r^{n-1}). \]これから\[\begin{eqnarray*} S(n)-rS(n) &=& x_{1}\{(1+r+r^{2}+\ldots+r^{n-1})-(r+r^{2}+\ldots+r^{n-1}+r^{n})\} \\ &=& x_{1}(1-r^{n}) \end{eqnarray*}\]となるので\[ S(n)=x_{1}\cdot\dfrac{1-r^{n}}{1-r}. \]もちろん\( \; r \neq 1 \; \)とするのである。

 これを用いていよいよ一般項を求める。\[ \begin{eqnarray*} x_{n}-x_{n-1}&=&r^{n-2}y_{1}, \\ x_{n-1}-x_{n-2} &=& r^{n-3}y_{1}, \\ &\vdots& \\ x_{2}-x_{1} &= &y_{1} \end{eqnarray*} \]の辺々をダイナミック足し算することで、\[ \begin{eqnarray*} x_{n}-x_{1} &=& y_{1}(1+r+r^{2}+\ldots+r^{n-2}) \\ &=& (x_{2}-x_{1})\cdot \dfrac{1-r^{n-1}}{1-r}. \end{eqnarray*} \]こうして一般項が求まった。見やすく整理すると、\[ x_{n}=r^{n-1}x_{1}+\dfrac{1-r^{n-1}}{1-r}\cdot\Delta \] となる。

フィボナッチ数列(準備)

 さて、ようやくこの記事で扱いたかった話題に入る。フィボナッチ数列とは次のような「三項間漸化式」から生成される数列である:\[ x_{n+2}=x_{n+1}+x_{n}. \]ここで\[ x_{1}=x_{2}=1. \]前とその前の項を足した数が次の項になる、という一見シンプルな漸化式である。ただこの数列は驚くべき普遍性を備えた「ある数」と密接に関係している。さしあたりそこら辺の話題は置いておき、これを純粋に数学的対象とみなして一般項を求めてみよう。

 とはいってもこれは二項間でなく三項間の漸化式であるからそれほど簡単ではない。そこでなんとかして、三項間の漸化式を二項間のそれに落とし込みたい。ここであるテクニックが必要なのだが、それは「等比数列に変形できたらなあ」という発想である。確かに等比数列に変換できたらその後の扱いに便利そうであるが、問題はどう変形するかということだ。そもそも等比数列に変換できるのか。そこをみていこう。

 考えられる最も簡単な形は、\( \; \alpha x_{n+1}+\beta x_{n} \; \)という塊で等比数列になっている場合だろう。つまり\[ \alpha x_{n+2}+\beta x_{n+1}=r(\alpha x_{n+1}+\beta x_{n}) \]という形に変形できたとすれば、これは等比数列になっているので二項間の漸化式に落とし込めたことになる。では上式をばらしてみよう。\[ x_{n+2}=(r-\beta/\alpha )x_{n+1}+r\beta /\alpha x_{n}. \]これとフィボナッチ数列の漸化式を比べれば、\[ r-\dfrac{\beta}{\alpha}=1, \;\;\; r\dfrac{\beta}{\alpha}=1 \]を得る。これをじっと見るとあることに気づくのだがどうだろうか。少し無理があるかもしれない。「解と係数の関係」というものを知っているだろうか。

解と係数の関係

 二次方程式とは、\[ ax^{2}+bx+c=0 \]という形の方程式である。ここでもちろん「二次」であるためには\( \; a \neq 0 \; \)でなければならない。以下では簡単のため\( \; a>0 \; \)を仮定しよう。

 この方程式を満たす解を知りたいのだが、どうすればいいだろうか。左辺の二次関数は放物線を描く。これはよく知られた事実である。なのでこれを既知の情報として解の表式を求めたい。放物線は軸に対して左右対称である。この対称性はある種の不変性(軸に対する反転に関して不変)なので、これを存分に生かしたい。そのためにはまず軸の位置を求めなければならないのだが、これには二次関数を平方完成すればよい:\[ ax^{2}+bx+c=a(x+b/2a)^{2}-b^{2}/4a+c. \]この変形でどうして軸の位置がわかるのだろうか。それは、軸のある位置で放物線は最小値をとるということがわかっているからだ。上のように変形すれば、二乗で括られた部分は必然的にゼロ以上の値をとるので、この部分がゼロであるとき二次関数は最小値をとることがわかる。つまり軸の位置\( \; x_{0} \; \)は平方されている項をゼロにする値であって、\[ x_{0}=-\dfrac{b}{2a}. \]

 元の二次方程式は、この放物線と水平軸が交わる点をその解としてもつ。よって対称性により軸から等距離にあるはずだ。その距離を\( \; t \; \)とおくと、二つの交点の位置\( \; x^{+}, \; x^{-} \; \)は\[ x_{+}=x_{0}+t, \;\;\; x_{-}=x_{0}-t \]と表される。これから二つの解が満たさなければいけない第一の条件式が得られる:\[ x_{+}+x_{-}=2x_{0}. \]さて解を得るには少なくともあとひとつ別の条件式が必要だ。まずこの二つの解は、与えられた二次方程式の解なのだから次の等式を満たしている。\[ \begin{cases} ax_{+}^{2}+bx_{+}+c=0 \\ ax_{-}^{2}+bx_{-}+c=0.\end{cases}\]この辺々を足して少し変形すれば\[ x_{+}^{2}+x_{-}^{2}=(b/a)^{2}-2c/a \]を得る。どうしてこれを求めたかというと、次の恒等式に利用したかったからだ。すなわち\[ (x_{+}+x_{-})^{2}=(x_{+}^{2}+x_{-}^{2})+2x_{+}x_{-}. \]このうちの二項はすでに求まっているので、二解の積の表式が得られる:\[ x_{+}x_{-}=\dfrac{c}{a}. \]

 以上をまとめると、解と係数の関係\[ \begin{cases} x_{+}+x_{-} = -b/a, \\ x_{+}\cdot x_{-}= c/a. \end{cases} \]が求まった。これとさきほどフィボナッチ数列に関して得られた関係式\[ \begin{cases} r-\beta/\alpha=1, \\ r\cdot(\beta/\alpha)=1 \end{cases} \]を比べれば、対応関係\[  (x_{+}, \; x_{-})=(r, \; -\beta/\alpha) \]が成り立っていることがわかる。つまり、\( \; r, \; -\beta/\alpha \; \)は、その係数が\[ -b/a=1, \;\;\; c/a=-1 \]という関係式を満たすような二次方程式の解となっていることを知るのである。そのような二次方程式の形は\[ x^{2}-x-1=0 \]である。これをよく観察すれば、対応関係\[ \begin{cases} x_{n+2} &\rightarrow& x^{2}, \\ x_{n+1} &\rightarrow& x, \\ x_{n} &\rightarrow& 1 \end{cases} \]が存在していることがわかる。つまり任意の三項間漸化式に対して、上の対応関係に従って置き換えた後で得られる二次方程式を解けば、その二解を用いて二項間漸化式に変形することができる。

 解と係数の関係を使えば、有名な二次方程式の解の公式が求まる:\[ x_{\pm}=\dfrac{-b\pm\sqrt{b^{2}-4ac}}{2a}. \]これを使ってフィボナッチ数列に対応する二つの解を求めると、\[ \varphi_{\pm}=\dfrac{1\pm\sqrt{5}}{2} \]となる。この大きい方の解\( \; \varphi_{+} \; \)を「黄金数」と呼ぶこともある。

フィボナッチ数列(一般項)

 これで準備が整った。一番最初に、等比数列へと変形しようと試みて仮定した形を、うまく\( \; \varphi_{\pm} \; \)で表してみよう。\[ x_{n+2}-(-\beta/\alpha) x_{n+1}=r(x_{n+1}-(-\beta/\alpha)x_{n}) \]となるので結局\[ x_{n+2}-\varphi_{-}x_{n+1}=\varphi_{+}(x_{n+1}-\varphi_{-}x_{n}) \]と変形できる!前と同じように\[ y_{n}=x_{n+1}-\varphi_{-}x_{n}, \;\;\; n=1, \; 2, \;3, \ldots \]とおけば\[ y_{n+1}=\varphi_{+}y_{n} \]となるから\[ y_{n}=x_{n+1}-\varphi_{-}x_{n}={\varphi_{+}}^{n-1}y_{1}. \]ところで\[ y_{1}=x_{2}-\varphi_{-}x_{1}=\varphi_{+} \]なので、これを用いてちょちょっと変形すると\[ \dfrac{x_{n+1}}{{\varphi_{+}}^{n}}=\varphi\dfrac{x_{n}}{{\varphi_{+}}^{n-1}}+1 \]となる。ここで\[ \varphi = \dfrac{\varphi_{-}}{\varphi_{+}}. \]

 いま\[ c_{n}=\dfrac{x_{n}}{{\varphi_{+}}^{n-1}} \]とおくと\[ c_{n+1}=\varphi c_{n}+1 \]なる漸化式が得られるが、この一般項は前に求めておいた。この場合\( \; \Delta=1, \; r=\varphi \; \)であるので\[ c_{n}=\varphi^{n-1}c_{1}+\dfrac{1-\varphi^{n-1}}{1-\varphi}=\dfrac{1-\varphi^{n}}{1-\varphi} \]となる。以上でフィボナッチ数列の一般項がついに求まった:\[ \begin{eqnarray*} x_{n}&=&{\varphi_{+}}^{n-1}\cdot\dfrac{1-\varphi^{n}}{1-\varphi} \\ &=& \dfrac{{\varphi_{+}}^{n}-{\varphi_{-}}^{n}}{\varphi_{+}-\varphi_{-}}. \end{eqnarray*}. \]具体的に数値を代入すれば、\[ x_{n}=\dfrac{1}{\sqrt{5}}\left [ \left ( \dfrac{1+\sqrt{5}}{2} \right )^{n}-\left ( \dfrac{1-\sqrt{5}}{2} \right )^{n} \right ]. \]

 どうだろうか。まさか無理数が出てくるとは思いもしなかったのではないだろうか。というのも、初期条件\( \; x_{1}=x_{2}=1 \; \)のもとで数列を計算していくと、\[ 1, \;1, \; 2, \; 3, \; 5, \; 8, \; 13, \; 21, \; 34, \; 55, \; 89, \ldots \]というふうに、当然自然数の系列が出てくるからだ。

 また、この数列で隣り合う項の比によって生成される数列を新たに定義すると、その極限は黄金数に等しい。すなわち\[ \varphi_{n}=x_{n+1}/x_{n} \]とおけば\[ \lim_{n \to \infty} \varphi_{n}=\varphi_{+}. \]これはさきほど求めた一般項から直ちにわかるが、ここではもうひとつ簡単に極限値を求める方法を紹介しておこう。極限値\( \; \varphi_{+} \; \)が存在することがわかれば(これについての証明はこの記事の最後の補遺へと載せておくので、気になる方は参考にして頂きたい)、\[ \lim_{n \to \infty}\varphi_{n+1}=\lim_{n \to \infty}\varphi_{n} \]がもちろん成り立つ。ところで\( \; x_{n+2}=x_{n+1}+x_{n} \; \)の両辺を\( \; x_{n+1} \; \)で割れば\[ \varphi_{n+1}=1+\dfrac{1}{\varphi_{n}} \]となるからこの両辺の極限ととると、\[ \varphi_{+}=1+\dfrac{1}{\varphi_{+}}. \]この方程式を解けば黄金数が出てくる。もちろん解は二つ出てくるが、正の方をとるのである。

至る所に黄金数

 黄金数は動植物、宇宙、芸術、人体など至る所に遍在する。そのあたりを包括した良書として『黄金比はすべてを美しくするか?』はオススメである。

黄金比はすべてを美しくするか?―最も謎めいた「比率」をめぐる数学物語

黄金比はすべてを美しくするか?―最も謎めいた「比率」をめぐる数学物語

 

線分ABがあるとして、この線分をその内点Cで二分割したいとする。それもただの二分割ではなくて、「CBを長さの基準にしたときに、ABとACの比がACとCBの比に等しくなる」ような内点Cで分割したとする。この条件を式で表してみると、ACを\( \; x \; \)として\[ \dfrac{1+x}{x}=\dfrac{x}{1}. \]この二次方程式を解けば黄金数が出てくる。この分割を「黄金分割」ともいう。

 また\( \; x \; \)として次のような値を考えてみる:\[ x=\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\ldots}}}}. \]この両辺を二乗すれば\[ x^{2}=1+\sqrt{1+\sqrt{1+\sqrt{1+\ldots}}}=1+x \]となってまたもや黄金数が出てくる。

 さらに\[ x=1+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1+\ldots}}} \]とおけば、右辺第二項の分母は\( \; x \; \)にほかならないので\[ x=1+\dfrac{1}{x} \]が出てきて黄金数が現れる。このように連分数で表現することもできるのだ。ちなみに\[ \varphi_{3}=\dfrac{x_{4}}{x_{3}}=1+\dfrac{x_{2}}{x_{3}}=1+\dfrac{x_{2}}{x_{2}+x_{1}}=1+\dfrac{1}{1+1} \]のようにすでに有限時間で連分数の形が出てきていることにも注意。

 またフィボナッチ数列は「らせん」と切っても切れない縁を持つ。フィボナッチ数列の各項と同じ長さの正方形のタイルを敷き詰めていくと、そこにらせん構造が現れる。以下のページも参照のこと:

夢のもつれの哲学2:黄金比とフィボナッチ数列 はじめの1〜ベンフォードの法則 ラマヌジャン〜孤高の天才 唯幻論物語 鏡よ鏡 聖母マリアは処女だったのか?

補遺――極限値の存在証明

 コーシー列であることがわかれば収束が示せる。よってこの方針でいく。\[ \varphi_{n+1}-\varphi_{n} \equiv \Delta_{n} \]とおいて\( \; |\Delta_{n+1}/\Delta_{n}| \; \)を計算すると、\[ \left | \dfrac{\Delta_{n+1}}{\Delta_{n}} \right |=\dfrac{1}{1+\varphi_{n}} \leq \dfrac{1}{2} \]が導ける。ここで\[ \begin{cases} \varphi_{n+1}\cdot\varphi_{n}=1+\varphi_{n}, \\ \varphi_{n} \geq 1, \;\;\; n=1, \; 2, \; 3, \ldots \end{cases} \]を用いた。すると\[ |\varphi_{n+l}-\varphi_{n}|\leq \sum_{k=n}^{n+l-1}|\Delta_{k}|\leq|\Delta_{n}|(1+\dfrac{1}{2}+\dfrac{1}{2^{2}}+\ldots+\dfrac{1}{2^{l-1}})=|\Delta_{n}|\dfrac{1-1/2^{l}}{1-1/2}<2|\Delta_{n}|. \]\( \Delta_{n} \; \)の絶対値は単調に減少していくのだから、これは数列\( \; \{\varphi_{n}\} \; \)がコーシー列であることを示している。よって収束するので極限値を持つことがわかった。