数学的帰納法とフィボナッチ数の定義を用いてFib(n)=(φ^n-ψ^n)/√5 を証明する

SICPから次の問題を解いてみたいと思います。

問題

φ=(1+√5)/2 としてFib(n)がφ^n/√5　に最も近い整数であることを証明せよ。
ヒント：ψ=(1-√5)/2 とする。数学的帰納法とFibonacci数の定義を用いて　Fib(n)=(φ^n-ψ^n)/√5 を証明する。

証明

任意の自然数nについて、Fib(n)=(φ^n - ψ^n)/√5であることを証明する。

(1)n=0のとき

φ^0 = 1
ψ^0 = 1
右辺 = (φ^n-ψ^n)/√5
     = (1-1)/√5 = 0
左辺 = Fib(0) = 0
より、左辺 = 右辺 = 0

(2)n=1のとき

φ^1 = (1+√5)/2
ψ^1 = (1-√5)/2
右辺 = (φ^n - ψ^n)/√5
     = ((1+√5)/2 - (1-√5)/2)/√5 = 1
左辺 = Fib(1) = 1
より、左辺 = 右辺 = 1

(3)n=k, n=k+1（k>=0)のとき

Fib(k) = (φ^k - ψ^k)/√5
Fib(k+1) = (φ^k+1 - ψ^k+1)/√5 

を仮定すると、

(4)n=k+2（k>=0)のとき

φ^2 = ((1+√5)/2)^2
     = (1+√5)/2 + 1
     = φ+1

ψ^2 = ((1-√5)/2)^2
     = (1-√5)/2 + 1
     = ψ+1

より、

右辺 = (φ^k+2 - ψ^k+2)/√5
     = (φ^kφ^2 - ψ^kψ^2)/√5
　　 = (φ^k(φ+1) - ψ^k(ψ+1))/√5
　　 = ((φ^kφ+φ^k) - (ψ^kψ+ψ^k))/√5
     = (φ^(k+1) - ψ^(k+1))/√5 + (φ^k - ψ^k)/√5
     = Fib(k+1) + Fib(k)

Fib(n)の定義より、左辺 = 右辺

以上から、数学的帰納法により、任意の自然数nについて
Fib(n) = (φ^n - ψ^n)/√5であることが成立する。

・・・・

数学的帰納法とフィボナッチ数の定義を用いてFib(n)=(φ^n-ψ^n)/√5 を証明するところまでで今日はギブアップ。
問題であるFib(n)がφ^n/√5　に最も近い整数であることの証明に行き詰りました。。。

なんだか久しぶりに数学を解いてるって感じで、頭を使いました。
疲れたので、続きは明日に後日、再チャレンジです！