Relasi Rekursif kelompok 5 tugas kuliah.pptx

Relasi Rekursif kelompok 5 tugas kuliah.

1. Relasi Rekursif Oleh kelompok V Febriani D. Maima Meirlin Y. Pandie Melan M.T.Nomeni Migel G. Mangngi Pedro Litelnoni Sonya G. Bangngu Yasinta Chr. Boleng Yeremia Kolan Yesri Jesika Teikuar

2. Definisi 1 Relasi rekursif berasal dari 2 kata yaitu relasi dan rekursif . Relasi berarti hubungan atau keterkaitan , sedangkan rekursif adalah pengulangan . Sehingga dapat disimpulkan bahwa relasi rekursif adalah hubungan yang berulang • Suatu relasi rekursi untuk sebuah barisan { 𝑎 n } merupakan sebuah rumus untuk menyatakan 𝑎 n ke dalam satu atau lebih suku-suku sebelumnya dari barisan tersebut , untuk suatu bilangan bulat nonnegatif 𝑛. • Suatu barisan disebut solusi dari sebuah relasi rekursi jika suku-suku pada barisan tersebut memenuhi relasi rekursin ya .

3. Contoh 1 Contoh 1 Misal {𝑎 n } barisan yang memenuhi relasi rekursi 𝑎 n =𝑎 n-1 − 𝑎 n-2 untuk 𝑛≥2, lalu misalkan 𝑎 =3 dan 𝑎 1 =5 . Tentukan nilai 𝑎 2 dan 𝑎 3 . Jawab Karena 𝑎 2 =𝑎 1 −𝑎 , maka 𝑎 2 =2 . Karena 𝑎 3 =𝑎 2 −𝑎 1 , maka 𝑎 3 = −3.

4. Contoh 2 • Untuk bilangan bulat nonnegatif 𝑛, apakah barisan 𝑎 n =3 𝑛, 𝑎 n =5 merupakan solusi bagi relasi rekursi 𝑎 n =2𝑎 n-1 −𝑎 n-2 ? Jawab ( i ) Misal 𝑎 n =3 𝑛, untuk bilangan bulat nonnegatif 𝑛. Maka : 𝑎 n =2𝑎 n-1 −𝑎 n-2 𝑎 n =2(3(𝑛 − 1))−3(𝑛 − 2) 𝑎 n =3 𝑛. Maka 𝑎 n =3 𝑛 merupakan solusi bagi relasi rekursi 𝑎 n =2𝑎 n-1 −𝑎 n-2 .

5. ( ii) Misal 𝑎 n =5 , untuk bilangan bulat nonnegatif 𝑛. Maka 𝑎 n =2𝑎 n-1 −𝑎 n-2 𝑎 n =2(5)− 5 𝑎 n =5 Maka 𝑎 n =5 merupakan solusi bagi relasi rekursi 𝑎 n =2𝑎 n-1 −𝑎 n-2 .

6. Jenis-jenis relasi rekursi Definisi 2 Suatu relasi rekursi linier homogen berderajat 𝑘 dengan koefisien konstan memiliki bentuk umum : 𝑎 n =𝑐 1 𝑎 n-1 +𝑐 2 𝑎 n-2 + ⋯+ 𝑐 k 𝑎 n-k dengan 𝑐 1 ,𝑐 2 ,…,𝑐 k adalah bilangan real, dan 𝑐 k ≠ 0.

7. Jenis-jenis relasi rekursi

8. Bila nilai f(n) = 0, maka diperoleh relasi rekurensi yang memenuhi : C a n + C 1 a n-1 + C 2 a n-2 + … + C k a n-k = 0. Relasi rekurensi demikian disebut dengan relasi rekurensi homogen dan solusi dari relasi rekurensi homogen ini dinamakan solusi homogen atau jawab homogen .

9. 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 .

10. Menentukan Relasi Rekursi Linier Homogen dengan Koefisien Konstan Contoh 1 Tentukan solusi dari relasi rekursi 𝑎 n =𝑎 n-1 +2𝑎 n-2 , dengan 𝑎 =2 , dan 𝑎 1 =7 . Jawab • Bentuk persamaan karakteristik dari relasi rekursi 𝑎 n =𝑎 n-1 +2𝑎 n-2 . Pindahkan semua suku ke ruas kiri . 𝑎 n −𝑎 n-1 − 2 𝑎 n-2 =0 Karena relasi di atas memiliki derajat 2, maka bentuk polinomial derajat 2 yang bersesuaian dengan masing-masing suku dari relasi tersebut , perhatikan setiap koefisien dan tanda tiap suku .

11. 𝑎 n −𝑎 n-1 − 2 𝑎 n-2 =0 ↓ 𝑟 2 − 𝑟−2 𝑟 =0 𝑟 2 − 𝑟−2=0 Persamaan di atas disebut persamaan karakteristik , dan memiliki 2 akar berbeda yaitu 𝑟 1 =2 dan 𝑟 2 = −1 yang disebut akar-akar karakteristik . Menentukan Relasi Rekursi Linier Homogen dengan Koefisien Konstan

12. Bentuk solusi umum dari relasi rekursi yangmemiliki 2 akar berbeda adalah 𝑎 n =𝑐 1 ∙r1 𝑛 + 𝑐 2 ∙r2 n Sehingga solusi umum dari relasi rekursi di atas adalah 𝑎 n =𝑐 1 ∙ 2𝑛+ 𝑐 2 ∙(−1) n Untuk suatu 𝑐 1 ,𝑐 2 bilangan real. Menentukan Relasi Rekursi Linier Homogen dengan Koefisien Konstan

13. Untuk mendapatkan solusi khusus , gunakan nilai awal yang diketahui . 𝑎 =2 = 𝑐 1 ∙2 +𝑐 2 ∙(−1) 2 = 𝑐 1 +𝑐 2 ... (1 ) 𝑎1=7= 𝑐 1 ∙2 1 +𝑐 2 ∙(−1) 1 7=2 𝑐1−𝑐2 ... (2) Persamaan (1) dan (2) dapat diselesaikan dengan metode substitusi/eliminasi untuk mendapatkan 𝑐 1 =3 dan 𝑐 2 = −1. Sehingga solusi khusus dari relasi rekursi 𝑎 n =𝑎 n-1 +2𝑎 n-2 adalah 𝑎 n =3 ∙ 2 n −(−1) n. Menentukan Relasi Rekursi Linier Homogen dengan Koefisien Konstan

14. Menyelesaikan Relasi rekrusif dengan Fungsi Pembangkit Contoh Gunakan fungsi pembangkit biasa untuk menyelesaikan relasi rekursif berikut . 𝑎 =1, 𝑎 1 =3; 𝑎 n =2𝑎 n-1 + 4 n-1 ,n 2. Penyelesaian :