Barisan yang Didefinisikan Secara Rekursif
Sebuah barisan (sequence) dapat dinyatakan dalam beberapa cara. Cara pertama adalah dengan menuliskan beberapa suku pertama barisan itu, dengan harapan pembaca dapat dmengerti kelanjutan suku-suku barisan tersebut.
Misalnya, barisan 3, 5, 7, …
Cara itu sangat sederhana dan sering dilakukan. Akan tetapi, cara itu memiliki kelemahan, kadang-kadang pembaca dibuat slah mengerti terhadap kelanjutan suku-sukunya. Sebagai contoh, pada barisan 3, 5, 7, … di atas, sering diartikan bahwa pasangan tersebut adalah barisan-barisan bilangan ganjil yang lebih besar dari 2 sehingga suku-suku selanjutnya adalah 9, 11, 13, 15, … . Akan tetapi mungkin pula diartikansebagai barisan bilangan prima sehingga suku-suku selanjutnya adalah 11, 13, 17, … . Untuk sedapat mungkin menghindari salah pengertian seperti itu, suku-suku dapat dituliskan lebih panjang. Jadi, penulisan tidak hanya 3, 5, 7, …, tetapi diperpanjang menjadi 3, 5, 7, 9, 11, … (untuk menyatakan barisan bilangan ganjil yang lebih besar dari 2).
Cara kedua adalah menyatakan barisan dalam rumus eksplisit suku-sukunya. Misalnya, barisan bilangan ganjil lebih besar dari 2 dapat dinyatakan dengan rumus:
an = 2n + 1 (n bilangan bulat ≥ 1)
Dengan rumus tersebut, suku-suku setiap barisan dapat ditentukan dengan cepat. Sebagai contoh, dalam rumus an = 2n + 1 (n ≥ 1), maka :
a0 = 2.1 + 1 = 3
a1 = 2.2 + 1 = 5
a2 = 2.3 + 1 = 7 dst
Keuntungan mendefinisikan barisan dengan cara kedua adalah bahwa tiap-tiap suku barisan ditentukan secara tunggal dan penentuan suku ke-n (misal suku ke 51 = a50) dapat dilakukan secara cepat.
Cara ketiga untuk menyatakan barisan adalah secara rekursif. Suatu barisan didefinisikan secara rekursif jika kondisi awal barisan ditentukan, dan suku-suku barisan selanjutnya dinyatakan dalam hubungannya dengan sejumlah suku-suku yang sudah dinyatakan sebelumnya. Persamaan yang menyatakan hubungan antara beberapa suku tersebut dinamakan relasi rekurensi. Sebagai contoh, barisan bilangan ganjil lebih besar dari 2 yaitu 3, 5, 7, … dapat dinyatakan sebagai berikut :
Untuk semua bilangan bulat k ≥ 1,
ak = ak-1 + 2 (relasi rekurensi ) dan
a0 = 3 (kondisi awal)
Dengan relasi rekurensi dan kondisi awal, suku-suku barisan selanjutnya dapat dihitung sebagai:
a1 = a0 + 2 = 3 + 2 = 5
a2 = a1 + 2 = 5 + 2 = 7
a3 = a2 + 2 = 7 + 2 = 9
… dst
Contoh soal :
1. Diketahui : Suatu barisan c0, c1, c2, … didefinisikan secara rekursif sebagai berikut :
Untuk semua bilangan bulat k ≥ 2,
Ck = ck-1 + k ck-2 + 1
Dengan kondisi awal c0 = 1 dan c1 = 2.
Ditanya : Hitunglah c5!
Penyelesaian :
Oleh karena barisan didefinisikan secara rekursif, maka c5 tidak bisa dihitung secara langsung, tetapi harus terlebih dahulu menghitung c2, c3 dan c4.
A.c2 = c1 + 2 c0 + 1 = 2 + 2.1 + 1 = 5
c3= c2 + 3 c1 + 1 = 5 + 3.2 + 1 = 12
c4= c3 + 4 c2 + 1 = 12 + 4.5 + 1 = 33
c5= c4 + 5 c3 + 1 = 33 + 5.12 + 1 = 94
Jadi, c5 = 94
B. c5 = 95
C. c5 = 96
D. c5= 93
2. Diketahui : Misalkan a1, a2, … ; b1, b2, … dan c1, c2, … adalah 3 barisan yang semua sukunya memenuhi relasi rekurensi. Nilai suatu suku sama dengan 3 kali nilai suku sebelumnya.
Jadi, ak = 3ak-1; bk=3bk-1; ck=3 ck-1.
Tetapi kondisi awal ketiga barisan tersebut berbeda :
a1= 0 ; b1 = 1 ; c1= 2
Ditanya : Nyatakan barisan-barisan terebut dengan cara menuliskan beberapa suku awal barisannya !
A. barisan a1 adalah :0,0,0 …
barisan b1 adalah: 3,6,9…
barisan c1 adalah: 1,6,18,…
B. barisan a1 adalah :1,1,1 …
barisan b1 adalah: 3,9,81…
barisan c1 adalah: 6,18,54…
C. barisan a1 adalah :0,1,2 …
barisan b1 adalah: 3,9,27…
barisan c1 adalah: 6,18,54…
D. Pada barisan a1, a2….
a2 = 3a1 =3.0 = 0
a3 = 3a2 = 3.0 = 0
a4 = 3a3 = 3.0 = 0
pada barisan b1, b2….
b2 = 3b1 = 3.1 = 3
b3 = 3b2 =3.3 = 9
b4 = 3b3 = 3.9 = 27
pada barisan c1, c2….
c2 = 3c1 = 3.2 = 6
c3 = 3c2 = 3.6 =18
c4 = 3c3 = 3.18 = 54
dengan demikian , barisan a1 adalah :0,0,0 …
barisan b1 adalah: 3,9,27…
barisan c1 adalah: 6,18,54…
3. Diketahui : mk = 2mk-1 + 1 untuk bilangan bulat k ≥ 2
m1 = 1
Ditanya : Carilah rumus eksplisit barisan m1 , m2 ,…yang menyatakan masalah menara Hanoi.
penyelesaian :
A. mk = 3k – 1 untuk bilangan bulat k < 1
B. mk = 2mk-1 + 1
= 2 ( 2mk-2 + 1 ) + 1 = 22 mk-2 + 2.1 + 1
= 22 ( 2mk-3 + 1 ) + 2.1 + 1 = 23 mk-3 + 22.1 + 2.1 + 1
= 23 ( 2mk-4 + 1 ) + 22.1 + 2.1 + 1 = 24 mk-4 + 23.1 + 22.1 + 2.1 + 1
= 24 ( 2mk-5 + 1 ) + 23.1 + 22.1 + 2.1 + 1 = 25 mk-5 + 24.1 + 23.1 + 22.1 + 2.1 + 1
= ……….
= 2k-1mk-(k-1) + 2k-2.1 + … + 23.1 + 22.1 + 21 + 1
= 2k-1m1 + 2k-2 + … + 23 + 22 + 21 + 1
Oleh karena m1 = 1, maka :
mk = 2k-1 + 2k-2 + 2k-3 + … + 23 + 22 + 21 + 1
mk merupakan deret geometri dengan r = 2 yang besarnya = (2^((k-1)+1)-1)/(2-1) = 2k – 1
jadi, mk = 2k – 1 untuk bilangan bulat k ≥ 1
C. mk = 2k + 1 untuk bilangan bulat k > 1
D. mk = 2k – 2 untuk bilangan bulat k ≥ 2
Relasi rekursif homogen linear :
Definisi
Relasi rekursif homogen linear berderajat dua dengan koefisien konstanta merupakan relasi rekursif yang memiliki bentuk,
Definisi I
untuk setiap bilangan bulat k ≥ bilangan bulat tertentu, di mana A dan B merupakan suatu konstanta bilangan real, dengan B ≠ 0.
Relasi rekursif tersebut dikatakan “berderajat dua” karena ak dinyatakan dalam dua suku sebelumnya, ak – 1 dan ak – 2, dikatakan “linear” karena ak – 1 dan ak – 2 muncul pada suku yang berbeda dan masing-masing memiliki pangkat satu, dikatakan “homogen” karena total derajat dari masing-masing sukunya sama (sehingga tidak ada suku konstanta), dan “koefisien konstanta” karena A dan B merupakan suatu konstanta yang tidak bergantung terhadap k.
Contoh soal :
Nyatakan apakah masing-masing relasi rekursif berikut merupakan relasi rekursif homogen linear berderajat dua dengan koefisien konstanta atau bukan:
1. ak = (–4)ak – 1 + (k + 1)ak – 2
A. Iya; A = 1 = B.
B. Bukan; tidak linear.
C. Bukan; tidak berderajat dua.
D. Bukan; tidak homogen.
2. bk = bk – 1 + bk – 2
A. Bukan; tidak berderajat dua.
B. Iya; A = 0 dan B = 2.
C. Bukan; tidak linear.
D. Bukan; tidak homogen.
3. ck = (ck – 1)2 + ck – 1 ∙ ck – 2
A. Bukan; tidak berderajat dua.
B. Iya; A = 0 dan B = 2.
C. Bukan; tidak linear.
D. Bukan; tidak homogen.
4. dk = dk – 1 + dk – 2 + dk – 3
A. Bukan; tidak berderajat dua.
B. Iya; A = 0 dan B = 2.
C. Bukan; tidak linear.
D. Bukan; tidak homogen.
Nama kelompok :
Dilan Kusuma: 52413460 Dilankusuma95.blogspot.com
Ibnu Wildan: 54413182
ibnuwildann.blogspot.com
Rully Saputra: 56413647 rullysaputra02.wordpress.com
Andhika Rangga P 50413890
