Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas teorema 4 relasi rekurens linear pada Matematika Diskrit dengan judul "Teknik Perhitungan Lanjutan". Teorema tersebut menjelaskan cara menyelesaikan persamaan karakteristik dengan akar berbeda R1, R2, hingga Rt serta pengali M1, M2, hingga Mt. Dalam kasus solusi relasi rekurens An = C1An-1 + C2An-2 + ... + CkAn-K, nilai An tergantung pada Rt nilai yang berbeda. Contoh penerapan teorema diberikan untuk relasi An = 3An-1 + 3An-2 + An-3 dengan nilai awal A0 = 1, A1 = -2, dan A2 = 1. Dengan mengganti An = R^N, persamaan karakteristiknya adalah R^3 + 3R^2 + 3R + 1, yang menghasilkan solusi An = A10(-1)^N + A11N + A12N^2. Solusi ini dapat dicari dengan menggantikan nilai awal yang diberikan.

Sekarang bagaimana kalau persamaan karakteristiknya punya akar yang sama ada beberapa, jadi bukan hanya satu.

Jadi misalkan disini kita punya C1 sampai Ck bilangan real, misalkan persamaan karakteristik R pangkat K dikurang C1 kali R pangkat K min 1,

kurang C2 R pangkat K min 2, dikurang sampai Ck itu sama dengan 0, ini berasal dari sebelah kanan dipindah ke kiri,

itu memiliki T akar berbeda R1, R2, Rt dengan pengali masing-masing M1, M2, Mt.

Jadi R1 itu kita peroleh berulang M1 kali, R2 berulang M2 kali, kemudian Rt berulang Mt kali.

Kalau dia tidak berulang, jadi nilainya beda itu berarti M1, M2, M3 sampai Mt itu satu semua untuk kasus ini.

Nah sekarang karena Mi itu adalah ulangan tadi, berarti M1 ditambah M2 sampai Mt itu harus sama dengan K,

tidak boleh ada yang penamanya lebih atau kurang dari ini.

Nah barisan An adalah solusi dari relasi recurrence An sama dengan C1 kali An min 1 ditambah C2 An min 2 sampai Ck An min K,

jika dan hanya jika si An itu nilainya, kan kita punya ada Rt nilai yang berbeda,

jadi untuk yang pertama dia berulang M1 kali sehingga suku pertama koefisien dari R1 pangkat N adalah

Alfa 1 0 ditambah Alfa 1 1 N ditambah Alfa 1 2 N kwadrat sampai A1 M1 min 1 N pangkat M1 min 1 dikali dengan R1 pangkat N.

Suku yang kedua serupa, di sini akarnya R2 pangkat N koefisiennya adalah Alfa 2 0 ditambah Alfa 2 1 N ditambah sampai Alfa 2 M2 min 1 dikali N pangkat M2 min 1 R2 pangkat N.

Ini ditambah terus sampai koefisiennya untuk Rt pangkat N, ininya sama.

Kalau diperhatikan di sini untuk koefisien dari akar yang pertama misalnya R1 pangkat N,

kita lihat di kasus yang sebelumnya di mana R1 sama dengan R2,

ini An nya itu akan sama dengan Alfa 0 ditambah Alfa 1 N,

Alfa 0 kali R pangkat N ditambah Alfa 1 kali N R pangkat N.

Karena di sini dia M1 kali berarti di sini ada Alfa 1 0 ditambah Alfa 1 1 N ditambah Alfa 1 2 N kwadrat ditambah sampai Alfa 1 M1 min N kali N pangkat M1 min 1.

Jadi itu kenapa tiba-tiba ada tambahan N untuk mengantisipasi kelipatannya tadi.

Kita coba contohnya di sini ada relasi recurrence An sama dengan min 3 An min 1 min 3 An min 2 min An min 3.

Di sini diberikan A0 nya 1, A1 nya min 2 dan A2 nya sama dengan min 1, ini nilai awalnya.

Sekarang halnya sama, An nya kita berikan sama dengan R pangkat N,

substitusikan kepersamaan nya kemudian cari persamaan karakteristiknya.

Dalam hal ini persamaan karakteristiknya adalah R pangkat 3 ditambah 3 R kwadrat ditambah 3 R plus 1.

Kalau kita cari akarnya nanti kita dapat akar R sama dengan min 1 3 kali,

maka kita akan peroleh An nya sama dengan A10 kali min 1 pangkat N ditambah A11, ini yang kedua.

Jadi A11 kali N ini karena dia kelipatan kedua kali min 1 pangkat N terus kemudian A12 di sini N kwadrat karena itu yang ketiga.

Ini contohnya yang mudah, jadi hanya dia sama tapi yang samanya itu cuma satu tapi kelipatannya tiga.

Terus kita substitusi untuk kalau mau cari A10, A11 dan A12 nya itu kita masukkan A0 sama dengan 1, A1 sama dengan min 2, A1 sama dengan min 2 dan A2 sama dengan min 1.

Nanti kita akan peroleh A10nya 1, A11nya 3 dan A12nya sama dengan min 2.

Jadi An nya akan sama dengan 1 ditambah 3 N ditambah 2 N kwadrat dikali min 1 pangkat N.

Kalau misalnya ada R sama dengan min 1 nya berulang 3 kali, kalau misalnya ada R2 nya lagi yang kedua tapi beda,

ini nanti akan kombinasi dengan yang sebelumnya karena anggap saja dia juga berulang tapi M nya itu satu.

Jadi nanti kita cuma keluarnya nanti ada alfa 2 0 saja kalau ada.

Itu tadi bagaimana kita mencari solusi dari relasi recurrence tapi yang homogen.