Relasi Rekursi – @OnggoWr – 2013 1 / 3

Relasi Rekursi

*recurrence – rekurens – rekursi – perulangan.

Kata kunci: definisi, relasi rekursi linier berkoefisien konstan, solusi relasi rekurensi,

dan solusi homogen & partikelir

• menuliskan definisi dari relasi rekursi

• memberikan sebuah contoh bentuk dari relasi rekursi

• menyebutkan jenis-jenis relasi rekursi

• menjelaskan barisan Fibonacci sebagai salah satu contoh relasi rekursi.

Definisi 1

Suatu relasi rekursi untuk sebuah barisan *𝑎𝑛+ merupakan

sebuah rumus untuk menyatakan 𝑎𝑛 ke dalam satu atau lebih

suku-suku sebelumnya dari barisan tersebut, untuk suatu

bilangan bulat nonnegatif 𝑛.

Suatu barisan disebut solusi dari sebuah relasi rekursi jika suku-

suku pada barisan tersebut memenuhi relasi rekursinya.

Contoh 1

Misal *𝑎𝑛+ barisan yang memenuhi relasi rekursi

𝑎𝑛 = 𝑎𝑛−1 − 𝑎𝑛−2 untuk 𝑛 ≥ 2, lalu misalkan 𝑎0 = 3 dan 𝑎1 = 5.

Tentukan nilai 𝑎2 dan 𝑎3.

Jawab

Karena 𝑎2 = 𝑎1 − 𝑎0, maka 𝑎2 = 2.

Karena 𝑎3 = 𝑎2 − 𝑎1, maka 𝑎3 = −3.

Contoh 2

Untuk bilangan bulat nonnegatif 𝑛, apakah barisan 𝑎𝑛 = 3𝑛,

𝑎𝑛 = 2𝑛 dan 𝑎𝑛 = 5 merupakan solusi bagi relasi rekursi

𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 ?

Jawab

(i) Misal 𝑎𝑛 = 3𝑛, untuk bilangan bulat nonnegatif 𝑛. Maka

Relasi Rekursi – @OnggoWr – 2013 2 / 3

𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2

𝑎𝑛 = 2(3(𝑛 − 1)) − 3(𝑛 − 2)

𝑎𝑛 = 3𝑛.

Maka 𝑎𝑛 = 3𝑛 merupakan solusi bagi relasi rekursi 𝑎𝑛 = 2𝑎𝑛−1 −

𝑎𝑛−2.

(ii) Misal 𝑎𝑛 = 2𝑛, untuk bilangan bulat nonnegatif 𝑛. Maka

𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2

𝑎𝑛 = 2(2(𝑛−1)) − 2(𝑛−2)

𝑎𝑛 = 2𝑛 − 2𝑛−2

𝑎𝑛 = 2𝑛 (1 −1

4) = 2𝑛 ∙

3

4≠ 2𝑛.

Maka 𝑎𝑛 = 2𝑛 bukan merupakan solusi bagi relasi rekursi

𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2.

(iii) Misal 𝑎𝑛 = 5, untuk bilangan bulat nonnegatif 𝑛. Maka

𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2

𝑎𝑛 = 2(5) − 5

𝑎𝑛 = 5

Maka 𝑎𝑛 = 5 merupakan solusi bagi relasi rekursi 𝑎𝑛 = 2𝑎𝑛−1 −

𝑎𝑛−2.

Catatan: Kondisi awal (𝑎0) akan menentukan suku-suku pada

barisan berikutnya.

Contoh 3

Tentukan barisan yang merupakan solusi dari relasi rekursi

𝑎𝑛 = 3𝑎𝑛−1, jika diketahui 𝑎0 = 2.

Jawab

𝑎𝑛 = 3𝑎𝑛−1

𝑎𝑛 = 3(3𝑎𝑛−2) = 32 ∙ 𝑎𝑛−2

Relasi Rekursi – @OnggoWr – 2013 3 / 3

𝑎𝑛 = 3(3(3𝑎𝑛−3)) = 33 ∙ 𝑎𝑛−3

⋮

𝑎𝑛 = 3𝑛 ∙ 𝑎𝑛−𝑛 = 3𝑛 ∙ 𝑎0

𝑎𝑛 = 2 ∙ 3𝑛

Sehingga barisan 𝑎𝑛 = 2 ∙ 3𝑛 merupakan solusi dari relasi rekursi

𝑎𝑛 = 3𝑎𝑛−1 dengan nilai awal 𝑎0 = 2.

Jenis-jenis Relasi Rekursi

Definisi 2

Suatu relasi rekursi linier homogen berderajat 𝑘 dengan

koefisien konstan memiliki bentuk umum:

𝑎𝑛 = 𝑐1𝑎𝑛−1 + 𝑐2𝑎𝑛−2 +⋯+ 𝑐𝑘𝑎𝑛−𝑘

dengan 𝑐1, 𝑐2, … , 𝑐𝑘 adalah bilangan real, dan 𝑐𝑘 ≠ 0.

Perhatikan tebel berikut ini:

Relasi Rekursi Linier Homogen Koef. Konst. Degree

𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 2

𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−22 2

𝐻𝑛 = 2𝐻𝑛−1 + 1 1

𝑏𝑛 = 𝑛𝑏𝑛−1 1