RELASI REKURSI
*recurrence – rekurens – rekursi - perulangan
Definisi Relasi Rekursi
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-sukunya pada barisan
tersebut memenuhi relasi rekursinya.
Penyelesaian Relasi Rekursif Linier dgn
koefisien konstan
Salah satu metode yang digunakan adalah dengan persamaan karakteristik.
Bentuk umum relasi rekursif linier dgn koefisien konstan berderajat 𝑘 adalah
𝑐0 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 𝑓 𝑛 , dengan 𝑛 ≥ 𝑘, 𝑛, 𝑘 ∈ ℤ
1. Relasi rekurensi homogen dgn koefisien konstan (𝑓 𝑛 = 0)
𝑐0 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0
2. Relasi rekurensi tak homogen dgn koefisien konstan (𝑓 𝑛 ≠ 0)
𝑐0 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 ≠ 0
Solusi Rekurensi Homogen Linier
Misalkan diberikan suatu relasi rekurensi homogen linier :
𝑐0 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0, dengan 𝑛 ≥ 𝑘, 𝑛, 𝑘 ∈ ℤ
Persamaan karakteristik yang sesuai dengan rekurensi tersebut :
𝑡 𝑘 + 𝑐1 𝑡 𝑘−1 + ⋯ + 𝑐𝑘 = 0 (*)
Misalkan 𝛼1 , 𝛼2 , … 𝛼𝑘 adalah akar-akar persamaan karakteristik (*). Ada 2
kemungkinan akar
1. Semua akar berbeda
Solusi berbentuk 𝑎𝑛 = 𝐶1 𝛼1 𝑛 + 𝐶2 𝛼2 𝑛 + ⋯ + 𝐶𝑘 𝛼𝑘 𝑛
2. Ada akar kembar
Misalkan terdapat akar yang sama 𝛼1 = 𝛼2 = ⋯ = 𝛼𝑝 , 𝛼𝑝+1 , . . , 𝛼𝑘 ,
maka solusi berbentuk
𝑎𝑛 = 𝐶1 + 𝐶2 𝑛 + ⋯ + 𝐶𝑝 𝑛𝑝−1 𝛼1 𝑛 + 𝐶𝑝+1 𝛼𝑝+1 𝑛 + ...+𝐶𝑘 𝛼𝑘 𝑛
Solusi Rekurensi Homogen Linier
Solusi NonHomogen = Solusi Homogen + Solusi Khusus
𝒇(𝒏) Sifat Persamaan Karakteristik Bentuk Solusi Khusus
𝐾𝑎𝑛 𝑎 bukan akar persamaan 𝑃𝑎𝑛
karakteristik 𝑐(𝑡)
𝐾𝑎𝑛 𝑎 adalah akar persamaan 𝑃𝑛𝑚 𝑎𝑛
karekteristik 𝑐 (𝑡) kelipatan 𝑚
𝐾𝑛 𝑠 𝑎𝑛 𝑎 bukan akar persamaan 𝑃0 + 𝑃1 𝑛+. . +𝑃𝑠 𝑛 𝑠 𝑎𝑛
karakteristik 𝑐(𝑡) (𝑐(𝑎) ≠ 0)
𝐾𝑛 𝑠 𝑎𝑛 𝑎 adalah akar persamaan 𝑃0 + 𝑃1 𝑛+. . +𝑃𝑠 𝑛 𝑠 𝑛𝑚 𝑎𝑛
karakteristik 𝑐 (𝑡) kelipatan 𝑚
𝐾𝑛 𝑠 1 bukan akar persamaan 𝑃0 + 𝑃1 𝑛+. . +𝑃𝑠 𝑛 𝑠
karakteristik 𝑐(𝑡) (𝑐(1) ≠ 0)
𝐾𝑛 𝑠 1 adalah akar oersamaan 𝑃0 + 𝑃1 𝑛+. . +𝑃𝑠 𝑛 𝑠 𝑛𝑚
karakteristik 𝑐 (𝑡) kelipatan 𝑚
Contoh
Selesaikan relasi rekurensi berikut lewat persamaan karakteristiknya :
𝒂𝒏 = 𝟑𝒂𝒏−𝟏 + 𝟒𝒂𝒏−𝟐
Untuk 𝑛 ≥ 2 dengan kondisi awal 𝑎0 = 1 dan 𝑎1 = 3
Penyelesaian :
Pindahkan semua suku ke ruas kiri sehingga menjadi
𝒂𝒏 − 𝟑𝒂𝒏−𝟏 − 𝟒𝒂𝒏−𝟐 = 𝟎
merupakan relasi rekurensi homogen linier dengan koefisien konstan sehingga
persamaan karakteristik yang sesuai adalah
𝑡 2 − 3𝑡 − 4 = 𝑡 − 4 𝑡 + 1 = 0
Yang memiliki akar-akar karakteristik 𝛼1 = 4 dan α2 = −1
Oleh karena semua akar-akar karakteristik berbeda, maka penyelesaiannya adalah :
𝑎𝑛 = 𝑐1 (4)𝑛 +𝑐2 −1 𝑛
Untuk menentukan 𝑐1 dan 𝑐2 digunakan kondisi awal :
0 0
𝑎0 = 1 sehingga 1 = 𝑐1 4 + 𝑐2 −1
1 = 𝑐1 + 𝑐2
1 1
𝑎1 = 3 sehingga 3 = 𝑐1 4 + 𝑐2 −1
3 = 4𝑐1 − 𝑐2
4 1
yang memiliki penyelesaian 𝑐1 = 5 dan 𝑐2 = 5
Dengan demikian, penyelesaian relasi rekurensi 𝑎𝑛 − 3𝑎𝑛−1 − 4𝑎𝑛−2 = 0
adalah
𝟒 𝒏
𝟏 𝒏
𝒂𝒏 = (𝟒) + −𝟏
𝟓 𝟓