1】

F(2n-1)=F(n-1)^2 + F(n)^2

2】

F(2n)=F(n)*[F(n+1)+F(n-1)]

這裡

F(n)、F(n+1)、F(n-1)、F(2n)和F(2n-1)分別表示第n個、第n+1個、第n-1個、第2n個和第2n-1個Fibonacci數。

證明了這兩個公式，就可以快速計算第m個Fibonacci數。

例如計算F(1000)。

原來根據定義，需先計算F(998）和F(999)。

現在可利用公式2】，折半計算F(500)和F(499)。

而F(500)又可先折半計算F(250)和F(249)，同時據公式1】也得出了F(499)。

故可以把原先計算F(1000)所需計算999個F數，減少為僅需計算22個F數。