Matematika Diskrit : Penyelesaian Relasi Rekurensi dengan Iterasi

Penyelesaian dengan Iterasi

Prinsipnya, dihitung suku-suku barisan secara berurutan terus menerus sehingga diperoleh suatu pola tertentu.

Misalnya

Contoh 1:

Misalkan uang sebanyak Rp10.000 disimpan di bank dengan sistem bunga berbunga dengan besar bunga 11% per tahun. Berapa banyak uang setelah 30 tahun?

Penyelesaian

Misalkan P_n menyatakan nilai uang setalah n tahun.

Nilai uang setelah n tahun sama dengan nilai uang tahun sebelumnya ditambah dengan bunga uang
P_n = P_n–1 + 0,11 P_n–1
P₀ = 10.000

Jadi, P_n= (1,11)ⁿ P₀ = 10.000 (1,11)ⁿ
Setelah 30 tahun, banyaknya uang adalah P₃₀ = 10.000 (1,11)³⁰ = Rp228.922,9

Contoh 2:

Misalkan K_n adalah graf dengan n buah titik dan setiap pasang titik dihubungkan dengan sebuah garis (Graf Lengkap).

Jika S_n menyatakan jumlah garis dalam K_n, maka:

1. Buktikan bahwa S_n memenuhi relasi rekurensi S_n = S_n-1 + (n-1) dan kondisi awal S₁ = 0
2. Selesaikan relasi rekurensi S_n tersebut

Penyelesaian
1. K_n untuk n = 1, 2, 3, 4, dan 5

Banyaknya garis dalam K₄ adalah banyaknya garis K₃ ditambah dengan banyaknya garis baru yang harus dibuat akibat penambahan satu buah titik.

Banyaknya garis baru yang ditambahkan pada K₄ sama dengan banyaknya titik pada K₃.

Jadi S₄ = S₃ + 3.

Secara umum, S_n = S_n-1 + (n-1)
Kondisi awal S₁ = 0 jelas benar karena tidak mungkin membuat garis dari satu buah titik.

2. S_n = S_n-1 + (n-1)

= (S_n-2 + (n-2)) + (n-1) = S_n-2 + (n-2) + (n-1)

= (S_n-3 + (n-3)) + (n-2) + (n-1) = S_n-3 + (n-3) + (n-2) + (n-1)

= …

= S_n-(n-1) + (n-(n-1)) + …+ (n-3) + (n-2) + (n-1)

= S₁ + 1 + 2 + … + (n-2) + (n-1)

Karena S₁ = 0 maka S_n = 1 + 2 + … + (n-2) + (n-1) = ½ n (n-1)

Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Matematika Diskrit – Rekursi, daftar lengkapnya adalah sebagai berikut.

Tonton juga video pilihan dari kami berikut ini