Fibonacci 数列

Fibonacci (フィボナッチ Leonardo da Pisa, Leonardo Pisano, ピサのレオナルド) の Liber Abbaci (算術書), 1202 (1828 再版) の問題:

一番 (つが) いの兎が一ヶ月毎に一番いの兎を生み, 生まれた一番いは二ヶ月後から子を生み始めるとする。 兎が死なないとすると, 一年後に新しい子が生まれたとき, 全部で何番いになるか ?

解答: n ヶ月後の兎の数を a_n とする。 n ≧ 2 の時, 「n ヶ月後の番いの数」 は 「その一ト月前の番いの数」 に 「その二月前の番いが生む番いの数」 を加えたものに等しい。 即ち

a_n = a_n-1 + a_n-2, n ≧ 2 … (a)

又明らかに a₁ = 1, a₂ = 2, よって

答: 233 番い

普通漸化式 (a) を満たし a₁ = a₂ = 1 の数列を Fibonacci 数列, その各々の項を Fibonacci 数という。 又 a₁ = 1, a₂ = 3 として漸化式 (a) を満たす数列を Lucas (リュカ) 数列, その各々の項を Lucas 数という。

漸化式 (a) の特性方程式 t² - t - 1 = 0 より, t = (1 ± √5)/2. 故

a_n+1 - ((1 - √5)/2)a_n = ((1 + √5)/2)^n-1(1 - (1 - √5)/2) = ((1 + √5)/2)ⁿ.

同様に

a_n+1 - ((1 + √5)/2)a_n = ((1 - √5)/2)ⁿ.

辺々引いて

(√5)a_n = ((1 + √5)/2)ⁿ - ((1 - √5)/2)ⁿ.

故に a_n = (((1 + √5)/2)ⁿ - ((1 - √5)/2)ⁿ)/√5. [Binet (ビネ, Jacques Phillippe Marie, 1786 -- 1850)]

このように, Fibonacci 数列 {a_n} は全ての項が自然数であるにもかかわらず無理数を使わなければその一般項は書けない。

同様に, 漸化式 a_n+2 - a_n+1 + 2a_n = 0, a₁ = 1, a₂ = 4 ではその全ての項が整数であるにもかかわらず, 一般項を書くには虚数が必要である。 実際

a_n = ((-14 + i√7)((1 + i√7)/2)^n-1 - (14 + i√7)((1 - i√7)/2)^n-1)/7.

Fibonacci 数列については次の事実も知られている。

a₁ = a₂ = 1, a_n+2 = a_n+1 + a_n
⇒
a_m+n = a_ma_n+1 + a_m-1a_n.

証明は数学的帰納法, 又は Binet の公式を代入してみればよい。

その他にも幾つかの性質が知られているようである。

上記の公式を数学的帰納法で示すやり方は, 今までこの site でやって来ているものと一寸違うことに気付いたので, 一応その証明を書いておく。

n = 1 の場合。

a_m+1 = a_ma₂ + a_m-1a₁ = a_m + a_m-1 というのは定義式そのものである (番号が一つずれているけれども)。

n = 2 の場合。

rhs = 2a_m + a_m-1
= 2a_m + a_m+1 - a_m (∵a_m+1 = a_m + a_m-1)
= a_m+1 + a_m
= a_m+2 = lhs.

n = k, k - 1 の時の成立を仮定する。

n = k + 1 の時

lhs = a_m+ka₂ + a_m+k-1a₁ (m+k+1 = (m+k) + 1 と考えた)後半は m + (k-1) と思う)
= (a_ma_k+1 + a_m-1a_k) + (a_ma_k + a_m-1a_k-1) (後半は m + (k-1) と思う)
= a_m(a_k+1 + a_k) + a_m-1(a_k + a_k-1)
= a_ma_k+2 + a_m-1a_k = rhs.■

参考文献. かずかずの数, 数学セミナー (11), 1986.

次へ
漸化式の目次へ