Fibonacci Dizisi icin kapali bir formul

Question

Fibonacci dizisi $f_0 = 0$ ve $f_1 = 1$ olmak uzere $n \geq 2$ icin $$f_{n} = f_{n-1} +f_{n-2}$$ kuraliyla tanimlanir. Yani, dizimiz $0$ ve $1$ ile basliyor ve bundan sonra gelen her terim kendinden once gelen iki terimin toplamina esit. Bu dizi icin kapali bir formul bulabilir misiniz?

(Kapali formulden kastim su: oyle bir formul bulabilir misiniz ki $n$inci terimi bulmak icin kendinden once gelen terimleri hesaplamam gerekmesin?)

Answer 1

Terimleri solda toplayip indeksi 2 kaydirirsak $f_{n+2}-f_{n+1}-f_n=0$ elde ederiz.

Burdan $r^2-r-1=0$ ve kokleri $r_{1,2}=\frac{1}{2}\mp\frac{\sqrt{5}}{2}$ olur.

 Kokler farkli oldugundan $f_n=c_1r_1^n+c_2r_2^n$ olur.

Baslangic kosullarindan $c_1+c_2=0$ ve $c_1r_1+c_2r_2=1$ elde ederiz.

Cozdugumuzde $c_1=\frac{1}{\sqrt{5}}$ ve $c_2=\frac{-1}{\sqrt{5}}$ olarak bulunur.

Bu degerleri yerine koyarsak

 $f_n=\frac{1}{\sqrt{5}}(\frac{1}{2}+\frac{\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1}{2}-\frac{\sqrt{5}}{2})^n$ olur.

Answer 2

Sercan'in guzel cevap(lar)indan sonra ben de bir ksky girisiminde bulunmak istiyorum. En basit yontem degil belki ama tatli bir yontem. Bu yanit neden lineer cebir etiketi kullandigimi da aciklayacak.

Fibonacci dizisi ve matrisler

$$A = \begin{bmatrix} 1 & 1 \\ 1 &0\end{bmatrix} \quad ; \quad x_n = \begin{bmatrix} f_{n+1} \\ f_n \end{bmatrix}$$ olsun. Fibonacci dizisini bu bilgiyle yeniden kodlayalim:

$$x_{n} = \begin{bmatrix}f_{n+1} \\ f_{n} \end{bmatrix} = \begin{bmatrix} f_{n} + f_{n-1} \\ f_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \begin{bmatrix} f_{n} \\ f_{n-1} \end{bmatrix} = Ax_{n-1}$$ ve bu islemi tekrar tekrar yapip  $$x_{n} = A^n x_0$$  oldugunu gozlemleyelim. Soruyu cevapladik. $f_{n}$'i bulmak icin $A^n$'i hesaplayip bu matrisi $x_0$ ile carpmamiz lazim (Aslinda $A^{n-1}$'i hesaplamak yeterli tabii ama maksat indeksler guzel olsun).

Simdi hesaplamalari yapalim.

Bir matrisin kuvvetlerini hesaplamak

Elimizde herhangi bir matris olsun. Bu matrisin herhangi bir kuvvetini nasil hesaplayabiliriz? Matris carpimi halihazirda oldukca zaman alan bir is. Siradan bir $3 \times 3$ matrisin karesini almak bile -bilgisayar degilsek- hic kolay degil. Bazen sansli olabiliyoruz ama. Ornegin, $$A = \begin{bmatrix} a & 0 & 0 \\ 0 & b & 0 \\ 0 &0 & c \end{bmatrix}$$ ise $$A^2 = \begin{bmatrix} a^2 & 0 & 0 \\ 0 & b^2 & 0 \\ 0 &0 & c^2 \end{bmatrix}$$ oluyor. Daha da devam edersek $A^n$ matrisininin kosegeninde $a^n, b^n, c^n$ olan kosegen matris oldugunu gormek zor degil. Ama elimizdeki matris her zaman icin bu kadar guzel calismak zorunda degil. Isteyen   $$\begin{bmatrix} 1 &2 &3 \\ 4 & 5& 6 \\ 7 & 8 & 9 \end{bmatrix}$$  matrisinin kubunu hesaplasin ve gorsun.

Ozdegerler ve Ozvektorler - Kosegenlestirme

$T : \mathbb{C}^n \to \mathbb{C}^n$ (isterseniz $\mathbb{C}$ yerine $\mathbb{R}$ alabilirsiniz) lineer bir fonksiyon olsun. Diyelim ki oldukca sansliyiz ve lineer bagimsiz $n$ tane ozvektorumuz var: $v_1, v_2, \ldots, v_n$. Standart lineer cebir bilgimizle $\{v_ 1, v_2 \ldots, v_n\}$ kumesinin $\mathbb{C}^n$ (isterseniz $\mathbb{R}^n$) icin bir taban oldugunu soyleyebiliriz. Yine standart lineer cebir bilgimizle bu lineer fonksiyonun bu tabana gore matrisini yazarsak bu matrisin bir kosegen matris oldugunu gorebiliriz (isteyen ornek yazip deneyebilir!). Taban degistirme formulunu kullanirsak, $A$ bu lineer fonksiyonun standart tabandaki matrisi, $S$ standart tabandan ozvektorlerden olusan tabana gecme matrisi ve $K$ yukaridaki kosegen matris olmak uzere $$A = S^{-1}KS$$ esitligini gorebiliriz. Yani, once taban degistir, yeni tabanda kosegen matrisle isini yap, sonra tabanini geri degistir.

Dikkat ederseniz $$A ^2 = S^{-1}KSS^{-1}KS = A^2 = S^{-1}K^2 S$$ ve ayni sekilde $$A^m = S^{-1} K^m S$$ demek ki kosegen bir matris olmasak bile, bu durumda kosegen $K$ matrisi ile buyuk kuvvetleri hesaplayip soldan $S^{-1}$ ve sagdan $S$ ile carparak kuvvetleri kolayca hesaplamak kolay. 

Sonuc olarak, eger elimizdeki matrisin ozvektorleri taban olusturuyorsa, o zaman yuksek kuvvetleri almak o kadar da zor degil!

Ya bu kadar sansli degilsek?

Simdi kendimizi $\mathbb{C}^n$ durumuna kisitlayalim ve $n \times n$ bir matris dusunelim. Cebirin temel teoreminden dolayi $n$ adet ozdegerimiz oldugunu biliyoruz cunku karakteristik polinomumuz derecesi $n$ olan bir polinom. Ama bu ozdegerler birbirinden farkli olmak zorunda degiller, ornegin karakteristik polinom icerisinde $(x - 2)^2$ carpani varsa, $2$ ozdegeri birden fazla sayiliyor. Yukaridaki ilk durumda sansliydik ve ozdegerlerimiz kac defa sayiliyorsa, o kadar lineer bagimsiz ozvektor bulabiliyorduk ve ozdegerler bir taban olusturuyordu. Ama $$\begin{bmatrix} 1 & 1 \\ 0 & 1\end{bmatrix}$$ matrisinden de gorebilecegimiz gibi bu her zaman mumkun degil. Ama sorun degil. Yine de bir cozum yolu var: Jordan formu.

Buraya 8000 karakterden uzun yazamayacagim icin buraya hic girmeyecegim.

Soruya geri donelim

$$A = \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}$$ matrisinin ozdegerleri nelerdir? $$\det\begin{bmatrix}1 - x & 1 \\ 1 & -x \end{bmatrix} = (1-x)(-x) - 1 = x^2 - x - 1$$ oldugu icin ozdegerlerimiz Sercan'in cevabindaki $\phi$ ve $\bar{\phi}$. Peki ozdegerler nelerdir? Biraz hesaplama ile $$v_{\phi}=\begin{bmatrix} \phi \\ 1 \end{bmatrix} \quad ; \quad v_{\bar{\phi}}\begin{bmatrix} \bar{\phi} \\ 1 \end{bmatrix}$$ oldugunu bulabiliriz. O halde $$A^n x_0 = \begin{bmatrix} \phi & \bar{\phi} \\ 1 & 1\end{bmatrix}^{-1} \begin{bmatrix} \phi & 0 \\ 0 & \bar{\phi} \end{bmatrix}  \begin{bmatrix} \phi & \bar{\phi} \\ 1 & 1\end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix}$$ Bunu korkmadan akillica hesaplayip ikinci girdisine bakarsak Sercan ve Okkes Dulgerci'nin cavaplarindaki $$f_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}$$ formulune ulasiyoruz.

Comments

Son cumlede korkmadan akillica derken $\phi + \bar{\phi}$ ve $\phi \bar{\phi} sayilarinin guzel sayilar oldugunu soylemek istedim.

Answer 3

Geren fonksiyonunu $(*)$ ( lutfen sondaki aciklamayi okuyunuz)  $$f(z)=\sum\limits_{n\geq0}f_nz^n$$ olarak tanimlayalim. O zaman $$\frac{f(z)-f_0-f_1z}{z^2}=\frac{f(z)-f_0}z+f(z)$$ olur. Burdan $$f(z)=\frac z{1-z-z^2}=\frac{1}{\sqrt5}\bigg( \frac1{1-\phi z}-\frac1{1-\bar\phi z}\bigg)$$ olur. ($\phi=\frac12 (1-\sqrt5)$). Yani  $$f_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}.$$  


Aciklamalar: Geren fonksiyon dedigim su: kat sayilari fibonacci dizisinin degerleri olan sonsuz bir seri. Eger tanimdan sonraki esitligi yazarsaniz. sol tarafin $f_2+f_3z+\cdots$ ve sag tarafin $(f_0+f_1)+(f_1+f_2)z+\cdots$ oldugunu gorursunuz. Bi sonraki adimda sadece $f(z)$'yi cektik. En son adimda da $\frac1{1-x}$'in seri acilimini uyguladik.

Ek aciklama: Kodlama teorisinde "linear recurring sequence" icin bu yontem cok kullanisli.

Comments

Guzelmis. 10 puan.

---

Bir de $r^2-r-1=0$ deyip daha basitten de bulunuyor, fakat bu daha genel ve hosuma giden bir cozum. Eyvallah.

---

Onu da yazsana uzun. Ben de baska bir cevap yaziyorum.

---

Iki tane "En iyi cevap" secebiliyorum sanmistim, secemedim. Senin "En iyi cevap" Okkes Dulgerci'ye gitti.

---

Nasip bu isler :)

---

çok iyi imiş   

---

Üretici (geren) fonksiyon çözümü iyiydi.

Answer 4

Fark formulu denilen bir yontem de vardi: (1. sinif konusu olmasi lazim). Ayni yontem difransiyel denklemlerde de kullaniliyor.

Cozmemiz gereken: $r^2-r-1=0$. Burda kokler $\frac{1\pm\sqrt5}{2}$. Genel cozum de $f_n=c_1(\frac{1+\sqrt5}{2})^n+c_2(\frac{1-\sqrt5}{2})^n$ seklinde olmali. Verilen ilk iki terimden $c_1$ ve $c_2$ artik kolaycana bulunabilir. $c_1=-c_2=\frac1{\sqrt5}$.