RELASI REKURENSI pada MATEMATIKA DESKRIT
Pengertian Relasi Rekurensi Matematika Diskrit
Relasi Rekurensi merupakan salah satu masalah dalam Matematika Diskrit. Sebuah relasi rekurensi mendefinisikan suku ke-n dari sebuah barisan secara tak langsung; untuk menghitung an, pertama-tama harus dihitung a0, a1, a3..., an-1. Salah satu permasalahan yang melibatkan relasi rekurensi adalah masalah Tower of Hanoi, yang selanjutnya akan dicari bentuk umum penyelesaiannya. Relasi rekurensi jgka akan membahas penyelesaian umum yang melibatkan persamaan linier homogen dengan koefisien konstan yang melibatkan persamaan karakteristik dengan 2 akar, yaitu (1) r1, r2 dua bilangan riil yang berbeda. (2) r1, r2 dua bilangan kompleks. (3) r1, r2 dua bilangan riil yang sama, selanjutnya r1 dan r2 akan disebut akar-akar karakteristik.
Himpunan Yang Didefinisikan Secara Rekursif
Langkah-langkah dalam mendefinisikan suatu himpunan secara rekursif:
- Langkah basis: Spesifikasi koleksi awal dari anggota
- Langkah rekursif: Mendefinisikan aturan konstruksi anggota baru dari anggota yang telah diketahui
Misalkan S didefinisikan secara rekursif oleh: 3 Î S, (x+y) Î S jika x Î S dan y Î S
Maka S adalah himpunan bilangan bulat positif yang habis dibagi 3.
Bukti:
Misalkan A himpunan yang beranggotakan semua bilangan bulat positif yang habis dibagi 3.
Untuk membuktikan bahwa A = S, harus ditunjukkan
A Í S dan S Í A.
Bagian I:
Akan dibuktikan A Í S, yaitu menunjukkan bahwa setiap bilangan bulat positif yang habis dibagi 3 ada di S (dengan menggunakan induksi matematika).
Misalkan P(n): proposisi “3n anggota S”.
1. Langkah basis: P(1) benar, karena 3 Î S.
2. Langkah induktif:
Asumsikan P(k) benar, yaitu 3k Î S.
Akan ditunjukkan P(k+1) juga benar, yaitu 3(k+1) Î S
Karena 3k Î S dan 3 Î S, berdasarkan definisi rekursif dari S, 3k+3 = 3(k+1) juga ada di S.
3. Konklusi:
Jadi, setiap bilangan bulat positif yang habis dibagi 3 ada di S.
Kesimpulan dari bagian I adalah A Í S.
Bagian II:
Akan ditunjukkan S Í A dengan menggunakan definisi rekursif dari S.
Langkah basis:
Akan ditunjukkan setiap anggota awal S ada di A.
Karena 3 habis dibagi 3 maka 3 Î A.
Langkah rekursif:
Akan ditunjukkan bahwa setiap bilangan bulat yang dibangun dengan mengunakan langkah rekursif juga merupakan anggota A, yaitu
(x+y) Î A jika x,y Î S (yang diasumsikan Î A).
Jika x dan y keduanya di A, maka 3 | x dan 3 | y. Akibatnya, 3 | (x + y).
Kesimpulan dari bagian II adalah S Í A.
Jadi, secara keseluruhan, berlaku A = S.
Relasi Rekurens
Relasi rekursif adalah suatu topik penting dan menarik dalam kombinatorik. Banyak permasalahan dalam matematika, khususnya kombinatorik dapat dimodelkan ke dalam bentuk relasi 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.
Barisan (sequence) a0, a1, a2, …, an dilambangkan dengan {an} Elemen barisan ke-n, yaitu an, dapat ditentukan dari suatu persamaan.
Bila persamaan yang mengekspresikan an dinyatakan secara rekursif dalam satu atau lebih term elemen sebelumnya, yaitu a0, a1, a2, …, an–1, maka persamaan tersebut dinamakan relasi rekurens.
Artikel Terkait : solusi-khusus-dari-relasi-rekurensi
Barisan (sequence) a0, a1, a2, …, an dilambangkan dengan {an} Elemen barisan ke-n, yaitu an, dapat ditentukan dari suatu persamaan.
Bila persamaan yang mengekspresikan an dinyatakan secara rekursif dalam satu atau lebih term elemen sebelumnya, yaitu a0, a1, a2, …, an–1, maka persamaan tersebut dinamakan relasi rekurens.
Artikel Terkait : solusi-khusus-dari-relasi-rekurensi
Contoh 2:
an = 2an–1 + 1
an = an–1 + 2an–2
an = 2an–1 – an–2
Kondisi awal (initial conditions) suatu barisan adalah satu atau lebih nilai yang diperlukan untuk memulai menghitung elemen-elemen selanjutnya.
an = 2an–1 + 1
an = an–1 + 2an–2
an = 2an–1 – an–2
Kondisi awal (initial conditions) suatu barisan adalah satu atau lebih nilai yang diperlukan untuk memulai menghitung elemen-elemen selanjutnya.
Contoh 3:
an = 2an–1 + 1; a0 = 1
an = an–1 + 2an–2 ; a0 = 1 dan a1 = 2
Karena relasi rekurens menyatakan definisi barisan secara rekursif, maka kondisi awal merupakan langkah basis pada definisi rekursif tersebut.
an = 2an–1 + 1; a0 = 1
an = an–1 + 2an–2 ; a0 = 1 dan a1 = 2
Karena relasi rekurens menyatakan definisi barisan secara rekursif, maka kondisi awal merupakan langkah basis pada definisi rekursif tersebut.
Contoh 4:
Barisan Fibonacci 0, 1, 1, 2, 3, 5, 8, 13, … dapat dinyatakan dengan relasi rekurens
fn = fn–1 + fn–2 ; f0 = 0 dan f1 = 1
Kondisi awal secara unik menentukan elemen-elemen barisan. Kondisi awal yang berbeda akan menghasilkan elemen-elemen barisan yang berbeda pula.
Solusi dari sebuah relasi rekurens adalah sebuah formula yang tidak melibatkan lagi term rekursif. Formula tersebut memenuhi relasi rekurens yang dimaksud.
Barisan Fibonacci 0, 1, 1, 2, 3, 5, 8, 13, … dapat dinyatakan dengan relasi rekurens
fn = fn–1 + fn–2 ; f0 = 0 dan f1 = 1
Kondisi awal secara unik menentukan elemen-elemen barisan. Kondisi awal yang berbeda akan menghasilkan elemen-elemen barisan yang berbeda pula.
Solusi dari sebuah relasi rekurens adalah sebuah formula yang tidak melibatkan lagi term rekursif. Formula tersebut memenuhi relasi rekurens yang dimaksud.
Contoh 5:
Misalkan {an} adalah barisan yang memenuhi relasi rekurens berikut:
an = 2an–1 – an–2 ; a0 = 1 dan a1 = 2
Periksa apakah an = 3n merupakan solusi relasi rekurens tersebut.
Penyelesaian:
2an–1 – an–2 = 2[3(n – 1)] – 3(n – 2)
= 6n – 6 – 3n + 6
= 3n = an
Jadi, an = 3n merupakan solusi dari relasi rekurens tersebut.
Apakah an = 2n merupakan solusi relasi rekurens an = 2an–1 – an–2 ; a0 = 1 dan a1 = 2?
Penyelesaian:
2an–1 – an–2 = 2×2n–1 – 2n–2
= 2n–1 + 1 – 2n–2
= 2n – 2n–2 ¹ 2n
Jadi, an = 2n bukan merupakan solusi relasi rekurens tsb.
Cara lain: Karena a0 = 1 dan a1 = 2, maka dapat dihitung
a2 = 2a1 – a0 = 2×2 – 1 = 3
Dari rumus an = 2n dapat dihitung a0 = 20 = 1,
a1 = 21 = 2, dan a2 = 22 = 4
Karena 3 ¹ 4, maka an = 2n bukan merupakan solusi dari relasi rekurens tsb.
Misalkan {an} adalah barisan yang memenuhi relasi rekurens berikut:
an = 2an–1 – an–2 ; a0 = 1 dan a1 = 2
Periksa apakah an = 3n merupakan solusi relasi rekurens tersebut.
Penyelesaian:
2an–1 – an–2 = 2[3(n – 1)] – 3(n – 2)
= 6n – 6 – 3n + 6
= 3n = an
Jadi, an = 3n merupakan solusi dari relasi rekurens tersebut.
Apakah an = 2n merupakan solusi relasi rekurens an = 2an–1 – an–2 ; a0 = 1 dan a1 = 2?
Penyelesaian:
2an–1 – an–2 = 2×2n–1 – 2n–2
= 2n–1 + 1 – 2n–2
= 2n – 2n–2 ¹ 2n
Jadi, an = 2n bukan merupakan solusi relasi rekurens tsb.
Cara lain: Karena a0 = 1 dan a1 = 2, maka dapat dihitung
a2 = 2a1 – a0 = 2×2 – 1 = 3
Dari rumus an = 2n dapat dihitung a0 = 20 = 1,
a1 = 21 = 2, dan a2 = 22 = 4
Karena 3 ¹ 4, maka an = 2n bukan merupakan solusi dari relasi rekurens tsb.
Metode Iterasi
Metode paling dasar dalam menentukan rumus eksplisit dari barisan yang didefinisikan secara rekursif adalah metode iterasi. Cara kerja iterasi seperti berikut: Diberikan barisan a0, a1, a2, … yang didefinisikan oleh relasi rekursif dan kondisi awalnya, kita akan menentukan beberapa suku awal dari barisan tersebut untuk melihat pola yang terbentuk. Jika kita sudah menemukan polanya, kita dapat menebak rumus eksplisit dari barisan tersebut.
Baca Juga :
Baca Juga :
matematika rekurensi itu apa
ReplyDeleteThanks gan
ReplyDelete