Salah satu rekurensi yang paling terkenal muncul dari sebuah kisah sederhana. Misalkan seorang ilmuwan membawa sepasang kelinci yang baru lahir ke sebuah pulau terpencil. Kelinci jenis ini belum dapat berkembang biak sampai bulan ketiga kehidupannya, tetapi setelah itu menghasilkan sepasang kelinci baru setiap bulan. Jadi, pada bulan pertama dan kedua hanya ada sepasang kelinci di pulau itu, tetapi pada bulan ketiga ada dua pasang kelinci karena pasangan pertama menghasilkan sepasang anak kelinci. Pada bulan keempat, pasangan kelinci mula-mula masih ada, demikian pula sepasang anak kelinci pertama mereka, yang belum cukup dewasa untuk berkembang biak. Namun, pasangan mula-mula melahirkan sepasang kelinci lagi sehingga kini ada tiga pasang kelinci di pulau itu. Dengan mengasumsikan bahwa tidak ada predator pemangsa kelinci di pulau tersebut dan kelinci-kelinci itu memiliki rentang hidup tak terbatas, berapa pasang kelinci yang ada di pulau itu pada bulan kesepuluh?
Mari kita lihat cara memperoleh rekurensi dari kisah ini. Misalkan \(f_n\) menyatakan banyaknya pasangan kelinci di pulau itu pada bulan \(n\text{.}\) Jadi, berdasarkan uraian di atas, \(f_1 = 1\text{,}\) \(f_2 = 1\text{,}\) \(f_3=2\text{,}\) dan \(f_4=3\text{.}\) Bagaimana kita menghitung \(f_n\text{?}\) Pada bulan \(n^\text{th}\text{,}\) kita memiliki semua pasangan kelinci yang sudah ada pada bulan sebelumnya, yaitu \(f_{n-1}\text{;}\) namun, sebagian pasangan kelinci itu juga berkembang biak pada bulan ini. Hanya pasangan yang lahir sebelum bulan sebelumnya yang dapat berkembang biak pada bulan \(n\text{,}\) sehingga ada \(f_{n-2}\) pasangan kelinci yang dapat berkembang biak, dan masing-masing menghasilkan sepasang kelinci baru. Dengan demikian, banyaknya pasangan kelinci pada bulan \(n\) adalah \(f_n = f_{n-1} + f_{n-2}\) untuk \(n\geq 3\text{,}\) dengan \(f_1=f_2=1\text{.}\) Barisan bilangan \(\{f_n\colon n\geq 0\}\) (kita menetapkan \(f_0=0\text{,}\) yang memenuhi rekurensi tersebut) dikenal sebagai barisan Fibonacci dan dinamai menurut Leonardo dari Pisa, yang lebih dikenal sebagai Fibonacci, seorang matematikawan Italia yang hidup sekitar tahun 1170 hingga sekitar tahun 1250. Suku-suku \(f_0,f_1,\dots,f_{20}\) dari barisan Fibonacci adalah
\begin{equation*}
0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987, 1597,2584,4181,6765.
\end{equation*}
Jadi, jawaban atas pertanyaan kita tentang banyaknya pasangan kelinci di pulau itu pada bulan kesepuluh adalah \(55\text{.}\) Nilai ini sangat mudah dihitung, tetapi bagaimana jika kita menanyakan nilai \(f_{1000}\) dalam barisan Fibonacci? Dapatkah kita menentukan apakah pertidaksamaan berikut benar atau salah—tanpa benar-benar menghitung \(f_{1000}\text{?}\)
\begin{equation*}
f_{1000} \lt 232748383849990383201823093383773932
\end{equation*}
Rasio-rasio tersebut tampak konvergen ke suatu bilangan. Dapatkah kita menentukan bilangan ini? Apakah bilangan ini berkaitan dengan rumus eksplisit untuk
\(f_n\) (jika rumus seperti itu memang ada)?
Contoh 9.2.
Barisan Fibonacci tidak akan dipelajari sedemikian luas jika kegunaannya hanya untuk menghitung pasangan kelinci di sebuah pulau hipotetis. Berikut contoh lain yang juga menghasilkan barisan Fibonacci. Misalkan
\(c_n\) menyatakan banyaknya cara menutupi papan berpetak berukuran
\(2\times n\) dengan ubin berukuran
\(2\times 1\text{.}\) Maka
\(c_1=1\) dan
\(c_2=2\text{,}\) sedangkan rekurensinya adalah
\(c_{n+2} = c_{n+1}+c_n\text{.}\) Hal ini karena kolom paling kanan papan tersebut diisi oleh sebuah ubin vertikal (sehingga bagian sisanya dapat ditutupi ubin dengan
\(c_{n+1}\) cara), atau dua kolom paling kanannya diisi oleh dua ubin horizontal (sehingga bagian sisanya dapat ditutupi ubin dengan
\(c_n\) cara).
