フィボナッチ数列

フィボナッチ数列の定義として、初項を0とする定義を選択する。つまり

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

として定義される数列$f(n)$をフィボナッチ数列として定義する。

フィボナッチ数列の最初の16項.

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...

フィボナッチ数列については多くの研究結果がある。

フィボナッチ数列の加法公式

次の加法公式が成立する。

\[ f(n+m) = f(n)f(m+1) + f(n-1)f(m) \]

右辺では、左辺の対称性から必然的に$n$と$m$を入れ替えても良いので

\[ f(n+m) = f(m)f(n+1) + f(m-1)f(n) \]

と書くこともできる。

証明.

帰納法によって簡単にできる。

フィボナッチ数列の母関数

\[ \frac{x}{1-x-x^2} = f(0)+f(1)x+f(2)x^2+\cdots + f(n)x^n + \cdots \] が成立する。

次の動画では母関数の導出方法と応用例を述べている。

この動画で述べている応用例は

$a_n = f(2n)$ とおいて、$a_n$ の母関数を得て、 \[a_{n+2} = 3a_{n+1} -a_n \] という漸化式を得るというものである。 つまり、フィボナッチ数列の偶数項だけを見た数列の漸化式を調べていることになる。

例.

フィボナッチ数列は

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 ...

となるがこの偶数項を抜き出すと

0 1 3 8 21 55 144 377 987 ...

となるが、これが数列 $a_n$ となる。

フィボナッチ数列の周期

フィボナッチ数列自体は単調増加のため、純粋な周期をもっていないが、 ある自然数で割った余りに注目すると、周期をもつ。この事実から、特に「下n桁」に注目すると周期をもつことが分かる。

例. フィボナッチ数列の下１桁は、周期60で循環する。

(f(0)~f(59))   011235831459437077415617853819099875279651673033695493257291
(f(60)~f(119)) 011235831459437077415617853819099875279651673033695493257291
以下循環して続く。

例2.　フィボナッチ数列の下２桁は、周期300で循環する。

$n \geq 3$に対して、フィボナッチ数列の下$n$桁は

を周期に持ち、循環する。

したがって、$f(a)$ と$f(a+15\cdot 10^{100})$ は 10 adic 的に非常に近い数となることが分かる。

特に$f(0)=0$だから、 \[ \lim_{n\to \infty} f(15\cdot 10^n) = 0 \quad \mbox{(10 adic の世界の等式) } \] が成立する。