Barisan dan Deret Fibonacci

Leonardo da Pisa atau Leonardo Pisano (1170 – 1250), juga dikenal sebagai Fibonacci, adalah seorang matematikawan Italia yang dikenal sebagai penemu bilangan Fibonacci.

1. Barisan Fibonacci dan Rumus Rekursif

Barisan Fibonacci dimulai dari 0 sebagai suku ke-0 dan 1 sebagai suku pertama, dan setiap sukunya sama dengan penjumlahan dua suku sebelumnya. Suku ke-n dari barisan ini disimbolkan Fₙ.

F(0) = 0, F(1) = 1

F(2) = F(0) + F(1) = 1

F(3) = F(1) + F(2) = 1 + 1 = 2

F(4) = F(2) + F(3) = 1 + 2 = 3, dan seterusnya, berikut beberapa suku dari barisan Fibonacci:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

2. Aproksimasi Barisan Geometri dan Golden Ratio

Perhatikan tabel rasio berikut:

Fn	Fn+1	Rasio
2	3	1,5
3	5	1,666667
5	8	1,6
8	13	1,625
…	…	…
144	233	1,618056
233	377	1,618026
377	610	1,618037
610	987	1,618033
987	1597	1,618034
1597	2584	1,618034

Semakin membesar nilai n, rasio antarsuku semakin mendekati nilai tertentu, misalkan r. Untuk nilai n yang sangat besar, kita dapat mengaproksimasi:

F_n = F_n-1 + F_n-2, bagi masing-masing ruas dengan F_n-2 

F_n/F_n-2  = F_n-1/F_n-2  + 1

r² ≈ r + 1

r² − r − 1 ≈ 0, selesaikan persamaan kuadrat ini

akan tetapi barisan Fibonacci selalu bernilai positif untuk setiap n positif, sehingga dipilihlah nilai r yang positif. Dengan melimitkan nilai n menuju tak hingga, akan diperoleh rasio ini:

Rasio ini disebut sebagai "Golden Ratio" atau "Rasio Emas" yang dilambangkan dengan φ.

Jadi, semakin besar nilai n, barisan Fibonacci akan semakin mendekati barisan geometri dengan rasionya adalah φ, yang disebut sebagai Golden Ratio.

3. Rumus Non-Rekursif Suku ke-n untuk Barisan Fibonacci

Ingat kembali bahwa persamaan kuadrat untuk menentukan rasio:

r² − r − 1 = 0

memiliki dua solusi, dengan satu solusi bernilai positif dan satu solusi bernilai negatif.

Kita simbolkan solusi positif dari r² − r − 1 = 0 dengan φ dan kita simbolkan solusi negatif dengan ψ, sehingga dapat dituliskan:

Untuk melihat hubungan antara barisan dan konstanta-konstanta ini, perhatikan bahwa φ dan ψ keduanya merupakan solusi dari persamaan x² = x + 1, dan dengan demikian x² − x − 1 = 0. Oleh karena itu, pangkat-pangkat dari φ dan ψ memenuhi rekursi Fibonacci. Dengan kata lain,

φⁿ = φⁿ⁻¹ + φⁿ⁻²

ψⁿ = ψⁿ⁻¹ + ψⁿ⁻²

Dari sini, dapat disimpulkan bahwa untuk setiap nilai a dan b, barisan yang didefinisikan oleh

Uₙ = aφⁿ + bψⁿ

memenuhi rekursi yang sama, yaitu

Uₙ = aφⁿ + bψⁿ 

= a(φⁿ⁻¹ + φⁿ⁻²) + b(ψⁿ⁻¹ + ψⁿ⁻²) 

= aφⁿ⁻¹ + bψⁿ⁻¹ + aφⁿ⁻² + bψⁿ⁻² 

= Uₙ₋₁ + Uₙ₋₂.

Kasus khusus untuk barisan Fibonacci dimana F₀ = 0 dan F₁ = 1:

Fₙ = Aφⁿ + Bψⁿ

di mana A dan B adalah konstanta yang ditentukan dari kondisi awal.

F₀ = 0, sehingga Aφ⁰ + Bψ⁰ = 0 ↔ A + B = 0 ↔ B = −A ...(i)

F₁ = 1, sehingga Aφ¹ + Bψ¹ = 1 ↔ Aφ + Bψ = 1 ...(ii)

Masukkan (i) ke (ii)

Aφ − Aψ = 1 ↔ A(φ − ψ) = 1 ↔ A√5 = 1 ↔ A = 1/(√5), masukkan ke (i)

B = −1/(√5), masukkan ke rumus Fₙ

Fₙ = (φⁿ − ψⁿ)/(√5)

4. Deret Fibonacci

1 + 1 + 2 + 3 + 5 + 8 + ... + Fₙ = F_n+2 − 1

Bukti:

• Langkah Basis

Tunjukkan bahwa p(n) benar untuk n = 1

p(1): 1 = F₁ = F₃ − 1 = 2 − 1 = 1, jelas benar

• Langkah Induksi

Asumsikan bahwa p(n) benar untuk n = k

p(k): 1 + 1 + 2 + 3 + 5 + 8 + ... + F_k = F_k+2 − 1

Akan ditunjukkan bahwa p(n) benar untuk n = k + 1

p(k + 1): 1 + 1 + 2 + 3 + 5 + 8 + ... + F_k + F_k+1 = F_k+2 + F_k+1 − 1

= F_k+3 − 1, berarti p(n) benar untuk n = k + 1

• Langkah Konklusi

Karena telah ditunjukkan bahwa p(n) benar untuk n = 1, dan telah diasumsikan bahwa p(n) benar untuk n = k, sehingga dapat ditunjukkan bahwa p(n) benar untuk n = k + 1. Oleh karena itu, p(n) benar untuk setiap n bilangan asli.

Jadi, rumus deret Fibonacci adalah:

1 + 1 + 2 + 3 + 5 + 8 + ... + Fₙ = F_n+2 − 1

5. Barisan Fibonacci Umum

Ingat kembali:

φⁿ = φⁿ⁻¹ + φⁿ⁻²

ψⁿ = ψⁿ⁻¹ + ψⁿ⁻²

Dari sini, dapat disimpulkan bahwa untuk setiap nilai a dan b, barisan yang didefinisikan oleh

Uₙ = aφⁿ + bψⁿ

memenuhi rekursi yang sama, yaitu

Uₙ = aφⁿ + bψⁿ 

= a(φⁿ⁻¹ + φⁿ⁻²) + b(ψⁿ⁻¹ + ψⁿ⁻²) 

= aφⁿ⁻¹ + bψⁿ⁻¹ + aφⁿ⁻² + bψⁿ⁻² 

= Uₙ₋₁ + Uₙ₋₂.

Misal suku pertama adalah u dan suku kedua adalah v

U₁ = 1u + 0v

U₂ = 0u + 1v

U₃ = 1u + 1v

U₄ = 1u + 2v

U₅ = 2u + 3v

U₆ = 3u + 5v

...

U_n = u.F_n-2 + v.F_n-1 = U₁.F_n-2 + U₂.F_n-1 

Jadi, bentuk rekursif untuk barisan Fibonacci umum adalah

U_n = U₁.F_n-2 + U₂.F_n-1 

contoh:

Suatu barisan Fibonacci umum dengan suku pertama adalah 4 dan suku kedua adalah 5, tentukan suku ke-15.

U₁₅ = U₁.F₁₃ + U₂.F₁₄ = 4.233 + 5.377 = 2817

Contoh yang cukup terkenal untuk barisan Fibonacci umum adalah barisan Lukas, dimana suku ke-0 adalah 2 dan suku ke-1 adalah 1, semakin besar nilai n, suku ke-n akan semakin mendekati perpangkatan dari golden ratio.

n	Un	φn
0	2	1
1	1	1,618033989
2	3	2,618033989
3	4	4,236067977
4	7	6,854101966
5	11	11,09016994
…	…	…
10	123	122,9918694
15	1364	1364,000733
20	15127	15126,99993

Barisan Lukas ini semakin besar n, suku ke-n akan semakin mendekati φⁿ.

6. Deret Fibonacci Umum

Ingat kembali bahwa bentuk rekursif suku ke-n barisan Fibonacci umum:

U_n = U₁.F_n-2 + U₂.F_n-1 

S_n = U₁ + U₂ + U₃ + ... + U_n 

misal U₁ = u dan U₂ = v

S_n = u + v + (u + v) + ... + u.F_n-2 + v.F_n-1 

S_n = u(1 + 0 + F₁ + F₂ + ... + F_n-2) + v(0 + F₁ + F₂ + ... + F_n-1)

ingat kembali deret Fibonacci bahwa F₁ + F₂ + ... + Fₙ = F_n+2 − 1, sehingga

S_n = u(1 + F_n − 1) + v(F_n+1 − 1)

S_n = u.F_n + v(F_n+1 − 1)

S_n = U₁.F_n + U₂.(F_n+1 − 1)

Contoh:

Suatu barisan Fibonacci umum dengan suku pertama adalah 1 dan suku kedua adalah 4, tentukan jumlah 10 suku pertama.

S₁₀ = 1.F₁₀ + 4.(F₁₁ − 1) = 1.55 + 4.(89 − 1) = 407.

Sedikit cerita dari Minfor untuk Sixtyfourians. Pada tahun 2014 pernah seseorang meminta Minfor untuk menentukan suku pertama dan suku kedua dari sebuah barisan Fibonacci umum, lalu orang itu melakukan pola rekursif sebagaimana barisan Fibonacci sampai suku ke-10. Uniknya, jumlah suku pertama sampai suku ke-10 bisa ditentukan dengan cepat. Minfor pun heran, bagaimana bisa secepat itu.

Minfor mencoba memecahkan rahasia dibalik itu, dan ternyata:

U₇ = U₁.F_7-2 + U₂.F_7-1 = 5U₁ + 8U₂ 

S₁₀ = U₁.F₁₀ + U₂.(F₁₁ − 1) = 55U₁ + 88U₂ 

perhatikan bahwa 11.U₇ = 11.(5U₁ + 8U₂) = 55U₁ + 88U₂ = S₁₀ 

ternyata jumlah 10 suku pertama sama dengan 11 kali suku ke-7.

Jadi, S₁₀ = 11.U₇ 

Minfor berhasil memecahkan ini di tahun 2015.