Relasi Rekursi. Matematika Informatika 4. Onggo

Relasi Rekursi Matematika Informatika 4 Onggo Wiryawan @OnggoWr

Definisi Definisi 1 • Suatu relasi rekursi untuk sebuah barisan {𝑎𝑛 } merupakan sebuah rumus untuk menyatakan 𝑎𝑛 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 rekursinya.

Contoh 1 Contoh 1 • Misal 𝑎𝑛 barisan yang memenuhi relasi rekursi 𝑎𝑛 = 𝑎𝑛−1 − 𝑎𝑛−2 untuk 𝑛 ≥ 2, lalu misalkan 𝑎0 = 3 dan 𝑎1 = 5. Tentukan nilai 𝑎2 dan 𝑎3 . Jawab • Karena 𝑎2 = 𝑎1 − 𝑎0 , maka 𝑎2 = 2. Karena 𝑎3 = 𝑎2 − 𝑎1 , maka 𝑎3 = −3. 

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

Contoh 2 (ii) Misal 𝑎𝑛 = 2𝑛 , untuk bilangan bulat nonnegatif 𝑛. Maka 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 𝑎𝑛 = 2 2 𝑛−1 − 2 𝑛−2 𝑎𝑛 = 2𝑛 − 2𝑛−2 𝑎𝑛 = 2𝑛 1 − 14 = 2𝑛 ∙ 34 ≠ 2𝑛 . Maka 𝑎𝑛 = 2𝑛 bukan merupakan solusi bagi relasi rekursi 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 .

Contoh 2 (iii) Misal 𝑎𝑛 = 5, untuk bilangan bulat nonnegatif 𝑛. Maka 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 𝑎𝑛 = 2 5 − 5 𝑎𝑛 = 5 • Maka 𝑎𝑛 = 5 merupakan solusi bagi relasi rekursi 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 .  Catatan: Kondisi awal 𝑎0 akan menentukan suku-suku pada barisan berikutnya.

Contoh 3 Contoh 3 • Tentukan barisan yang merupakan solusi dari relasi rekursi 𝑎𝑛 = 3𝑎𝑛−1 , jika diketahui 𝑎0 = 2. Jawab 𝑎𝑛 = 3𝑎𝑛−1 𝑎𝑛 = 3 3𝑎𝑛−2 = 32 ∙ 𝑎𝑛−2 𝑎𝑛 = 3 3 3𝑎𝑛−3 = 33 ∙ 𝑎𝑛−3 ⋮ 𝑎𝑛 = 3𝑛 ∙ 𝑎𝑛−𝑛 = 3𝑛 ∙ 𝑎0 𝑎𝑛 = 2 ∙ 3𝑛 • Sehingga barisan 𝑎𝑛 = 2 ∙ 3𝑛 merupakan solusi dari relasi rekursi 𝑎𝑛 = 3𝑎𝑛−1 dengan nilai awal 𝑎0 = 2.

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

Jenis-jenis Relasi Rekursi • Perhatikan tabel berikut ini: Relasi Rekursi 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 2 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 𝐻𝑛 = 2𝐻𝑛−1 + 1 𝑏𝑛 = 𝑛𝑏𝑛−1

Linier    

Homogen    

Koef. Konst.    

Degree 2 2 1 1

Menentukan Relasi Rekursi Linier Homogen dengan Koefisien Konstan

Contoh 1 • Tentukan solusi dari relasi rekursi 𝑎𝑛 = 𝑎𝑛−1 + 2𝑎𝑛−2 , dengan 𝑎0 = 2, dan 𝑎1 = 7. Jawab • Bentuk persamaan karakteristik dari relasi rekursi 𝑎𝑛 = 𝑎𝑛−1 + 2𝑎𝑛−2 . • Pindahkan semua suku ke ruas kiri. 𝑎𝑛 − 𝑎𝑛−1 − 2𝑎𝑛−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.


𝑎𝑛 − 𝑎𝑛−1 − 2𝑎𝑛−2 = 0 ↓ 𝑟 2 − 𝑟 − 2𝑟 0 = 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.


• Bentuk solusi umum dari relasi rekursi yang memiliki 2 akar berbeda adalah 𝑎𝑛 = 𝑐1 ∙ 𝑟1𝑛 + 𝑐2 ∙ 𝑟2𝑛

• Sehingga solusi umum dari relasi rekursi di atas adalah 𝑎𝑛 = 𝑐1 ∙ 2𝑛 + 𝑐2 ∙ −1 𝑛 • Untuk suatu 𝑐1 , 𝑐2 bilangan real.


• Untuk mendapatkan solusi khusus, gunakan nilai awal yang diketahui. 𝑎0 = 2 = 𝑐1 ∙ 20 + 𝑐2 ∙ −1 0 2 = 𝑐1 + 𝑐2 ... (1) 𝑎1 = 7 = 𝑐1 ∙ 21 + 𝑐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 𝑎𝑛 = 𝑎𝑛−1 + 2𝑎𝑛−2 adalah 𝑎𝑛 = 3 ∙ 2𝑛 − −1 𝑛 . 


Contoh 2 • Tentukan solusi dari relasi rekursi 𝑎𝑛 = 6𝑎𝑛−1 − 9𝑎𝑛−2 , dengan 𝑎0 = 1, dan 𝑎1 = 6. Jawab • Bentuk persamaan karakteristik dari relasi rekursi tersebut. 𝑎𝑛 = 6𝑎𝑛−1 − 9𝑎𝑛−2 ↓ 𝑎𝑛 − 6𝑎𝑛−1 + 9𝑎𝑛−2 = 0 ↓ 𝑟 2 − 6𝑟 + 9 = 0


• Persamaan karakteristik di atas memiliki akarakar karakteristik kembar yaitu 𝑟1 = 𝑟2 = 3. • Bentuk solusi umum dari relasi rekursi yang memiliki 2 akar kembar adalah 𝑎𝑛 = 𝑐1 ∙ 𝑟1𝑛 + 𝑐2 ∙ 𝑛𝑟1𝑛


• Sehingga solusi umum dari relasi rekursi di atas adalah 𝑎𝑛 = 𝑐1 ∙ 3𝑛 + 𝑐2 ∙ 𝑛 3 𝑛 • Untuk suatu 𝑐1 , 𝑐2 bilangan real. • Untuk mendapatkan solusi khusus, gunakan nilai awal yang diketahui. 𝑎0 = 1 = 𝑐1 ∙ 30 + 𝑐2 ∙ 0 −1 0 1 = 𝑐1 ... (1) 𝑎1 = 6 = 𝑐1 ∙ 31 + 𝑐2 ∙ 1 3 1 6 = 3𝑐1 + 3𝑐2 ... (2)


• Persamaan (1) dan (2) dapat diselesaikan dengan metode substitusi/eliminasi untuk mendapatkan 𝑐1 = 1 dan 𝑐2 = 1. • Sehingga solusi khusus dari relasi rekursi 𝑎𝑛 = 6𝑎𝑛−1 − 9𝑎𝑛−2 adalah 𝑎𝑛 = 3𝑛 + 𝑛 ∙ 3𝑛 . 


Contoh 3 • Tentukan solusi dari relasi rekursi 𝑎𝑛 = 6𝑎𝑛−1 − 11𝑎𝑛−2 + 6𝑎𝑛−3 , dengan 𝑎0 = 2, 𝑎1 = 5 dan 𝑎2 = 15. Jawab • Bentuk persamaan karakteristik dari relasi rekursi tersebut. 𝑎𝑛 = 6𝑎𝑛−1 − 11𝑎𝑛−2 + 6𝑎𝑛−3 ↓ 𝑎𝑛 − 6𝑎𝑛−1 + 11𝑎𝑛−2 − 6𝑎𝑛−3 = 0 ↓ 𝑟 3 − 6𝑟 2 + 11𝑟 − 6 = 0


• Persamaan karakteristik di atas memiliki akar-akar karakteristik berbeda yaitu 𝑟1 = 1, 𝑟2 = 2 dan 𝑟3 = 3. • Bentuk solusi umum dari relasi rekursi yang memiliki 3 akar berbeda adalah 𝑎𝑛 = 𝑐1 ∙ 𝑟1𝑛 + 𝑐2 ∙ 𝑟2𝑛 + 𝑐3 ∙ 𝑟3𝑛

• Sehingga solusi umum dari relasi rekursi di atas adalah 𝑎𝑛 = 𝑐1 ∙ 1𝑛 + 𝑐2 ∙ 2𝑛 + 𝑐3 ∙ 3𝑛 • Untuk suatu 𝑐1 , 𝑐2 , 𝑐3 bilangan real.


• Untuk mendapatkan solusi khusus, gunakan nilai awal yang diketahui. 𝑎0 = 2 = 𝑐1 + 𝑐2 + 𝑐3 𝑎1 = 5 = 𝑐1 + 2𝑐2 + 3𝑐3 𝑎2 = 15 = 𝑐1 + 4𝑐2 + 9𝑐3 • 3 persamaan di atas dapat diselesaikan dengan metode substitusi/eliminasi untuk mendapatkan 𝑐1 = 1, 𝑐2 = −1 dan 𝑐3 = 2. • Sehingga solusi khusus dari relasi rekursi 𝑎𝑛 = 6𝑎𝑛−1 − 11𝑎𝑛−2 + 6𝑎𝑛−3 adalah 𝑎𝑛 = 1 − 2𝑛 + 2 ∙ 3𝑛 . 

Latihan Latihan Tentukan solusi khusus dari relasi-relasi rekursi berikut ini. 1. 𝑎𝑛 = 2𝑎𝑛−1 , 𝑎0 = 3 2. 𝑎𝑛 = 5𝑎𝑛−1 − 6𝑎𝑛−2 , 𝑎0 = 1, 𝑎1 = 0 3. 𝑎𝑛 = 4𝑎𝑛−1 − 4𝑎𝑛−2 , 𝑎0 = 6, 𝑎1 = 8 4. 𝑎𝑛 = 4𝑎𝑛−2 , 𝑎0 = 0, 𝑎1 = 4 5. 𝑎𝑛 = 2𝑎𝑛−1 + 𝑎𝑛−2 − 2𝑎𝑛−3 , 𝑎0 = 3, 𝑎1 = 6 dan 𝑎2 = 0 6. 𝑎𝑛 = 2𝑎𝑛−1 + 5𝑎𝑛−2 − 6𝑎𝑛−3 , 𝑎0 = 7, 𝑎1 = −4 dan 𝑎2 = 8

Relasi Rekursi. Matematika Informatika 4. Onggo

Recommend Documents