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

Video ini membahas teknik perhitungan lanjutan dalam matematika diskrit, khususnya mengenai relasi rekurens dengan koefisien konstan. Untuk menyelesaikan relasi rekurens linear homogen dengan koefisien konstan, langkah dasarnya adalah dengan mengasumsikan solusi sebagai pangkat n untuk suatu konstanta R. Selanjutnya, dilakukan substitusi solusi ke dalam persamaan dan diperoleh persamaan karakteristik. Teorema yang disebutkan menjelaskan solusi untuk relasi rekurens dengan dua suku, seperti dalam kasus relasi Fibonacci dengan nilai awal F0=0 dan F1=1. Dengan menggunakan metode ini, solusi untuk barisan Fibonacci dapat ditemukan dengan akar persamaan karakteristik R2-R-1=0.

Bagaimana untuk menyelesaikan relasi recurrence ini?

Ada beberapa relasi recurrence yang ada metodenya untuk menyelesaikannya.

Jadi contohnya untuk relasi recurrence linear homogen dengan koefisien yang konstan.

Caranya yang paling dasar untuk mencari solusinya adalah

kita misalkan a n itu sama dengan pangkat n untuk R suatu konstanta.

Jadi dia diasumsikan merupakan solusi dari relasi recurrence-nya.

Langkah berikutnya adalah karena dia merupakan solusi

maka kita bisa substitusikan ke dalam persamaan

a n sama dengan C1 a n-1 plus C2 a n-2 sampai Ck a n-k

jika dan hanya jika R pangkat n itu sama dengan C1 kali R pangkat n-1

ditambah C2 kali R pangkat n-2 sampai Ck kali R pangkat n-k

karena itu si a n-nya disubstitusi dengan R pangkat n

jadi a n-1 disubstitusi dengan R pangkat n-1

dan a n-k disubstitusi dengan R pangkat n-k.

Karena semuanya ini pangkat dari R itu lebih besar dari n-k

maka kita bisa bagi seluruh suku-suku dari persamaan ini dengan R pangkat n-k

kemudian seluruh persamaan yang kita pindahkan sebelah kiri

maka kita akan dapat persamaan R pangkat k dikurangi dari persamaan yang disebelah kanan tadi

yaitu C1 R pangkat k-1 ditambah C2 R pangkat k-2 sampai Ck

karena yang suku terakhir kan sudah dibagi R pangkat n-k itu dapatnya 1

nah itu sama dengan 0 karena yang tadi yang di sisi kanan itu kita pindah semua ke kiri tinggal 0

ini kita sebut sebagai persamaan karakteristik

kalau kita punya R pangkat n tadi diasumsikan menjadi a n

maka kalau ini persamaan karakteristiknya itu ada solusinya

maka dia akan menjadi solusi juga untuk barisan a n-nya tadi

atau solusi dari relasi recurrence linear homogene dengan koefisien konstan

untuk rangkumannya dari apa yang tadi kita bahas itu ada di teorema

yaitu teoremanya di sini hanya untuk 2 suku

jadi misalkan kita punya C1 dan C2 itu bilangan real

kita punya R kuadrat min C1 R min C2 sama dengan 0 itu memiliki 2 akar yang berbeda R1 dan R2

maka barisan a n adalah solusi dari relasi recurrence a n sama dengan C1 a n min 1 ditambah C2 a n min 2

jika dan hanya jika a n itu sama dengan alpha 1 kali R1 pangkat n ditambah alpha 2 kali R2 pangkat n

untuk n-nya mulai dari 0 1 2 dan seterusnya dan alpha 1 alpha 2 adalah konstanta

ini teoremanya memang bagian kecil dari apa yang sebelumnya kita bahas karena di sini hanya ada 2 suku

sekarang kalau kita lihat untuk relasi recurrence yang menyatakan barisan Fibonacci tadi

kita akan lihat nilai awalnya kan F0 nya 0 F1 nya 1

untuk mencari solusi ini kita masukkan si Fn itu akan sama dengan R pangkat n

jadi nanti kita akan dapatkan kita substitusikan ya kepersamaan aslinya

kita dapatkan R pangkat n sama dengan R pangkat n min 1 ditambah R pangkat n min 2

nah ini semua sukunya kita bagi dengan R pangkat n min 2

kita akan dapat R2 ini sama dengan R ditambah 1

kemudian suku yang kanan itu kita pindahkan ke kiri

nanti kita akan dapat persamaan R2 min R min 1 sama dengan 0

nah sekarang si R ini dicari solusinya dari persamaan R2 min R min 1 sama dengan 0

kita bisa tahu bahwa R1 nya nanti kita dapat 1 plus akar 5 per 2

dan R2 nya itu akan sama dengan 1 min akar 5 per 2

jadi ini adalah solusi dari si barisan Fibonacci Fn sama dengan Fn min 1 plus Fn min 2