Root One

数学中心のブログです。

フィボナッチ数列の隠れた非線形3項間漸化式

前回の記事

フィボナッチ数列の母関数とその応用例 - Root One

の議論をくりかえしていたら、ある線形でない3項間漸化式が見つかりました。

(一応断っておきますが、新発見だと主張するつもりはありません。経験上、少し議論をした程度で得られる初等的な結果というのは知られていないわけがないからです。)

フィボナッチ数列が満たす2次の漸化式

 f(n) を初項0のフィボナッチ数列、つまり

 \displaystyle f(n+2) = f(n+1) + f(n) \quad (f(0)=0,f(1)=1)

をみたすものとします。このとき

 \displaystyle g(n) = \frac{f(2^{n+1}) }{f(2^n)}

とおくと

 \displaystyle g(n+1) = g(n)^2-2 \quad (n\geq 1) \tag{1} \label{eq:gg22}

が成立します。

証明は、フィボナッチ数列の一般項を使用すればダイレクトにできます。

ところで、線形でない漸化式

 \displaystyle a_{n+1} = a_n^2 -2

というのは、通常は解けない(初等関数では表示できない)としたものですが、 -2 というのが絶妙な数で、この場合は一般的に a_n を表示できます。

ただあまりきれいにはなりませんのでここでは紹介しませんが、そんな解の一つとして

 \displaystyle a_n = \frac{f(2^{n+1}) }{f(2^n)} \quad (n \geq 1 ) 

がとれるというのは、ちょっと面白いかもしれません。

2べき番目のフィボナッチ数列が満たす3項間漸化式

\eqref{eq:gg22} によれば  c_n = f(2^n) とおくと、

 \displaystyle \frac{c_{n+2}}{c_{n+1}} =\left( \frac{c_{n+1}}{c_{n}} \right)^2 -2 \quad (n \geq 1 )

が満たされるので

 \displaystyle c_{n+2} = \frac{{c_{n+1}}^3}{c_n^2} -2c_{n+1}  \quad (n \geq 1 ) \tag{2} \label{eq:cnf2c}

が成り立ちます。

つまり、フィボナッチ数列2^n 番目の数列すらも、3項間漸化式を満たすことになるわけです。

こうして考えると、フィボナッチ数列というのは、その部分列に、多くの異なる種類の3項間漸化式が隠れた数列ということになりそうです。

実験例

\eqref{eq:cnf2c} によれば、 f(2), f(4) から始まって順番に

 \displaystyle f(8) , f(16) , f(32) ,f(64), \cdots

が求められるはずです。以下実験してみます。まず初期値を計算します。

 \displaystyle c_1 = f(2) = 1. \quad c_2= f(4)=3.

これから、漸化式を用いて計算していきます。

 \displaystyle f(8) = c_3 = \frac{{c_{2}}^3}{c_1^2} -2c_{2} = \frac{3^3}{1}-6 = 21. 

実際フィボナッチ数列の表を作成すると

n f(n)
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987

なので、正しい結果となっています。もう一つ計算すると

 \displaystyle f(16) = c_4 = \frac{{c_{3}}^3}{c_2^2} -2c_{3} = \frac{21^3}{3^2}-42 = 987

となりますが、やはり表からこれが正しいことが分かります。

手計算での確認はここらへんが限度かなという感じがしますが、計算機を使用するとかなりの番号まで確認できるはずです。