证明Fib(n)是最接近Φ^n √5, 其中Φ=(1+√5)/2

Fib 的定义如下:

1
Fib(0) = 0
2
Fib(1) = 1
3
Fib(n) = Fib(n - 1) + Fib(n - 2) 当 n >= 2 时

我们设

img

img

先来证明 img


img

img

可知基础情况成立。而假设 img成立,有

img

img

img

于是

img

可知递归情况也成立。原命题得证。


sqrt(5) > 2 容易知道 γ 的绝对值

img

因此

img

img

而因为

img

于是有

img

换句话说,Fib(n) 是最接近img整数。