Binet’in f(n) = (x1n - x2n) / (x1 - x2) formülünü aşağıdaki adımları takip ederek elde edebiliriz:
Yukardaki mesajda, Φ sayısıyla alakalı bir denklem türetmiştik:
Φ2 - Φ - 1 = 0
Bu denklemin köklerini bulmuştuk sonra:
x1 = ((1 + √5) / 2)
x2 = ((1 - √5) / 2)
Şimdi genel bir f fonksiyonu nasıl tanımlarız buna bakalım.
Böyle durumlarda, eldeki bilgileri tekrar gözden geçirmekte yarar var. Bu mevcut bilgileri kullanıp, bazı yer değiştirme esasları uygulayarak genel geçer bir formül elde edebiliyor muyuz araştırmak lazım.
Örneğin, Φ2 - Φ - 1 = 0 denkleminden başlayalım.
Burada, Φ gördüğümüz yere x yazarsak herhangi bir değişiklik yapmamış oluruz.
O halde x2 - x - 1 = 0 ise
x1 = x
x2 = x + 1 olmaz mı?
x3'ü de şu şekilde yazabiliriz değil mi?
x3 = x * x2
Şimdi buradaki x2 ifadesini ortadan kaldırıp, x’e göre bir yazım yapabiliriz. Çünkü x2'ın ne olduğunu biliyoruz. O halde:
x3 = x * (x + 1) olur. Bu da aşağıdaki ifadeye eşittir.
x3 = x2 + x
x2 yerine x + 1 yazmaya devam ediyorum.
x3 = x + 1 + x = 2 * x + 1
Evet x4'e geçelim.
x4 = x * x3
x3 yerine 2 * x + 1 yazıyorum.
x4 = x * (2 * x + 1)
x4 = 2 * x2 + x
x2 yerine x + 1 yazıyorum.
x4 = 2 * (x + 1) + x
x4 = 3 * x + 2
Bu yaklaşımı devam ettirirsek, x5'in değerinin 5 * x + 3, x6'nın 8 *x + 5, x7'nin 13 * x + 8 olduğunu buluruz.
Sonuçları alt alta bir daha yazalım.
x1 = x
x2 = x + 1
x3 = 2 * x + 1
x4 = 3 * x + 2
x5 = 5 * x + 3
x6 = 8 * x + 5
x7 = 13 * x + 8
Burada sizin de gözünüze bir örüntü çarpmış olmalı. x’in üssü 1, 2, 3, 4, 5 … diye artıkça, x’in katsayıları da fibonacci serisinin 1. 2. 3. 4. … indislerinde yer alan değerleri alıyorlar. Öte yandan denklemdeki sabit ise Fibonacci serisini 1 adım geriden takip ederek değerler alıyor.
Biz fibonacci serisini bulan fonksiyona f ismini vermiştik. Yani:
x7 = 13 * x + 8 ise
f(7)'nin bize 13 değerini, f(6)'nın da 8 değerini vermesi gerekir.
O halde, xn ifadesini yazacak olursak şöyle yazamaz mıyız?
xn = f(n) * x + f(n - 1)
Fibonacci denkleminin köklerini bu denklemlere yazalım.
x1n = f(n) * x1 + f(n - 1)
x2n = f(n) * x2 + f(n - 1)
Şimdi bu iki ifadeyi birbirinden çıkartabiliriz.
x1n - x2n = f(n) * x1 + f(n - 1) - f(n) * x2 - f(n - 1)
f(n - 1)'ler birbirini götürür, elimizde şöyle bir formül kalır:
x1n - x2n = f(n) * x1 - f(n) * x2
Yukardaki ifadeyi f(n) parantezine alabiliriz.
x1n - x2n = f(n) * (x1 - x2)
f(n)'i yalnız bırakalım.
f(n) = (x1n - x2n) / (x1 - x2)
Gördüğünüz gibi son adımda fibonacci dizisinin fonksiyonel formülünü elde ettik. Fibonacci sayısının köklerini de bulmuştuk zaten. Bu kökleri, son elde ettiğimiz formüldeki yerlerine koyarak Fibonacci serisinin n. basamağındaki değeri O(1) hızında bulabiliriz.