RELASI REKURSIF
Definisi
Sebuah relasi rekursif (berulang) untuk barisan
a0 , a1, a2, a3, . . . , an-1
adalah suatu persamaan yang menghubungkan
an dengan suku-suku sebelumnya.
Catatan:
1. Untuk mendefinisikan sebuah barisan, relasi berulang
memerlukan nilai awal yang sudah ditentukan.
2. Syarat awal untuk barisan a0, a1, a2, . . . adalah nilai-nilai
yang diberikan secara eksplisit pada beberapa suku dari
barisan tersebut.
Contoh-contoh:
1. Relasi rekursif dari barisan (3, 7 , 11, 15, . . . )
Misalkan an menyatakan suku ke-n dari barisan tsb.
Perhatikan utk n ≥ 1, suku ke-n dari barisan adalah jumlah
suku sebelumnya dengan 4, jika a0 = 3.
Sehingga relasi rekursif utk an adalah:
a0 = 3, an = an-1 + 4 , n ≥ 1
a0 = 3 disebut syarat awal
an = an-1 + 4, disebut bagian rekursif
2. Barisan Fibonacci (1, 1 , 2, 3, 5, 8,13, 21, 34, . . .)
Misalkan Fn menyatakan suku ke-n dari barisan tsb.
Perhatikan utk n ≥ 3, suku ke-n dari barisan adalah
jumlah dua suku sebelumnya.
Sehingga relasi rekursif utk Fn adalah:
F1 = F2 = 1, Fn = Fn-1 + Fn-2 , n ≥ 3
F1 = 1, dan F2 = 1 disebut syarat awal
Fn = Fn-1 + Fn-2, disebut bagian rekursif
3. Misalkan Pn menyatakan banyaknya permutasi dari n
obyek, maka:
P1 = 1 (karena hanya ada satu permutasi dari 1 obyek)
Untuk n ≥ 2, Pn diperoleh dg cara berikut:
Terdapat n kemungkinan posisi dari satu obyek tertentu,
setiap kemungkinan posisi dari satu obyek ini diikuti oleh
permutasi dari n-1 obyek.
Karena banyak permutasi dari n-1 obyek ini adalah Pn-1
maka terdapat hubungan Pn = nPn-1.
Dengan demikian diperoleh
P1 = 1, Pn = nPn-1 , n ≥ 2
Bentuk ini disebut relasi rekursif untuk Pn
P1 = 1 disebut syarat awal
Pn = nPn-1, disebut bagian rekursif
Relasi Rekursif Liner
Koefisien Konstan
Bentuk umum relasi rekursif linier koefisien konstan adalah
C0 an + C1 an-1 + C2 an-2 + … + Ck an-k = f(n)
dimana Ci adalah konstan , untuk setiap i = 0,1,2,…,k dan f(n)
adalah sebuah fungsi numerik dengan variabel n.
Relasi rekursif tersebut dikatakan relasi rekursif linier berderajat k ,
jika C0 ≠ 0 dan Ck ≠ 0.
Contoh Relasi Rekursif Liner
Koefisien Konstan
a) 2 an + 2 an-1 = 3n relasi rekursif linier
berderajat 1
b) tn = 7 tn-1 relasi rekursif linier
berderajat 1
c) an– an-1– an-2 = 0 relasi rekursif linier
berderajat 2
d) bn-3 – 3bn = n+3 relasi rekursif linier
berderajat 3
Relasi Rekursif Liner
Homogen Koefisien Konstan
Untuk relasi rekursif linier koefisien konstan:
C0 an + C1 an-1 + … + Ck an-k = f(n).
Bila nilai f(n) = 0, maka diperoleh relasi rekursif yang
memenuhi
C0 an + C1 an-1 + C2 an-2 + … + Ck an-k = 0.
Relasi rekursif ini disebut dengan relasi rekursif homogen
Solusi dari relasi rekursif homogen ini dinamakan solusi
homogen atau jawab homogen.
• Solusi homogen dari sebuah persamaan rekursif linier dengan
koefisien konstan dinyatakan dalam bentuk Axn , dimana x adalah
akar karakteristik dan A adalah konstanta yang akan ditentukan
kemudian untuk memenuhi syarat batas yang diberikan.
• Dengan substitusi Axn kepada an pada persamaan homogen
C0 an + C1 an-1 + C2 an-2 + … + Ck an-k = 0 ,
maka diperoleh:
C0 Axn + C1 Axn-1 + C2 Axn-2 + … + Ck Axn-k = 0.
C0 xn + C1 xn-1 + C2 xn-2 + … + Ck xn-k = 0
C0 xk + C1 xk-1 + C2 xk-2 + … + Ck = 0
Persamaan ini merupakan persamaan karakteristik dari relasi
rekursif yang diberikan
Kasus 1: Akar-akarKarakteristik Berbeda
C0 xk + C1 xk-1 + C2 xk-2 + … + Ck = 0
Bila persamaan karakteristik di atas memiliki sebanyak k akar
karakteristik berbeda (x1 x2 … xk) , maka solusi homogen
dari relasi rekursifnya dinyatakan dalam bentuk
an(h) = A1 x1n + A2 x2n + … + Ak xkn
Dimana:
an(h) = solusi homogen
xi = akar karakteristik dari persamaan karakeristik
Ai = konstanta yang akan dicari yg memenuhi syarat batas yang
ditentukan.
Contoh 1.
Tentukan solusi homogen dari relasi rekursif b n + bn-1 – 6 bn-2 = 0 dengan kondisi
batas b0 = 0 , b1 = 1 .
Penyelesaian :
Relasi rekursif tersebut adalah relasi rekursif homogen, karena f(n) = 0.
Persamaan karakteristik dari relasi rekursif b n + bn-1 – 6 bn-2 = 0 adalah x2 + x - 6
=0
atau (x + 3) ( x - 2) = 0
hingga diperoleh akar-akar karakteristik x1 = -3 dan x2 = 2.
Oleh karena akar-akar karakteristiknya berbeda, maka solusi homogennya adalah bn(h)
= A1 x1n + A2 x2n
bn(h) = A1 (-3)n + A2 . 2n.
bn(h) = A1 (-3)n + A2 . 2n
Dengan kondisi batas b0 = 0 dan b1 = 1 , maka
b0(h) = A1 (-3)0 + A2 . 20 0 = A1 + A2 .
b1(h) = A1 (-3)1 + A2 . 21 1 = -3 A1 + 2 A2 .
bila diselesaikan maka akan diperoleh harga A1 = (-
1/5) dan A2 = 1/5, sehingga jawab homogen dari
1 1 n
(h)
relasi
n ( 3 ) b
b rekurensi n
2
n + bn-1 – 6 bn-2 = 0 adalah
5 5
Kasus 2: Akar-akar Karakteristik Rangkap
C0 xk + C1 xk-1 + C2 xk-2 + … + Ck = 0
Jika akar karakteristik x1 dari persamaan karakteristik
merupakan akar rangkap yang berulang sebanyak m kali,
maka bentuk solusi homogen yang sesuai untuk akar rangkap
tersebut adalah
(A1 . nm-1 + A2 . nm-2 + … + Am-2 n2 + Am-1 . n + Am ) x1n
dimana Ai adalah konstanta yang nantinya akan ditentukan
untuk memenuhi kondisi batas yang ditentukan.
Contoh 2.
Tentukan solusi dari relasi rekursif a n + 4 an-1 + 4 an-2 = 0 .
Penyelesaian :
Relasi rekursif homogen : an + 4 an-1 + 4 an-2 = 0.
Persamaan karakteristiknya adalah x2 + 4x + 4 = 0
(x + 2) ( x + 2) = 0
diperoleh akar-akar karakteristik x1 = x2 = -2 , m = 2,
Oleh karena akar-akar karakteristiknya rangkap 2,
maka solusi homogennya adalah
an(h) = (A1 nm-1 + A2 nm-2) x1n ,
an(h) = (A1 n + A2 ) (-2)n
Contoh 3
Tentukan solusi homogen dari relasi rekursif
4 an - 20 an-1 + 17 an-2 – 4 an-3 = 0.
Penyelesaian :
Persamaan karakteristiknya : 4x3 - 20x2 + 17x - 4 = 0
akar-akar karakteristiknya : x1 = ½ , x2 = ½ dan x3 = 4
solusi homogennya adalah:
an(h) = (A1 n + A2 ) (½)n + A3 . 4n
Soal-soal Latihan
Tentukan solusi homogen dari relasi rekursif berikut :
1. an – 7 an-1 + 10 an-2 = 0 dengan syarat batas a0 = 0 dan a1 = 3.
2. an – 4 an-1 + 4 an-2 = 0 dengan syarat batas a0 = 1 dan a1 = 6.
3. an + 6 an-1 + 9 an-2 = 3 dengan syarat batas a0 = 1 dan a1 = 1.
4. an - 2 an-1 + 2 an-2 – an-3 = 0 dengan a0 = 1, a1 = 1 dan a2 = 1 .
5. Jika an menyatakan banyaknya cara untuk menempatkan
n koin berbeda di dalam 5 kotak. Bentuk relasi
rekursifnya dan tentukan pula penyelesaiannya.
6. Jika sebuah tangga memiliki n buah anak tangga dan
seseorang diminta menaiki tangga tersebut dengan aturan
setiap kali melangkah diperolehkan melangkah satu atau
dua anak tangga sekaligus.
a. Apabila bn menyatakan banyaknya cara yang berbeda
orang tersebut dapat menaiki tangga dengan n anak
tangga tersebut, bentuklah relasi rekursif dari bn.
b. Tentukan pula penyelesaian relasi rekursif dari bn
tersebut.