Relasi Rekursi *recurrence – rekurens – rekursi – perulangan.
Kata kunci: definisi, relasi rekursi linier berkoefisien konstan, solusi relasi rekurensi, dan solusi homogen & partikelir • • • •
menuliskan definisi dari relasi rekursi memberikan sebuah contoh bentuk dari relasi rekursi menyebutkan jenis-jenis relasi rekursi menjelaskan barisan Fibonacci sebagai salah satu contoh relasi rekursi.
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 sukusuku pada barisan tersebut memenuhi relasi rekursinya. 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 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 Relasi Rekursi – @OnggoWr – 2013
1/7
𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 𝑎𝑛 = 2(3(𝑛 − 1)) − 3(𝑛 − 2) 𝑎𝑛 = 3𝑛. Maka 𝑎𝑛 = 3𝑛 merupakan solusi bagi relasi rekursi 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 . (ii) Misal 𝑎𝑛 = 2𝑛 , untuk bilangan bulat nonnegatif 𝑛. Maka 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 𝑎𝑛 = 2(2(𝑛−1) ) − 2(𝑛−2) 𝑎𝑛 = 2𝑛 − 2𝑛−2 1
3
𝑎𝑛 = 2𝑛 (1 − 4) = 2𝑛 ∙ 4 ≠ 2𝑛 . Maka 𝑎𝑛 = 2𝑛 bukan merupakan solusi bagi relasi rekursi 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−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 Tentukan barisan yang merupakan solusi dari relasi rekursi 𝑎𝑛 = 3𝑎𝑛−1 , jika diketahui 𝑎0 = 2. Jawab 𝑎𝑛 = 3𝑎𝑛−1 𝑎𝑛 = 3(3𝑎𝑛−2 ) = 32 ∙ 𝑎𝑛−2 Relasi Rekursi – @OnggoWr – 2013
2/7
𝑎𝑛 = 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. Perhatikan tabel berikut ini: Relasi Rekursi 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 2 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 𝐻𝑛 = 2𝐻𝑛−1 + 1 𝑏𝑛 = 𝑛𝑏𝑛−1
Linier
Relasi Rekursi – @OnggoWr – 2013
Homogen Koef. Konst. Degree 2 2 1 1
3/7
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.
Relasi Rekursi – @OnggoWr – 2013
4/7
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 akar-akar karakteristik kembar yaitu 𝑟1 = 𝑟2 = 3. Bentuk solusi umum dari relasi rekursi yang memiliki 2 akar kembar adalah 𝑎𝑛 = 𝑐1 ∙ 𝑟1𝑛 + 𝑐2 ∙ 𝑛𝑟1𝑛
Relasi Rekursi – @OnggoWr – 2013
5/7
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
Relasi Rekursi – @OnggoWr – 2013
6/7
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 Tentukan solusi khusus dari relasi-relasi rekursi berikut ini. 1. 2. 3. 4. 5. 6.
𝑎𝑛 𝑎𝑛 𝑎𝑛 𝑎𝑛 𝑎𝑛 𝑎𝑛
= 2𝑎𝑛−1 , 𝑎0 = 3 = 5𝑎𝑛−1 − 6𝑎𝑛−2 , 𝑎0 = 1, 𝑎1 = 0 = 4𝑎𝑛−1 − 4𝑎𝑛−2 , 𝑎0 = 6, 𝑎1 = 8 = 4𝑎𝑛−2 , 𝑎0 = 0, 𝑎1 = 4 = 2𝑎𝑛−1 + 𝑎𝑛−2 − 2𝑎𝑛−3 , 𝑎0 = 3, 𝑎1 = 6 dan 𝑎2 = 0 = 2𝑎𝑛−1 + 5𝑎𝑛−2 − 6𝑎𝑛−3 , 𝑎0 = 7, 𝑎1 = −4 dan 𝑎2 = 8
Relasi Rekursi – @OnggoWr – 2013
7/7
