13.relasi Rekurensi [PDF]

Citation preview

Tim Matematika Diskrit



Barisan yang didefinisikan secara rekursif



Contoh 1. Suatu barisan c0, c1, c2, … didefinisikan secara rekursif sbb: Untuk semua bilangan bulat k ≥ 2, ck = ck-1 + k ck-2 + 1 Dengan kondisi awal: c0 = 1 dan c1 = 2. Hitunglah c5. Penyelesaian: Karena barisan didefinisikan secara rekursif, maka c5 tidak bisa dihitung secara langsung, tetapi harus terlebih dahulu menghitung c2, c3, dan c4. 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



Contoh 2. Misalkan a1, a2, …; b1, b2, … dan c1, c2, … adalah 3 barisan yang semuanya memenuhi relasi rekurensi: Nilai suatu suku sama dengan 3 kali nilai suku sebelumnya. Jadi ak = 3 ak-1; bk = 3 bk-1; ck = 3 ck-1 Tetapi kondisi awal ketiga barisan tersebut berbeda: a1 = 0; b1 = 1; c1 = 2 Nyatakan barisan-barisan tersebut dengan cara menuliskan beberapa suku awal barisan tersebut! Apakah ketiganya merupakan barisan yang sama? Penyelesaian: Barisan ai adalah: 0, 0, 0, … Barisan bi adalah: 3, 9, 27, … Barisan ci adalah: 6, 18, 54, … Tampak bahwa ketiga barisan tersebut berbeda



Contoh 3. (Bilangan Fibonacci) Pada tahun 1202, Leonardo of Pisa yang dikenal dengan Fibonacci mengemukakan masalah sbb: Misalkan mula-mula ada sepasang kelinci (jantan dan betina) yang baru lahir. Setiap bulan, kelinci-kelinci yang sudah berumur 2 bulan akan beranak 2 ekor kelinci (jantan dan betina). Carilah banyaknya kelinci setelah 12 bulan (dan secara umum setelah n bulan) Penyelesaian: Pada bulan ke-0, ada 1 pasang kelinci (sebut pasangan A) Pada bulan ke-1, tetap masih ada 1 pasang kelinci (A) karena belu cukup umur untuk beranak Pada bulan ke-2, pasangan A mempunyai sepasang anak (sebut pasangan B). Jadi total ada 2 pasang kelinci. Pada bulan ke-3, pasangan A mempunyai sepasang anak lagi (sebut pasangan C), tetapi pasangan B belum punya anak krn belum cukup umur. Total 3 pasang. Pada bulan ke-4, pasangan A mempunyai sepasang anak lagi (sebut pasangan D), pasangan B juga mempunyai sepasang anak (sebut pasangan E). Total 5 pasang kelinci). Dan seterusnya …



Anak kelinci yang lahir pada tiap bulan ke - dinyatakan dalam tabel sbb: Induk Kelinci



1



2



3



4



5



6



A



-



B



C



D



F



I



B



-



-



-



E



G



J



C



-



-



-



-



H



K



D



-



-



-



-



-



L



E



-



-



-



-



-



M



F



-



-



-



-



-



-



G



-



-



-



-



-



-



Misalkan Fn menyatakan banyak pasangan kelinci yang hidup pada bulan ke-n (n ≥ 0) Maka: F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, … Fn terbentuk dari 2 hal yaitu: Fn-1 pasang kelinci dari bulan sebelumnya ditambah dengan jumlah pasangan anak yang dilahirkan. Karena kelinci yang mempunyai anak adalah yang berumur minimal 2 bulan, maka jumlah pasang anak yang diperoleh sama dengan jumlah kelinci pada 2 bulan sebelumnya yaitu Fn-2. Maka didapat relasi Fn = Fn-1 + Fn-2 dengan F0 = 1; F1 = 1. Relasi ini dikenal dengan relasi Fibonacci. Fi yang terbetuk disebut Bilangan Fibonacci.



Contoh 4. (Menara Hanoi) Pada tahun 1883, seorang ahli matematika Perancis bernama Edouard Lucas mengemukakan suatu teka-teki sbb: Menurut legenda, ada sebuah kuil Budha yang di dalamnya terdapat 3 tiang berdiameter kecil terbuat dari permata. Pada waktu dunia diciptakan, Tuhan menciptakan 64 buah cakram dengan ukuran berbeda-beda pada salah satu tiang. Cakram-cakram tesebut ditumpuk satu di atas yang lain, sedemikian hingga semakin ke atas, diameter cakram semakin mengecil. Biksu-biksu kuil tersebut berusaha memindahkan cakram satu demi satu dari satu tiang ke tiang lain, sehingga semua cakram berpindah dari tiang A ke tiang C. Syaratnya: pemindahan hanya boleh dilakukan satu persatu, dan pada setiap keadaan, cakram dengan diameter yang lebih kecil harus berada di atas cakram dengan diameter yang lebih besar.



Menurut legenda, setelah pemindahan tersebut selesai, maka tiang, cakram, dan semua yang ada akan hancur menjadi debu. Bersamaan dengan itu, akan terdengar halilintar yang menggelegar dan dunia akan hilang (kiamat). Misalkan biksu-biksu tersebut dapat memindahkan sebuah cakram dalam satu detik, berapa lama dunia akan kiamat sejak diciptakan? Penyelesaian:



Suatu cara penyelesaian yang efisien adalah secara rekursif. Misalkan kita tahu tentang memindahkan (k-1) cakram dari tiang ke tiang lain. Maka cara paling efisien untuk memindahkan k cakram dari tiang A ke tiang C adalah sbb:



Langkah 1. pindahkan (k-1) buah cakram dari tiang A ke tiang B. Jika k > 2, eksekusi langkah ini memerlukan sejumlah proses untuk memindahkan cakram satu per satu. Langkah 2. pindahkan cakram yang terletak paling bawah dari tiang A ke tiang C. Langkah 3. pindahkan (k-1) buah cakram dari tiang B ke tiang C. seperti langkah 1, jika k > 2, langkah 3 juga memerlukan sejumlah proses di dalamnya.



Misalkan mn = jumlah langkah minimal untuk memindahkan n buah cakram dari satu tiang ke tiang lain. Perhatikan bahwa mn tidak dipengaruhi oleh asal dan tujuan tiang. mn juga tidak tergantung dari banyaknya cakram yang terletak di bawah n buah cakram yang dipindah tersebut.



Langkah 1 memerlukan mk-1 kali perpindahan. Langkah 2 memerlukan 1 kali perpindahan. Langkah 3 memerlukan mk-1 kali perpindahan. Jadi jumlah keseluruhan perpindahan minimal adalah: mk = mk-1 + 1 + mk-1 = 2mk-1 + 1 Kondisi awal terjadi jika k = 1 Diperoleh persamaan rekursif m1, m2, …, sbb: mk = 2 mk-1 + 1 (relasi rekurensi) m1 = 1 (kondisi awal) Maka untuk memindahkan: 2 cakram, dibutuhkan m2 = 2 m1 + 1 = 2.1 + 1 = 3 langkah 3 cakram, dibutuhkan m3 = 2 m2 + 1 = 2.3 + 1 = 7 langkah 4 cakram, dibutuhkan m4 = 2 m3 + 1 = 2.7 + 1 = 15 langkah, dst 64 cakram, dibutuhkan m64 = … = 1,844674.1019 detik ≈ 5.84542.1011 tahun



Contoh 5. (Perhitungan bunga bank) Jika kita menyimpan uang di bank, biasanya bank memberikan bunga yang dihitung per tahun, misal i. Jika bunga diberikan per periode tertentu dan dalam satu tahun ada m kali periode, maka besarnya bunga per periode = i/m. Sebagai contoh, suatu bank memberikan bunga 12% = 0,12 per tahun dan bunga diberikan secara bulanan. Maka besarnya bunga per bulan = 0,12/12 = 0,01. Untuk tiap bilangan positif k ≥ 1, misalkan: Pk = jumlah tabungan pada akhir periode ke-k (tanpa ada transaksi). Nyatakan Pk sehingga relasi rekurensi suku-suku sebelumnya!



Penyelesaian: Besarnya bunga selama periode ke-k adalah jumlah tabungan pada akhir periode ke (k-1) dikalikan dengan bunga untuk periode tersebut. Jadi, bunga selama periode ke-k adalah (Pk-1) (i/m). Jumlah uang tabungan pada akhir periode ke-k (=Pk) didapat dengan cara menjumlahkan uang tabungan pada akhir periode ke(k-1) (=Pk-1) dengan bungan yang didapat selama periode ke-k tersebut. Maka jumlah uang tabungan pada akhir periode ke-k adalah: Pk = Pk-1 + Pk-1 (i/m)



= Pk-1 (1 + i/m) Kondisi awal (P0) adalah jumlah uang tabungan mula-mula.



Penyelesaian Relasi Rekurensi dengan Iterasi



n(n  1) 1  2  3  ...  n  2 n(n  1)(2n  1) 2 2 2 1  2  3  ...  n  6 n(n  1)(n  2) 1.2  2.3  3.4  ...  n(n  1)  3 n 1 r 1 2 n 1  r  r  ...  r  , r 1 r 1



Contoh 6. Misalkan a0, a1, a2, …, barisan yang didefinisikan secara rekursif sbb: Untuk semua bilangan bulat k ≥ 1, ak = ak-1 + 2 (relasi rekurensi), a0 = 1 (kondisi awal) Carilah rumus eksplisit barisan tersebut dengan metode iterasi. Penyelesaian: ak = ak-1 + 2 = (ak-2) + 2 = ak-2 + 2.2 = (ak-3) + 2.2 = ak-3 + 3.2 = (ak-4) + 3.2 = ak-4 + 4.2 Sesuai pola, terlihat bahwa ak = ak-k + k.2 = a0 + 2.k Karena a0 = 1 maka penyelesaian persamaan rekursif adalah ak = 1 + 2k. Jika diselesaikan dengan cara menaik: a1 = a0 + 2 a2 = a1 + 2 = (a0 + 2) + 2 = a0 + 2.2 a3 = a2 + 2 = (a0 + 2 + 2) + 2 = a0 + 3.2 … ak = a0 + k.2 = 1 + 2k



Contoh 7. Carilah rumus eksplisit barisan m1, m2, … yang menyatakan masalah menara Hanoi. mk = 2 mk-1 + 1 untuk bilangan bulat k ≥ 2 m1 = 1 Penyelesaian: mk = 2 mk-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 =… = 2k-1 mk-(k-1) + 2k-2.1 + … + 23.1 + 22.1 + 21 + 1 = 2k-1 m1 + 2k-2 + … + 23 + 22 + 21 + 1 Karena m1 = 1 maka: mk = 2k-1 + 2k-2 + 2k-3 + … + 23 + 22 + 21 + 1 mk merupakan deret geometri dengan r = 2 yang besarnya = 2k -1 Jadi mk = 2k -1 untuk bilangan bulat k ≥ 1



Contoh 8. Misalkan Kn adalah graf dengan n buah titik dan setiap pasang titik dihubungkan dengan sebuah garis (Graf Lengkap). Jika Sn menyatakan jumlah garis dalam Kn, maka: a. Buktikan bahwa Sn memenuhi relasi rekurensi Sn = Sn-1 + (n-1) dan kondisi awal S1 = 0 b. Selesaikan relasi rekurensi Sn tersebut. Penyelesaian: a. Kn untuk n = 1, 2, 3, 4, dan 5



K1



K2



K3



K4



K5



Banyaknya garis dalam K4 adalah banyaknya garis K3 ditambah dengan banyaknya garis baru yang harus dibuat akibat penambahan satu buah titik. Banyaknya garis baru yang ditambahkan pada K4 sama dengan banyaknya titik pada K3. Jadi S4 = S3 + 3. Secara umum: Sn = Sn-1 + (n-1) Kondisi awal S1 = 0 jelas benar karena tidak mungkin membuat garis dari satu buah titik. b. Sn



= Sn-1 + (n-1) = (Sn-2 + (n-2)) + (n-1) = Sn-2 + (n-2) + (n-1) = (Sn-3 + (n-3)) + (n-2) + (n-1) = Sn-3 + (n-3) + (n-2) + (n-1) =… = Sn-(n-1) + (n-(n-1)) + …+ (n-3) + (n-2) + (n-1) = S1 + 1 + 2 + … + (n-2) + (n-1) Karena S1 = 0 maka Sn = 1 + 2 + … + (n-2) + (n-1) = ½ n (n-1)



Contoh 9. Buktikan bahwa rumus eksplisit yang didapat pada contoh 8 merupakan rumus yang benar. Penyelesaian: Dari contoh 8 didapat Sn = ½ n (n-1) Akan dibuktikan kebenaran rumus tersebut dengan induksi matematika. Basis: Akan dibuktikan kebenaran rumus untuk n = 1. Menurut rumus, untuk n = 1, S1 = ½ 1 (1-1) = 0 Menurut kondisi awal, S1 = 0. jadi terbukti rumus benar untuk n = 0. Induksi: Misalkan rumus benar untuk n = k. Jadi Sk = ½ k (k-1) Menurut persamaan rekurensi untuk n = k + 1, Sk+1 = S(k+1)-1 + ((k+1) -1) = Sk + (k) = ½ k (k-1) + k (hipotesa induk) = ½ k (k+1) = ½ (k+1) ((k+1)-1) Terbukti rumus benar untuk n = k + 1 Jadi rumus eksplisit untuk Sn benar untuk n ≥ 1.



Penyelesaian Relasi Rekurensi lewat Persamaan Karakteristik



Contoh 10. Tentukan apakah persamaan di bawah ini merupakan relasi rekurensi linier, linier dengan koefisien konstan atau homogen linier dengan koefisien konstan. Jika demikian tentukan derajatnya! a. an – 7 an-1 + 10 an-2 = 0 b. bk = bk-1 + bk-2 + bk-3 c. ck = 2 ck-2 d. dk = dk-12 + dk-2 e. ek = ek-1.ek-2 f. fk – 2 fk-1 + 1 =0 g. hk = -hk-1 + (k-1) hk-2



Penyelesaian: a. Relasi rekurensi homogen linier dengan koefisien konstan derajat 2. b. Relasi (b) dapat dinyatakan dengan bk – bk-1 – bk-2 – bk-3 = 0, yang merupakan relasi rekurensi homogen linier dengan koefisien konstan derajat 3. c. Relasi rekurensi homogen linier dengan koefisien konstan derajat 2. d. Bukan relasi rekurensi linier karena memuat suku kuadratis dk-12. e. Bukan relasi rekurensi linier karena memuat pergandaan suku (ek-1.ek-2) f. Relasi rekurensi linier dengan koefisien konstan derajat 1 (f(n) = -1) g. Relasi rekurensi linier dengan derajat 2 (koefisien tidak konstan)



b. Relasi Rekurensi Homogen Linier dengan Koefisien Konstan



Contoh 11. Selesaikan relasi rekurensi di bawah ini lewat persamaan karakteristiknya: a. an = 3 an-1 + 4 an-2 untuk n ≥ 2 dengan kondisi awal a0 = 1 dan a1 = 3. b. an – 3 an-1 + 3 an-2 – an-3 = 0 untuk n ≥ 3 dengan kondisi awal a0 = 1; a1 = 2 dan a2 = 4 c. an – 7 an-1 + 16 an-2 – 12 an-3 = 0 untuk n ≥ 3 dengan kondisi awal a0 = 1; a1 = 4 dan a2 = 8



Penyelesaian: a. Relasi rekurensi an - 3 an-1 + 4 an-2 = 0, merupakan relasi rekurensi homogen linier dengan koefisien konstan. Persamaan karakteristik yang sesuai adalah t2 – 3t – 4 = (t-4)(t+1) = 0 yang mempunyai akar-akar karakteristik α1 = 4 dan α2 = -1. karena semua akar-akarnya berbeda, maka penyelesaiannya adalah: an = c1 4n + c2 (-1)n Untuk menentukan c1 dan c2, digunakan kondisi awal: a0 = 1 sehingga 1 = c1 (4)0 + c2 (-1)0 = c1 + c2 a1 = 3 sehingga 3 = c1 (4)1 + c2 (-1)1 = 4 c1 – c2 Didapat sistem persamaan linier c1 + c2 = 1 dan 4c1 – c2 = 3 yang mempunyai penyelesaian c1 = 4/5 dan c2 = 1/5 Maka penyelesaian relasi rekurensi an - 3 an-1 + 4 an-2 = 0 adalah an = 4/5 (4)n + 1/5 (-1)n



Contoh 12. Suatu taruhan dilakukan dengan cara melempar koin seimbang. Seorang penjudi mempertaruhkan Rp 1.000,- dalam setiap kali permainan. Jika yang muncul adalah gambar maka ia menang Rp 1.000,- dan sebaliknya, ia akan kalah Rp 1.000,- jika yang muncul adalah angka. Penjudi tersebut akan berhenti bermain jika ia kehabisan uang, atau ia menang Rp M (dalam ribuan). M adalah bilangan bulat positif yang besarnya ditentukan sebelum ia mulai berjudi. Misalkan Pn adalah probabilitas penjudi akan kehabisan uang jika sebelum berjudi ia membawa uang sebanyak Rp n (dalam ribuan) a. Carilah rumus eksplisit untuk Pn b. Bagaimana penjudi harus menentukan M untuk meminimumkan kemungkinan kehabisan uang?



Penyelesaian: a. Jika suatu koin seimbang dilemparkan, maka kemungkinan munculnya angka sama dengan kemungkinan munculnya gambar P(angka) = P(gambar) = ½



Ini berarti bahwa kemungkinan menang (gambar) dan kalah (angka) juga sama. Jika penjudi mempunyai (k-1) ribu, maka setelah 1 kali permainan, ada 2 kemungkinan jumlah uang yang dimiliki penjudi tersebut: 1. Uang yang dimiliki = (k) ribu. Ini terjadi kalau penjudi tersebut menang/muncul gambar. Jika demikian, maka kemungkinan ia kehabisan uang = Pk. 2. Uang yang dimiliki = (k-2) ribu. Ini terjadi kalau penjudi tersebut kalah/muncul angka. Jika demikian maka kemungkinan ia kehabisan uang adalah Pk-2.



Untuk kedua kasus tsb, kemungkinan terjadinya sama, yaitu = ½. Didapat relasi rekurensi Pk-1 = ½ Pk + ½ Pk-2; 2 ≤ k ≤ M. Didapat Pk – 2Pk-1 + Pk-2 = 0 Persamaan karakteristik yang sesuai t2 – 2t + 1 = 0 yang mempunyai akar kembar α1 = α2 = 1. Penyelesaian relasi rekurensi adalah Pn = (c1 + c2n) 1n = c1 + c2n Kondisi awal:



Untuk n = 0, probabilitas ia akan kehabisan uang = 1. Jadi P0 = 1. Untuk n = M, probabilitas ia akan kehabisan uang = 0 karena jika uangnya = M, ia akan berhenti berjudi sehingga tidak akan kehabisan uang. Jadi PM = 0.



Dengan memasukkan kondisi-kondisi awal in ke relasi rekurensi, didapat: 1 = c1 + c2(0) atau c1 = 1 0 = c1 + c2 M = 1 + c2 M sehingga c2 = -1/M Relasi rekurensi yang sesuai adalah: Pn = 1 – n/M untuk sembarang bilangan bulat n dengan 0 ≤ n ≤ M. selanjutnya dibuktikan dengan induksi matematika. b. Agar penjudi kehabisan uang (Pn = 1), maka n/M haruslah = 0. ini terjadi kalau M sangat besar. Semakin besar target kemenangan yang dicapai supaya ia berhenti berjudi (M), semakin besar kemungkinannya ia akan kehabisan uang (Pn = 1). Jadi untuk meminimumkan kemungkinan kehabisan uang, M harus dibuat sedekat-dekatnya dengan n (uang yang dimiliki sebelum ia mulai berjudi).



c. Penyelesaian Total



f(n) (D,a: konstan)



Sifat Persamaan Karakteristik C(t)



Bentuk Penyelesaian Khusus



D an



a bukan akar persamaan karakteristik c(t) (c(a) ≠ 0)



P an



D an



a adalah akar persamaan karakteristik c(t) kelipatan m



P nm a n



D ns a n



a bukan akar persamaan karakteristik c(t) (c(a) ≠ 0)



(P0+P1n+…+Psns) an



D ns a n



a adalah akar persamaan karakteristik c(t) kelipatan m



(P0+P1n+…+Psns) nman



D ns



1 bukan akar persamaan karakteristik c(t) (c(1) ≠ 0)



P0+P1n+…+Psns



D ns



1 adalah akar persamaan karakteristik c(t) kelipatan m



(P0+P1n+…+Psns) nm



Contoh 13. Carilah penyelesaian total relasi rekurensi di bawah ini: a. an – 7 an-1 + 10 an-2 = 4n untuk n ≥ 2 dengan kondisi awal



a0 = 8 dan a1 = 36 b. an – 7 an-1 + 10 an-2 = 7.3n + 4n untuk n ≥ 2 c. an – 4 an-1 + 4 an-2 = 2n untuk n ≥ 2 d. an – 5 an-1 + 6 an-2 = n2 4n untuk n ≥ 2 e. an – 2 an-1 + an-2 = 5 + 3n untuk n ≥ 2



a. Relasi rekurensi homogennya adalah an – 7 an-1 + 10 an-2 = 0 Persamaan karakteristiknya t2 – 7t + 10 = 0 dengan akar-akar karakteristiknya adalah α1 = 2, α2 = 5. Penyelesaian homogen an = c1 2n + c5 5n Karena f(n) = 4n dan 4 bukan akar karakteristik, maka untuk mencari penyelesaian khusus dicoba bentuk ank = P (4)n. Penyelesaian khusus ini disubstitusikan ke relasi rekurensi awal.



Didapat: P 4n – 7 (P 4n-1) + 10 (P 4n-2) = 4n P 4n-2 (42 – 7.4 + 10) = 4n



P = -8



Penyelesaian khusus ank = -8 (4)n Penyelesaian total = penyelesaian homgen + penyelesaian khusus an = c1.2n + c2.5n – 8(4)n



Untuk mencari harga c1 dan c2, digunakan kondisi awal yang diberikan: a0 = 8 sehingga c1(2)0 + c2(5)0 – 8(4)0 8 = c1 + c2 – 8 16 = c1 + c2 a1 = 36 sehingga 36 = c1(2)1 + c2(5)1 – 8(4)1 36 = 2c1 + 5c2 – 32



68 = 2c1 + 5c2 Didapat sistem persamaan linier c1 + c2 = 16 dan 2c1 + 5c2 = 68 Yang bila diselesaikan akan menghasilkan c1 = 4 dan c2 = 12.



Jadi penyelesaian relasi rekurensi mula-mula adalah an = 4(2)n + 12(5)n – 8(4)n



Relasi Rekursif dalam Ilmu Komputer



2. Menggunakan struktur perulangan (looping). Contoh: untuk menghitung suku ke-n barisan Fibonacci yang memenuhi relasi Fn = Fn-1 + Fn-2 dengan F0 = 1 dan F1 = 1, maka dibuat struktur program sbb: Depan Tengah



:= :=



1 1



For i := 2 to n Akhir Depan Tengah {end For} Write (Akhir)



:= := :=



Depan + Tengah Tengah Akhir



3. Menggunakan prosedur atau fungsi yang dipanggil secara rekursif. Merupakan implementasi proses rekursif yang sesungguhnya dalam komputer. Relasi rekursif an dibuat dalam suatu prosedur/fungsi dengan n sebagai salah satu parameternya. Fungsi/prosedur ini secara rekursif memanggil dirinya sendiri dengan nilai parameter yang menurun. Jika barisan Fibonacci diselesaikan dengan cara ini, maka programnya adalah (dalam struktur pascal) sbb: Function Fib (n : Integer) : Integer; Begin If ((n=0) or (n=1)) Then Fib := 1 Else Fib := Fib (n-1) + Fib (n-2) End;



LATIHAN Dari buku