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

Video ini membahas definisi relasi rekurens dalam matematika diskrit, di mana relasi rekurens untuk barisan a, n adalah formula yang mengekspresikan a, n berdasarkan term sebelumnya. Barisan tersebut disebut sebagai solusi dari relasi rekurens jika termnya memenuhi relasi yang diberikan. Contohnya, untuk mencari nilai a2 dan a3 dari barisan dengan nilai awal a0=3 dan a1=5, kita gunakan rumus a, n = a, n-1 - a, n-2. Dengan demikian, melalui perhitungan berurutan, kita dapat menentukan nilai-nilai berikutnya dalam barisan tersebut.

Sebelumnya kita sudah bahas ide mengenai relasi recurrence.

Sekarang kita lihat definisi formalnya seperti apa.

Jadi sebuah relasi recurrence untuk barisan a, n adalah formula yang mengekspresikan a, n dalam satu atau lebih term sebelumnya pada barisan tersebut.

Jadi ada a0, a1, a2 sampai an-1 untuk semua bilangan bulat n dengan n lebih besar sama dengan n0 dimana n0 adalah bilangan bulat tidak negatif.

Nah barisan ini akan disebut sebagai solusi dari relasi recurrence jika termnya memenuhi relasi recurrence.

Jadi masing-masing itu akan memenuhi relasi recurrence yang sudah diberikan.

Jadi misalnya kalau a, n itu barisan yang memenuhi relasi recurrence a, n sama dengan a, n-1, min a, n-2.

Kalau yang sebelumnya itu a, n-1 plus a, n-2 untuk yang Fibonacci.

Kalau sekarang misalnya a, n itu sama dengan a, n-1, min a, n-2 untuk n-nya 2, 3, 4 dan seterusnya.

Dan misalkan kita berikan satu nilai awal a0-nya 3, a1-nya 5, terus berapa sih nilai a2 dan a3?

Nah nilai a2 di sini kita gunakan rumusnya yaitu a, n sama dengan a, n-1, min a, n-3.

Jadi kalau kita mau cari a2 berarti n-nya 2 akan sama dengan a1-a0.

Kita tahu bahwa a1 tadi sama dengan 5 dikasih nilai awalnya dan a0 sama dengan 3 maka ini 5-3 sama dengan 2.

Untuk a3-nya berarti di sini n-nya 3 maka a, n-1-nya adalah a2 dikurang a, n-2-nya itu sama dengan a1.

Kita lihat di sini bahwa untuk mencari a3 itu kita harus tahu a2 dulu.

Kalau a2-nya kita belum tahu maka kita tidak bisa mendapatkan nilai a3 dan juga nilai a, n yang lebih besar.

Kita kembali ke a3, a3 itu sama dengan a2 dikurang a1.

Jadi a2 tadi sudah kita hitung nilainya 2 kemudian a1 kita kembali ke nilai awalnya yaitu 5 jadi kita akan dapat nilai a-3.

Dan kita selanjutnya bisa mencari a4, a5 dan seterusnya.