[SICP] 問題 1.13 : フィボナッチ数を求める代数方程式

Φ= (1+√5)/2としてFib(n)がΦⁿ/√5に最も近い整数であることを証明せよ. ヒント: Ψ= (1-√5)/2とする. 帰納法とFibonacci数の定義(1.2.2節参照)を用い, Fib(n)=(Φⁿ-Ψⁿ)/√5を証明せよ.

まず, Fib(n)=(Φⁿ-Ψⁿ)/√5を証明する.

(1) n=1のとき

Fib(1)	=	{Φ1-Ψ1} / √5
	=	{(1+√5)/2 - (1-√5)/2} / √5
	=	2√5 / √5
	=	1

(2) n=2のとき

Φ2	=	{(1+√5)/2}2
	=	{1 + 2√5 + 5} / 4
	=	{2 + 2√5 + 4} / 4
	=	{1 + √5} / 2 + 1
	=	Φ + 1

Ψ2	=	{(1-√5)/2}2
	=	{1 - 2√5 + 5} / 4
	=	{2 - 2√5 + 4} / 4
	=	{1 - √5} / 2 + 1
	=	Ψ + 1

Fib(2)	=	{Φ2-Ψ2} / √5
	=	{(Φ + 1) - (Ψ + 1)} / √5
	=	{Φ - Ψ} / √5
	=	1

(3) n=k, k+1のときFib(n)=(Φⁿ-Ψⁿ)/√5が成立すると仮定する. n=k+2のとき

Fib(k+2)	=	Fib(k+1) + Fib(k)
	=	(Φk+1-Ψk+1)/√5 + (Φk-Ψk)/√5
	=	{(Φk+1+Φk) - (Ψk+1+Ψk)} / √5
	=	{Φk(Φ+1) - Ψk(Ψ+1)} / √5
	=	{ΦkΦ2 - ΨkΨ2} / √5
	=	{Φk+2 - Ψk+2} / √5

(4) 以上より, 1以上の整数nについて, Fib(n)=(Φⁿ-Ψⁿ)/√5が成立する.

次に, Ψ/√5の値を計算する.

Ψ/√5 = (1-√5)/2 ≒ -0.2764

Ψ/√5 < 1/2 であるから, 1以上の整数nについて, Ψⁿ/√5 < 1/2 である.
よって、Fib(n)がΦⁿ/√5に最も近い整数であるといえる.