Fibonacci, juga dikenal sebagai Leonardo Bonacci, Leonardo dari Pisa, atau Leonardo Bigollo Pisano, adalah matematikawan berkebangsaan Italia yang dijuluki sebagai “matematikawan paling berbakat sepanjang Zaman Pertengahan”. Ia lahir pada tahun 1170 dan wafat sekitar tahun 1250. Fibonacci terkenal karena karyanya dalam mengenalkan serangkaian bilangan yang saat ini dikenal sebagai bilangan Fibonacci. Di luar sana, sejumlah pihak bahkan mengklaim ini sebagai sidik jari Tuhan (fingerprint of God).
Dalam bukunya yang berjudul Liber Abaci, ditulis pada tahun 1202, Fibonacci mengajukan masalah yang berkaitan dengan perkembangbiakan kelinci di kawasan tertentu. Masalah tersebut dapat dinarasikan sebagai berikut: Sepasang kelinci muda (jantan dan betina) ditempatkan di suatu pulau terpencil. Asumsikan kelinci tersebut tidak bereproduksi sampai usianya 2 bulan, dan saat sudah mencapai usia 2 bulan, sepasang kelinci tersebut akan bereproduksi sehingga menghasilkan satu pasangan kelinci kecil setiap bulannya. Asumsikan juga bahwa kelinci-kelinci di pulau itu tidak bisa mati. Berapa banyak pasangan kelinci yang ada di sana saat $n$ bulan?
Baca: Materi, Soal, dan Pembahasan – Algoritma Euclid
Misalkan $f_n$ menyatakan banyaknya pasangan kelinci setelah $n$ bulan. Dalam kasus ini, $f_1 = 1$ karena hanya ada $1$ pasang kelinci di pulau itu setelah bulan pertama. Karena pasangan kelinci ini tidak bereproduksi pada bulan kedua, diperoleh $f_2 = 1.$ Berikutnya, sepasang kelinci tersebut bereproduksi dan menghasilkan sepasang kelinci kecil sehingga pada akhir bulan ketiga, sudah ada $2$ pasang kelinci. Jadi, $f(3) = 2.$
Untuk menentukan banyaknya pasangan kelinci setelah $n$ bulan, tambahkan banyaknya pasangan kelinci pada bulan sebelumnya, yaitu $f_{n-1},$ dengan banyaknya pasangan kelinci yang baru lahir, yaitu $f_{n-2},$ karena mereka dilahirkan dari pasangan kelinci yang usianya menginjak dua bulan. Ide ini kemudian membuat kita mendefinisikan secara formal “barisan dan bilangan Fibonacci” sebagai berikut.
Definisi: Barisan dan Bilangan Fibonacci
Menurut catatan sejarah, Édouard Lucas (1842–1891), matematikawan Prancis, merupakan orang pertama yang memberi nama barisan bilangan ini dengan menggunakan nama “Fibonacci”. Lucas merupakan matematikawan yang mempelajari secara detail terkait barisan Fibonacci hingga menemukan banyak sifat terkait dengannya. Lebih lanjut, definisi di atas menunjukkan bahwa mulai dari suku ketiga, nilai setiap suku ditentukan dengan cara menjumlahkan satu dan dua suku sebelumnya.
Kita akan menghitung $10$ bilangan Fibonacci pertama secara manual sebagai berikut.
$$\begin{aligned} f_1 & = 1 \\ f_2 & = 1 \\ f_3 & = f_2 + f_1 = 1 + 1 = 2 \\ f_4 & = f_3 + f_2 = 1 + 2 = 3 \\ f_5 & = f_4 + f_3 = 3 + 2 = 5 \\ f_6 & = f_5 + f_4 = 5 + 3 = 8 \\ f_7 & = f_6 + f_5 = 8 + 5 = 13 \\ f_8 & = f_7 + f_6 = 13 + 8 = 21 \\ f_9 & = f_8 + f_7 = 21 + 13 = 34 \\ f_{10} & = f_9 + f_8 = 34 + 21 = 55. \end{aligned}$$Barisan Fibonacci didefinisikan secara rekursif sehingga nilai suku-sukunya tergantung dari suku sebelumnya. Meskipun demikian, suku ke-$n$ barisan Fibonacci dapat ditentukan dengan menggunakan rumus eksplisit yang telah ditemukan. yaitu
$$f(n) = \dfrac{1}{\sqrt5}\left(\left(\dfrac{1+\sqrt5}{2}\right)^n-\left(\dfrac{1-\sqrt5}{2}\right)^n\right).$$Rumus ini dapat dibuktikan kebenarannya dengan menggunakan induksi kuat (lihat pembahasan pada bagian soal di bawah).
Barisan Fibonacci memiliki beberapa sifat menarik. Salah satunya adalah rasio antara dua bilangan Fibonacci yang berurutan mendekati rasio emas (golden ratio), yang disimbolkan dengan $\phi$ (baca: phi) dengan nilai sekitar $1,\!61803.$ Rasio emas ini sering ditemukan dalam alam dan dunia seni sehingga membuat barisan Fibonacci menjadi struktur yang menarik dalam matematika.
Selain itu, barisan Fibonacci juga memiliki aplikasi praktis dalam berbagai bidang. Misalnya, dalam matematika keuangan, barisan Fibonacci digunakan dalam perhitungan terkait bunga dan investasi. Dalam ilmu komputer, barisan Fibonacci digunakan dalam algoritma dan struktur data, seperti algoritma pencarian biner (binary search) dan pembagian konstanta waktu. Bahkan dalam biologi, pola barisan Fibonacci sering muncul dalam distribusi daun di pohon atau kelopak bunga di tumbuhan. Sebagai contoh, banyaknya spiral pada tanaman dengan susunan daunnya membentuk pola yang disebut sebagai filotaksis (phyllotaxis) selalu berupa bilangan Fibonacci.
Baca: Materi, Soal, dan Pembahasan – Kongruensi Modulo
Karya Leonardo Fibonacci membantu memperkaya dunia matematika dan ilmu pengetahuan secara umum, serta memberikan wawasan tentang bagaimana pola dan struktur matematika muncul dalam alam dan kehidupan sehari-hari kita.
Jika Anda ingin mencari soal latihan yang lebih banyak, Anda dapat mengakses ke folder soal mathcyber1997.com dengan mendaftar di . Folder soal tersebut tidak hanya berisi soal UTBK-SNBT, melainkan juga soal persiapan CPNS-PPPK, soal psikotes, soal TPA, soal ujian masuk perguruan tinggi, soal kompetensi matematika, dan masih banyak lagi.
Quote by Linda Hogan
Bagian Uraian
Soal Nomor 1
Misalkan $n$ merupakan bilangan bulat positif. Buktikan bahwa $\displaystyle \sum_{k=1}^n f_k = f_{n+2}-1.$
Berdasarkan definisi, $f_n = f_{n-1} + f_{n-2}$ untuk setiap bilangan bulat positif $n.$ Artinya, $f_k = f_{k+2}-f_{k+1}$ untuk setiap bilangan bulat positif $k.$ Dengan demikian, dapat ditulis
$$\displaystyle \sum_{k=1}^n f_k = \sum_{k=1}^n (f_{k+2}-f_{k+1}).$$Jumlahan di atas dapat dengan mudah dihitung karena bersifat teleskopis (suku-sukunya saling menghilangkan). Dari sini, didapat
$$\displaystyle \sum_{k=1}^n f_k = f_{n+2}-f_2 = f_{n+2}-1.$$Jadi, terbukti bahwa $\displaystyle \sum_{k=1}^n f_k = f_{n+2}-1.$
Baca: Materi, Soal, dan Pembahasan – Deret Teleskopik
Soal Nomor 2
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan bilangan Fibonacci. Buktikan bahwa $f_{n+3} + f_n = 2f_{n+2}$ untuk setiap bilangan bulat positif $n.$
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan bilangan Fibonacci. Berdasarkan definisi, $f_{n+2} = f_{n} + f_{n+1}$ untuk setiap $n \ge 0.$ Dengan demikian,
$$\begin{aligned} f_{n+3} + f_n & = (f_{n+2} + f_{n+1}) + f_n \\ & = f_{n+2} + (f_{n+1} + f_n) \\ & = f_{n+2} + f_{n+2} \\ & = 2f_{n+2}. \end{aligned}$$Jadi, terbukti bahwa $f_{n+3} + f_n = 2f_{n+2}.$
Soal Nomor 3
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan bilangan Fibonacci. Buktikan bahwa $f_{n+3}- f_n = 2f_{n+1}$ untuk setiap bilangan bulat positif $n.$
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan bilangan Fibonacci. Berdasarkan definisi, $f_{n+2} = f_{n} + f_{n+1}$ untuk setiap $n \ge 0.$ Dengan demikian,
$$\begin{aligned} f_{n+3}-f_n & = (f_{n+2} + f_{n+1})- f_n \\ & = ((f_{n+1} + \cancel{f_n}) + f_{n+1})-\cancel{f_n} \\ & = 2f_{n+1}. \end{aligned}$$Jadi, terbukti bahwa $f_{n+3}- f_n = 2f_{n+1}.$
Baca Juga: Soal dan Pembahasan – Barisan dan Deret Geometri
Soal Nomor 4
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan bilangan Fibonacci. Buktikan bahwa $f_{n-2}+f_{n+2} = 3f_{n}$ untuk setiap bilangan bulat positif $n.$
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan bilangan Fibonacci. Berdasarkan definisi, $f_{n+2} = f_{n} + f_{n+1}$ untuk setiap $n \ge 0.$ Dengan demikian,
$$\begin{aligned} f_{n-2}+f_{n+2} & = (f_n-f_{n-1}) + (f_n + f_{n+1}) \\ & = (f_n-(f_{n+1}-f_n)) + (f_n + f_{n+1}) \\ & = 3f_n. \end{aligned}$$Jadi, terbukti bahwa $f_{n-2}+f_{n+2} = 3f_{n}.$
Soal Nomor 5
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan bilangan Fibonacci. Buktikan bahwa $f_{2n} = f_n^2 + 2f_{n-1}f_n$ untuk setiap bilangan bulat positif $n.$
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan bilangan Fibonacci. Misalkan juga $P(n)$ menyatakan $f_{2n} = f_n^2 + 2f_{n-1}f_n$ untuk suatu bilangan bulat positif $n.$
Langkah Basis:
$P(1)$ benar karena
$$\begin{aligned} f_{2(1)} & = f(2) \\ & = 1 \\ & = 1^2 + 2 \cdot 0 \cdot 1 \\ & = f_1^2 + 2f_0f_1. \end{aligned}$$ $P(2)$ juga benar karena
$$\begin{aligned} f_{2(2)} & = f(4) \\ & = 3 \\ & = 1^2 + 2 \cdot 1 \cdot 1 \\ & = f_2^2 + 2f_1f_2. \end{aligned}$$Langkah Induktif:
Misalkan untuk sembarang bilangan bulat positif $k-1,$ $P(1), P(2),$ hingga $P(k-1)$ benar. Akan dibuktikan bahwa $P(k)$ juga benar.
Pandang $P(k-2)$ dan $P(k-1)$ yang berturut-turut menyatakan $f_{2k-4} = f_{k-2}^2 + 2f_{k-3}f_{k-2}$ dan $f_{2k-2} = f_{k-1}^2 + 2f_{k-2}f_{k-1}.$ Perhatikan bahwa
$$\begin{aligned} f_{2k} & = f_{2k-1} + f_{2k-2} \\ & = (f_{2k-2} + f_{2k-3}) + f_{2k-2} \\ & = (f_{2k-2} + (f_{2k-2}-f_{2k-4})) + f_{2k-2} \\ & = 3f_{2k-2}-f_{2k-4}. \end{aligned}$$Berdasarkan hipotesis induksi, didapat
$$\begin{aligned} 3f_{2k-2}-f_{2k-4} & = 3(f_{k-1}^2 + 2f_{k-2}f_{k-1})-(f_{k-2}^2 + 2f_{k-3}f_{k-2}) \\ & = 3f_{k-1}^2+6(f_k-f_{k-1})f_{k-1}-(f_k-f_{k-1})^2-2(f_{k-1}-f_{k-2})(f_{k}-f_{k-1}) \\ & = 3f_{k-1}^2+6(f_k-f_{k-1})f_{k-1}-(f_k-f_{k-1})^2-2(2f_{k-1}-f_{k})(f_{k}-f_{k-1}) \\ & = f_k^2 + 2f_kf_{k-1}. \end{aligned}$$ Jadi, $P(k)$ terbukti benar.
Karena $P(1)$ benar dan untuk sembarang bilangan bulat positif $k-1,$ kebenaran $P(k-1)$ mengimplikasikan kebenaran $P(k),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat positif $n.$ Artinya, $f_{2n} = f_n^2 + 2f_{n-1}f_n$ untuk setiap bilangan bulat positif $n.$ $\blacksquare$
Baca Juga: Soal dan Pembahasan – Barisan dan Deret Aritmetika
Soal Nomor 6
Misalkan $n$ merupakan bilangan bulat positif. Tentukan dan buktikan rumus sederhana yang menyatakan jumlah dari $n$ bilangan Fibonacci pertama dengan indeks ganjil, yaitu $f_1 + f_3 + \cdots + f_{2n-1}.$
Amati bahwa
$$\begin{aligned} f_1 & = 1 = f_2 \\ f_1 + f_3 & = 1 + 2 = 3 = f_4 \\ f_1 + f_3 + f_5 & = 1 + 2 + 5 = 8 = f_6. \end{aligned}$$Observasi di atas membuat kita mengajukan konjektur (dugaan) bahwa
$$f_1 + f_3 + \cdots + f_{2n-1} = f_{2n}$$untuk setiap bilangan bulat positif $n.$ Konjektur tersebut akan dibuktikan kebenarannya dengan menggunakan induksi matematika.
Misalkan $n$ merupakan bilangan bulat positif. Definisikan $P(n) : f_1 + f_3 + \cdots + f_{2n-1} = f_{2n}.$
Langkah Basis:
Untuk $n = 1$, diperoleh $P(1) : f_1 = 1 = f_2.$ Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan bulat positif $k,$ berlaku $$P(k) : f_1 + f_3 + \cdots + f_{2k-1} = f_{2k}.$$Asumsikan pernyataan di atas bernilai benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar, yaitu
$$f_1 + f_3 + \cdots + f_{2k-1} + f_{2k+1} = f_{2k+2}.$$Perhatikan bahwa
$$\begin{aligned} \underbrace{f_1 + f_3 + \cdots + f_{2k-1}}_{f_{2k}} + f_{2k+1} & = f_{2k} + f_{2k+1} && (\text{Hipotesis induksi}) \\ & = f_{2k+2}. && (\text{Definisi bilangan Fibonacci}) \end{aligned}$$Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n.$
Dengan demikian, rumus sederhana yang menyatakan jumlah dari $n$ bilangan Fibonacci pertama dengan indeks ganjil, yaitu $f_1 + f_3 + \cdots + f_{2n-1},$ adalah $f_{2n}.$
Baca Juga: Soal dan Pembahasan – Induksi Matematika pada Deret dan Ketaksamaan
Soal Nomor 7
Misalkan $n$ merupakan bilangan bulat positif. Tentukan dan buktikan rumus sederhana yang menyatakan jumlah dari $n$ bilangan Fibonacci pertama dengan indeks genap, yaitu $f_2 + f_4 + \cdots + f_{2n}.$
Amati bahwa
$$\begin{aligned} f_2 & = 1 = 2-1 = f_3-1 \\ f_2 + f_4 & = 1 + 3 = 5-1 = f_5-1 \\ f_2 + f_4 + f_6 & = 1 + 3 + 8 = 13-1 = f_7-1. \end{aligned}$$Observasi di atas membuat kita mengajukan konjektur (dugaan) bahwa
$$f_2 + f_4 + \cdots + f_{2n} = f_{2n+1}-1$$untuk setiap bilangan bulat positif $n.$ Konjektur tersebut akan dibuktikan kebenarannya dengan menggunakan induksi matematika.
Misalkan $n$ merupakan bilangan bulat positif. Definisikan $P(n) : f_2 + f_4 + \cdots + f_{2n} = f_{2n+1}-1.$
Langkah Basis:
Untuk $n = 1$, diperoleh $P(1) : f_2 = 1 = 2-1= f_3-1.$ Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan bulat positif $k,$ berlaku $$P(k) : f_2 + f_4 + \cdots + f_{2k} = f_{2k+1}-1.$$Asumsikan pernyataan di atas bernilai benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar, yaitu
$$f_2 + f_4 + \cdots + f_{2k} + f_{2k+2} = f_{2k+3}-1.$$Perhatikan bahwa
$$\begin{aligned} \underbrace{f_2+ f_4 + \cdots + f_{2k}}_{f_{2k+1}-1} + f_{2k+2} & = (f_{2k+1}-1) + f_{2k+2} && (\text{Hipotesis induksi}) \\ & = (f_{2k+1} + f_{2k+2})-1 \\ & = f_{2k+3}-1. && (\text{Definisi bilangan Fibonacci}) \end{aligned}$$Jadi, $P(k+1)$ benar.
Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n.$ Artinya, $$f_2 + f_4 + \cdots + f_{2n} = f_{2n+1}-1$$untuk setiap bilangan bulat positif $n.$
Soal Nomor 8
Misalkan $n$ merupakan bilangan bulat positif. Tentukan dan buktikan rumus sederhana untuk ekspresi $$f_n-f_{n-1} +f_{n-2}-\cdots+(-1)^{n+1}f_1.$$
Misalkan $n$ merupakan bilangan bulat positif.
Kasus 1:
Misalkan $n = 2k$ merupakan bilangan genap positif. Dengan demikian,
$$\begin{aligned} f_n-f_{n-1} +f_{n-2}-\cdots+(-1)^{n+1}f_1 & = (f_{2k} + f_{2k-1} + \cdots + f_1)-2(f_{2k-1} + f_{2k-3} + \cdots + f_1) \\ & = (f_{2k+2}-1)-2(f_{2k}) \\ & = (f_{2k+2}-f_{2k})-f_{2k}-1 \\ & = f_{2k+1}-f_{2k}-1 \\ & = f_{2k-1}-1 \\ & = f_{n-1}-1 \end{aligned}$$dengan menggunakan fakta bahwa $\displaystyle \sum_{m=1}^{2k} f_{m} = f_{2k+2}-1$ dan $\displaystyle \sum_{m=1}^{k} f_{2m-1} = f_{2k}.$
Kasus 2:
Misalkan $n = 2k+1$ merupakan bilangan ganjil positif. Dengan demikian,
$$\begin{aligned} f_n-f_{n-1} +f_{n-2}-\cdots+(-1)^{n+1}f_1 & = f_{2k+1}-(f_{2k}-f_{2k-1}+\cdots-(-1)^{n+1}f_1) \\ & = f_{2k+1}-(f_{2k-1}-1) \end{aligned}$$dengan menggunakan rumus yang telah dibuktikan dari Kasus 1 di atas. Kemudian,
$$\begin{aligned} f_{2k+1}-(f_{2k-1}-1) & = f_{2k}+1 \\ & = f_{n-1}+1. \end{aligned}$$Dengan menggabungkan rumus untuk Kasus 1 dan 2, dapat ditulis $$f_n-f_{n-1} +f_{n-2}-\cdots+(-1)^{n+1}f_1 = f_{n-1}-(-1)^n.$$
Soal Nomor 9
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan Fibonacci. Buktikan bahwa
$$\displaystyle \sum_{j=1}^n f_j^2 = f_1^2 + f_2^2 + \cdots + f_n^2 = f_nf_{n+1}$$untuk setiap bilangan bulat positif $n.$
Pernyataan tersebut akan dibuktikan dengan menggunakan induksi matematika.
Misalkan $n$ merupakan bilangan bulat positif. Definisikan $$P(n) : \displaystyle \sum_{j=1}^n f_j^2 = f_1^2 + f_2^2 + \cdots + f_n^2 = f_nf_{n+1}.$$Langkah Basis:
Untuk $n = 1$, diperoleh $$f_1^2 = 1^2 = 1 = 1 \cdot 1 = f_1 \cdot f_2.$$Jadi, $P(1)$ benar.
Langkah Induktif:
Misalkan untuk sembarang bilangan bulat positif $k,$ berlaku $$P(k) : \displaystyle \sum_{j=1}^k f_j^2 = f_1^2 + f_2^2 + \cdots + f_k^2 = f_kf_{k+1}.$$Asumsikan pernyataan di atas bernilai benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar, yaitu
$$\displaystyle \sum_{j=1}^{k+1} f_j^2 = f_1^2 + f_2^2 + \cdots + f_k^2 + f_{k+1}^2 = f_{k+1}f_{k+2}.$$
Perhatikan bahwa
$$\begin{aligned} \underbrace{f_1^2 + f_2^2 + \cdots + f_k^2}_{f_{k}f_{k+1}} + f_{k+1}^2 & = f_kf_{k+1} + f_{k+1}^2 && (\text{Hipotesis induksi}) \\ & = f_{k+1}(f_k + f_{k+1}) \\ & = f_{k+1}f_{k+2}. && (\text{Definisi barisan Fibonacci}) \end{aligned}$$Jadi, $P(k+1)$ benar.
Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n.$ Artinya, $$\displaystyle \sum_{j=1}^n f_j^2 = f_1^2 + f_2^2 + \cdots + f_n^2 = f_nf_{n+1}$$untuk setiap bilangan bulat positif $n.$ $\blacksquare$
Soal Nomor 10
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan Fibonacci. Buktikan bahwa
$$f_{n+1}f_{n-1}-f_n^2 = (-1)^n$$untuk setiap bilangan bulat positif $n.$
Pernyataan tersebut akan dibuktikan dengan menggunakan induksi matematika.
Misalkan $n$ merupakan bilangan bulat positif. Definisikan $$P(n) : f_{n+1}f_{n-1}-f_n^2 = (-1)^n.$$Langkah Basis:
Untuk $n = 1$, diperoleh $$f_2f_0-f_1^2 = 1 \cdot 0-1^2 = -1 = (-1)^1.$$Jadi, $P(1)$ benar.
Langkah Induktif:
Misalkan untuk sembarang bilangan bulat positif $k,$ berlaku $$P(k) : f_{k+1}f_{k-1}-f_k^2 = (-1)^k.$$Asumsikan pernyataan di atas bernilai benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar, yaitu
$$f_{k+2}f_{k}-f_{k+1}^2 = (-1)^{k+1}.$$Perhatikan bahwa
$$\begin{aligned} f_{k+2}f_{k}-f_{k+1}^2 & = (f_k + f_{k+1})f_k-f_{k+1}(f_{k-1} + f_k) \\ & = f_k^2 + \cancel{f_{k+1}f_k}-f_{k+1}f_{k-1}-\cancel{f_{k+1}f_k} \\ & = f_k^2-f_{k+1}f_{k-1} \\ & = -(-1)^k \\ & = (-1)^{k+1}. \end{aligned}$$Jadi, $P(k+1)$ benar.
Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n.$ Artinya, $$f_{n+1}f_{n-1}-f_n^2 = (-1)^n$$untuk setiap bilangan bulat positif $n.$ $\blacksquare$
Baca Juga: Soal dan Pembahasan – Induksi Matematika pada Keterbagian Bilangan
Soal Nomor 11
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan Fibonacci. Buktikan bahwa
$$f_1f_2 + f_2f_3 + \cdots + f_{2n-2}f_{2n-1} + f_{2n-1}f_{2n} = f_{2n}^2$$untuk setiap bilangan bulat positif $n.$
Pernyataan tersebut akan dibuktikan dengan menggunakan induksi matematika.
Misalkan $n$ merupakan bilangan bulat positif. Definisikan $$P(n) : f_1f_2 + f_2f_3 + \cdots + f_{2n-2}f_{2n-1} + f_{2n-1}f_{2n} = f_{2n}^2.$$Langkah Basis:
Untuk $n = 1$, diperoleh
$$f_1f_2 = (1)(1) = 1 = 1^2 = f_2^2.$$Jadi, $P(1)$ benar.
Langkah Induktif:
Misalkan untuk sembarang bilangan bulat positif $k,$ berlaku $$P(k) : f_1f_2 + f_2f_3 + \cdots + f_{2k-2}f_{2k-1} + f_{2k-1}f_{2k} = f_{2k}^2.$$Asumsikan pernyataan di atas bernilai benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar, yaitu
$$f_1f_2 + f_2f_3 + \cdots + f_{2k-2}f_{2k-1} + f_{2k-1}f_{2k} + f_{2k}f_{2k+1} + f_{2k+1}f_{2k+2} = f_{2k+2}^2.$$Perhatikan bahwa
$$\begin{aligned} \underbrace{f_1f_2 + f_2f_3 + \cdots + f_{2k-2}f_{2k-1} + f_{2k-1}f_{2k}}_{f_{2k}^2} + f_{2k}f_{2k+1} + f_{2k+1}f_{2k+2} & = f_{2k}^2 + f_{2k}f_{2k+1} + f_{2k+1}f_{2k+2} \\ & = f_{2k}(f_{2k} + f_{2k+1}) + f_{2k+1}f_{2k+2} \\ & = f_{2k}f_{2k+2} + f_{2k+1}f_{2k+2} \\ & = f_{2k+2}(f_{2k} + f_{2k+1}) \\ & = f_{2k+2}f_{2k+2} \\ & = f_{2k+2}^2. \end{aligned}$$Jadi, $P(k+1)$ benar.
Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n.$ Artinya, $$f_1f_2 + f_2f_3 + \cdots + f_{2n-2}f_{2n-1} + f_{2n-1}f_{2n} = f_{2n}^2$$untuk setiap bilangan bulat positif $n.$ $\blacksquare$
Soal Nomor 12
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan Fibonacci. Buktikan bahwa $$f_{m+n} = f_mf_{n+1} + f_nf_{m-1}$$untuk setiap bilangan bulat positif $m$ dan $n.$
Pernyataan tersebut akan dibuktikan dengan menggunakan induksi kuat.
Misalkan $n$ merupakan bilangan bulat positif. Ambil sembarang bilangan bulat positif $m.$ Selanjutnya, definisikan
$$P(n) : f_{m+n} = f_mf_{n+1} + f_nf_{m-1}.$$Langkah Basis:
Untuk $n = 1,$ diperoleh
$$\begin{aligned} f_{m+1} & = f_mf_2 + f_1f_{m-1} \\ & = f_m(1) + 1f_{m-1} \\ & = f_m + f_{m-1}. \end{aligned}$$Jadi, $P(1)$ benar definisi bilangan Fibonacci.
Untuk $n = 2,$ diperoleh
$$\begin{aligned} f_mf_3 + f_2f_{m-1} & = f_m(2) + 1f_{m-1} \\ & = 2f_m + f_{m-1} \\ & = f_m + (f_m + f_{m-1}) \\ & = f_m + f_{m+1} \\ & = f_{m+2}. \end{aligned}$$Jadi, $P(2)$ benar.
Langkah Induktif:
Misalkan untuk sembarang bilangan bulat positif $k,$ berlaku
$$P(k) : f_{m+k} = f_mf_{k+1} + f_kf_{m-1}.$$Asumsikan pernyataan di atas bernilai benar. Akan dibuktikan bahwa $P(k+1)$ juga benar, yaitu
$$f_{m+k+1} = f_{m}f_{k+2} + f_{k+1}f_{m-1}.$$Pandang $P(k-1)$ dan $P(k)$ yang berturut-turut menyatakan
$$f_{m+k-1} = f_{m}f_k + f_{k-1}f_{m-1}$$dan $$f_{m+k} = f_{m}f_{k+1} + f_{k}f_{m-1}.$$Perhatikan bahwa
$$\begin{aligned} f_{m}f_{k+2} + f_{k+1}f_{m-1} & = f_m(f_{k+1} + f_k) +(f_k + f_{k-1})f_{m-1} \\ & = f_mf_{k+1} + f_mf_k + f_kf_{m-1} + f_{k-1}f_{m-1} \\ & = (f_mf_k + f_{k-1}f_{m-1}) + (f_mf_{k+1} + f_kf_{m-1}) \\ & = f_{m+k-1} + f_{m+k} \\ & = f_{m+k+1}. \end{aligned}$$Jadi, $P(k+1)$ benar.
Berdasarkan prinsip induksi matematika, disimpulkan bahwa $P(n)$ benar untuk setiap bilangan bulat positif $n.$ Artinya, terbukti bahwa $$f_{m+n} = f_mf_{n+1} + f_nf_{m-1}$$untuk setiap bilangan bulat positif $m$ dan $n.$ $\blacksquare$
Soal Nomor 13
Misalkan $f_n$ menyatakan suku ke-$n$ dari barisan Fibonacci. Buktikan bahwa $f_n > \alpha^{n-2}$ untuk setiap bilangan bulat positif $n \ge 3$ dengan $\alpha = \dfrac{1+\sqrt5}{2}.$
Pernyataan tersebut akan dibuktikan dengan menggunakan induksi kuat.
Misalkan $n$ merupakan bilangan bulat positif. Selanjutnya, definisikan
$$P(n) : f_n > \alpha^{n-2}.$$Langkah Basis:
Untuk $n = 3,$ diperoleh $$f_3 = 2 > \dfrac{1+\sqrt5}{2} = \alpha.$$Sementara itu, untuk $n = 4,$ diperoleh $$f_4 = 3 > \dfrac{3+\sqrt5}{2} = \left(\dfrac{1+\sqrt5}{2}\right)^2 = \alpha^2.$$ Jadi, $P(3)$ dan $P(4)$ keduanya benar.
Langkah Induktif:
Misalkan untuk sembarang bilangan bulat positif $k \ge 3,$ berlaku
$$P(k) : f_k > \alpha^{k-2}.$$Asumsikan pernyataan di atas bernilai benar. Akan dibuktikan bahwa $P(k+1)$ juga benar, yaitu
$$f_{k+1} > \alpha^{k-1}.$$Karena $\alpha = \dfrac{1+\sqrt5}{2}$ merupakan akar dari persamaan $x^2-x-1=0,$ diperoleh $\alpha^2 = \alpha + 1.$ Dengan demikian,
$$\begin{aligned} \alpha^{k-1} & = \alpha^2 \cdot \alpha^{k-3} \\ & = (\alpha + 1) \cdot \alpha^{k-3} \\ & = \alpha^{k-2} + \alpha^{k-3}. \end{aligned}$$Dengan menggunakan hipotesis induksi, berlaku pertidaksamaan berikut.
$$\alpha^{n-2} < f_n~\text{dan}~\alpha^{n-3} < f_{n-1}.$$Dengan menjumlahkan pertidaksamaan tersebut sesuai ruasnya, didapat
$$\alpha^{n-1} = \alpha^{n-2} + \alpha^{n-3} < f_{n} + f_{n-1} = f_{n+1}.$$Jadi, $P(k+1)$ benar.
Berdasarkan prinsip induksi matematika, disimpulkan bahwa $P(n)$ benar untuk setiap bilangan bulat positif $n \ge 3.$ Artinya, terbukti bahwa $f_{n} > \alpha^{n-2}$ untuk setiap bilangan bulat positif $n \ge 3$ dengan $\alpha = \dfrac{1+\sqrt5}{2}.$ $\blacksquare$
Soal Nomor 14
Misalkan $n$ merupakan bilangan bulat positif, $\alpha = \dfrac{1 + \sqrt5}{2},$ dan $\beta = \dfrac{1-\sqrt5}{2}.$ Tunjukkan bahwa $f_n = \dfrac{1}{\sqrt5}(\alpha^n-\beta^n)$ dengan $f_n$ menyatakan suku ke-$n$ pada barisan Fibonacci.
Misalkan $f_n$ menyatakan suku ke-$n$ pada barisan bilangan Fibonacci. Misalkan juga $P(n)$ menyatakan $f_n = \dfrac{1}{\sqrt5}(\alpha^n-\beta^n)$ untuk suatu bilangan bulat positif $n.$ Catat bahwa $\alpha = \dfrac{1 + \sqrt5}{2},$ dan $\beta = \dfrac{1-\sqrt5}{2}$ adalah akar dari persamaan kuadrat $x^2-x-1 = 0$ sehingga berlaku $\alpha^2 = \alpha + 1$ dan $\beta^2 = \beta + 1.$
Langkah Basis:
$P(1)$ benar karena
$$\begin{aligned} f_{1} & = 1 \\ & = \dfrac{1}{\sqrt5}\left(\dfrac{2\sqrt5}{2}\right) \\ & = \dfrac{1}{\sqrt5}\left(\dfrac{1 + \sqrt5}{2}-\dfrac{1-\sqrt5}{2}\right) \\ & = \dfrac{1}{\sqrt5}(\alpha-\beta). \end{aligned}$$ $P(2)$ juga benar karena
$$\begin{aligned} f_{2} & = 1 \\ & = \dfrac{1}{\sqrt5}\left(\dfrac{4\sqrt5}{4}\right) \\ & = \dfrac{1}{\sqrt5}\left(\dfrac{6 + 2\sqrt5}{4}-\dfrac{6-2\sqrt5}{4}\right) \\ & = \dfrac{1}{\sqrt5}(\alpha^2-\beta^2). \end{aligned}$$Langkah Induktif:
Misalkan untuk sembarang bilangan bulat positif $k,$ $P(1), P(2),$ hingga $P(k)$ benar. Akan dibuktikan bahwa $P(k+1)$ juga benar.
Pandang $P(k-1)$ dan $P(k)$ yang berturut-turut menyatakan $f_{k-1} = \dfrac{1}{\sqrt5}(\alpha^{k-1}-\beta^{k-1})$ dan $f_{k} = \dfrac{1}{\sqrt5}(\alpha^{k}-\beta^{k}).$ Perhatikan bahwa
$$\begin{aligned} f_{k+1} & = f_{k-1} + f_k \\ & = \dfrac{1}{\sqrt5}(\alpha^{k-1}-\beta^{k-1}) + \dfrac{1}{\sqrt5}(\alpha^{k}-\beta^{k}) \\ & = \dfrac{1}{\sqrt5}\left((\alpha^{k-1}-\beta^{k-1} + (\alpha^{k}-\beta^{k})\right) \\ & = \dfrac{1}{\sqrt5}\left(\alpha^{k-1}(\alpha+1)-\beta^{k-1}(\beta+1)\right) \\ & = \dfrac{1}{\sqrt5}\left(\alpha^{k-1} \cdot \alpha^2-\beta^{k-1} \cdot \beta^2\right) \\ & = \dfrac{1}{\sqrt5}\left(\alpha^{k+1}-\beta^{k+1}\right). \end{aligned}$$Jadi, $P(k+1)$ terbukti benar.
Berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat positif $n.$ Artinya, untuk setiap bilangan bulat positif $n,$ berlaku $f_n = \dfrac{1}{\sqrt5}(\alpha^n-\beta^n)$ dengan $\alpha = \dfrac{1 + \sqrt5}{2}$ dan $\beta = \dfrac{1-\sqrt5}{2}.$ $\blacksquare$
Soal Nomor 15
Misalkan $F = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.$ Buktikan bahwa $F^n = \begin{pmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{pmatrix}$ untuk setiap bilangan bulat positif $n$ dengan $f_n$ menyatakan suku ke-$n$ dari barisan Fibonacci.
Pernyataan tersebut akan dibuktikan dengan menggunakan induksi matematika.
Misalkan $n$ merupakan bilangan bulat positif. Definisikan $$P(n) : F^n = \begin{pmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{pmatrix}$$dengan $F = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ dan $f_n$ menyatakan suku ke-$n$ dari barisan Fibonacci.
Langkah Basis:
Untuk $n = 1$, diperoleh
$$F^1 = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} f_2 & f_1 \\ f_1 & f_0 \end{pmatrix}.$$Jadi, $P(1)$ benar.
Langkah Induktif:
Misalkan untuk sembarang bilangan bulat positif $k,$ berlaku
$$P(k) : F^k = \begin{pmatrix} f_{k+1} & f_k \\ f_k & f_{k-1} \end{pmatrix}.$$Asumsikan pernyataan di atas bernilai benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar, yaitu
$$F^{k+1} = \begin{pmatrix} f_{k+2} & f_{k+1} \\ f_{k+1} & f_{k} \end{pmatrix}.$$Perhatikan bahwa
$$\begin{aligned} F^{k+1} & = F^k \cdot F \\ & = \begin{pmatrix} f_{k+1} & f_k \\ f_k & f_{k-1} \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \\ & = \begin{pmatrix} f_{k+1} + f_k & f_{k+1}+0 \\ f_k+f_{k-1} & f_k + 0 \end{pmatrix} \\ & = \begin{pmatrix} f_{k+2} & f_{k+1} \\ f_{k+1} & f_k \end{pmatrix}. && (\text{Definisi barisan Fibonacci}) \end{aligned}$$Jadi, $P(k+1)$ benar.
Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat positif $n.$ Artinya, $F^n = \begin{pmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{pmatrix}$ untuk setiap bilangan bulat positif $n$ dengan $F = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ dan $f_n$ menyatakan suku ke-$n$ dari barisan Fibonacci. $\blacksquare$