Fibonacci sayıları ve yinelemeli tanımlı seriler

Fibonacci sayıları bu aralar karşıma pek çok kereler çıkarak gündemime kısa süreli bir giriş yaptı, o sırada da bir arkadaşımla konuşurken yinelemeli seri hesaplamaları için kullanmanın faydalı olabileceğine kanaat getirdim.

Bilen bilir, Fibonacci sayıları dediğimiz seri şu problemi çözmek için çıkmıştır:

Diyelim ki elimizde bir çift tavşanla başlayan bir çiftlik olsun, üreme olgunluğundaki her tavşan çifti ayda bir bir çift tavşan daha üretiyor, ve yeni doğan bir tavşanın üreme olgunluğuna gelmesi bir ay sürüyor. Buna göre n ay sonra elimizde kaç çift tavşan olur?

Mükemmel bir indirgemecilikle tavşanların ölmediğini, sonsuz hızda çiftleşebildiğini, yaş farkını/kan bağını umursamadıklarını düşünürsek yanıt şöyle çıkıyor:

1. ay 1,
2. ay (önceki aydan)1+(onların yavrusu)1=2
3. ay (önceki aydan)2+(ilk çiftin yavrusu)1=3 (ikinci çift yavrulayamıyor çünkü henüz olgun değiller)
4. ay (önceki aydan)3+(iki ay öncekilerin yavruları)2=5

... derken n. aydaki miktara F(n) dersek bunun F(n)=F(n-1)+F(n-2) şeklinde bulunabileceğini görebiliriz. Bu sayılarla harika fraktal spiraller çizilebiliyor. Peki ama bu formül önceki değerlere atıfta bulunarak hesaplanıyor, bunu kendi başına, sadece n cinsinden belirtmenin yolu yok mu? Çeşitli numaralar gösteriyor ki var!

Fikir şu: bu Fn=Fn-1 + Fn-2 formülünü sağlayan bir kuvvet mümkün mü? Yani bir b sayısı var mıdır ki b^n=b^(n-1)+b^(n-2) denkliğini (her n sayısı için) sağlasın? Eh, işin aslı hızlı bir sadeleştirme bize b^2=b+1 denkliğini sağlamasının yeter ve şart olduğunu gösteriyor, bu da enikonu x^2-x-1 polinomunun köklerini bulmakla aynı şey (hızlı hesaplar gösteriyor ki bunun kökleri altın oran φ ve 1-φ çıkıyor, ama kafa karışıklığı olmaması için ben k ve l diyeceğim) (kayıt altına alınsın: k=(1+kök5)/2, l=(1-kök5)/2; k(n)=k^n, l(n)=l^n)

Demek ki k(n) = k(n-1) + k(n-2), l(n) = l(n-1) + l(n-2), dahası eğer bu iki seriyi herhangi bir oranda toplarsak, oluşacak bu yeni seri de aynı kurala (n. elemanın önceki iki elemanın toplamı şeklinde yazılması) uyacaktır. Öyleyse Fibonacci sayılarını bulmak için geriye sadece uygun oranı bulmak kalıyor, o da şunu veriyor: F(n) = (k(n)-l(n))/kök5 (o kadar da ilginç olmayan bir soru: "iyi de Fibonacci sayıları tam sayıların toplamıyla elde ediliyor, nereden çıktı bu kök5 vs?!" Kök5'in nereden çıktığını gördük: polinom kökünden. Peki neden Fibonacci sayılarında hiç görünmüyor? Çeşitli cebirsel numaralarla sadeleşiyor da ondan.) (Cebirin böyle sonuçları var, örneğin çok daha "büyülü" bir sonuç olarak 2 = küpkök(10+kök108) - küpkök(-10+kök108) var, konuya dair şuradaki 1. alıştırmaya bakabilirsiniz.)

Ama bu yazının daha önemli sonucu bunun (bir dereceye kadar) genelleştirilebilir bir yaklaşım olması. Eğer elimizdeki yinelemeli serinin tanımı sadece kendi terimleriyle yapılmışsa bu yöntem büyük ölçüde işe yarayacaktır (üretilen polinomun çoklu kökü olduğu durumlar ufak bir pürüz yaratıyor ama başa çıkmanın yolları var), tanımda fazladan terimler varsa (örneğin F(n) = 2F(n) + 1) bir genel ve bir özel çözüm bulunup bunların birleştirilmesi. Bir de, kendi alanım olduğu için ufak bir notla bunun diferansiyel denklemlerin ayrık(discrete) bir türü gibi ele alınabileceğine dikkat çekerek yazıyı bitireyim.

[2017-02-20:] Ufak bir ekleme yapıldı.