Materi dan Contoh Soal Relasi Rekurensi Linier Berkoefisien Konstan

RELASI REKURENSI LINIER BERKOEFISIEN

KONSTAN

RELASI REKURENSI LINIER BERKOEFISIEN

KONSTAN

Sebuah relasi rekurensi linier berkoefisien konstan dari sebuah fungsi numerik

a, secara umum ditulis sebagai berikut

C0 an + C1 an-1 + C2 an-2 + … + Ck an-k = f(n)

dimana Ci , untuk i = 0,1,2,…,k adalah konstan dan f(n) adalah sebuah fungsi

numerik dengan variabel n.

Relasi rekurensi tersebut dikatakan relasi rekurensi linier berderajat k , jika C0

dan Ck keduanya tidak bernilai 0 (nol).

Contoh 5.1.

2 an + 2 an-1 = 3n adalah sebuah relasi rekurensi linier berderajat 1

tn = 7 tn-1 adalah sebuah relasi rekurensi linier berderajat 1

an – an-1 – an-2 = 0 adalah sebuah relasi rekurensi linier berderajat 2

bn-3 – 3bn = n+3 adalah sebuah relasi rekurensi linier berderajat 3 

Untuk sebuah relasi rekurensi dengan koefisien konstan derajat k, jika

diberikan k buah harga aj yang berurutan am-k , am-k+1 , … , am-1 untuk suatu nilai

m tertentu, maka setiap nilai am yang lain dapat dicari dengan rumus

am =

0

1

C

 ( C1 am-1 + C2 am-2 + … + Ck am-k - f(m) )

dan selanjutnya, harga am+1 juga dapat dicari dengan cara

am+1 =

0

1

C

 ( C1 am + C2 am-1 + … + Ck am-k+1 - f(m+1) )

demikian pula untuk nilai am+2 , am+3 dan seterusnya. Di lain pihak, harga am-k-1

dapat pula dihitung dengan

am-k-1 =

k

C

1

 ( C1 am-1 + C2 am-2 + … + Ck-1 am-k - f(m-1) )

28

dan am-k-2 dapat dicari dengan

am-k-2 =

Ck

1

 ( C1 am-2 + C2 am-3 + … + Ck-1 am-k-1 - f(m-2) ).

Harga am-k-3 dan seterusnya dapat dicari dengan cara yang sama. Jadi, untuk sebuah

relasi rekurensi linier berkoefisien konstan derajat k , bila harga k buah aj yang

berurutan diketahui, maka harga aj yang lainnya dapat ditentukan secara unik.

Dengan kata lain, k buah harga aj yang diberikan merupakan himpunan syarat

batas (kondisi batas) yang harus dipenuhi oleh relasi rekurensi tersebut untuk dpat

memperoleh harga yang unik.

5.1. SOLUSI DARI RELASI REKURENSI

Seperti telah disebutkan pada bagian sebelumnya, sebuah relasi rekurensi

linier berkoefisien konstan dapat dinyatakan dalam bentuk C0 an + C1 an-1 + … + Ck

an-k = f(n). Bila nilai f(n) = 0, maka diperoleh relasi rekurensi yang memenuhi

C0 an + C1 an-1 + C2 an-2 + … + Ck an-k = 0.

Relasi rekurensi demikian disebut dengan relasi rekurensi homogen dan solusi dari

relasi rekurensi homogen ini dinamakan solusi homogen atau jawab homogen.

Dalam usaha mencari solusi dari sebuah relasi rekurensi perlu dicari dua

macam solusi, yaitu :

1. Solusi homogen (jawab homogen) yang diperoleh dari relasi rekurensi linier

dengan mengambil harga f(n) = 0.

2. Solusi khusus/partikuler (jawab khusus) yang memenuhi relasi rekurensi

sebenarnya.

Solusi total atau jawab keseluruhan dari sebuah relasi rekurensi adalah jumlah

dari solusi homogen dan solusi partikuler. Misalkan an

(h) = (a0

(h), a1

(h), … ) adalah

solusi homogen yang diperoleh dan misalkan an

(p) = (a0

(p), a1

(p), … ) adalah solusi

partikuler yang diperoleh, maka solusi total dari relasi rekurensi yang dimaksud

adalah

an = a(h) + a(p)

29

Soal Latihan 5.1.

1. Tentukan lima nilai pertama dari an = an-1 + 3 an-2 jika diketahui a0 = 1 dan a1 = 2.

2. Misalkan {an} sebuah barisan bilangan yang memenuhi relasi rekurensi

an = an-1 – an-2 untuk n = 2, 3, 4,... dimana a0 = 3 dan a1 = 5. Tentukan a2 dan a3 .

3. Diketahui gn = gn-1 + 2 gn-2 dimana g6 = 11 dan g4 = 3. Tentukan g7 dan g9 .

4. Tentukan relasi rekurensi untuk menghitung jumlah langkah yang diperlukan untuk memindahkan n cakram pada permainan menara Hanoi.

5. Sebuah bola dijatuhkan dari ketinggian 15 meter. Bola tersebut selalu memantul dan mencapai ketinggian sepertiga dari ketinggian sebelumnya. Nyatakan relasi rekurensi untuk menghitung tinggi bola pada pantulan ke t.