Selamat datang, Kali ini kita akan berbagi tentang Penggunaan Iterasi dalam Penyelesaian Relasi Rekursif. Silahkan dibaca baik-baik tentang Penggunaan Iterasi dalam Penyelesaian Relasi Rekursif ini ya.
Misalkan kita memiliki suatu barisan yang memenuhi relasi rekursif dan kondisi awal tertentu. Akan sangat membantu apabila kita mengetahui rumus eksplisit dari barisan tersebut, khususnya jika kita diminta untuk menentukan suku dengan indeks yang sangat besar atau jika kita diminta untuk menguji sifat-sifat dari barisan tersebut. Rumus eksplisit yang seperti itu disebut sebagai selesaian dari relasi rekursif. Sebagai contoh, pada pembahasan ini kita akan menunjukkan bahwa barisan Menara Hanoi akan memenuhi rumus,
dan barisan bunga majemuk akan memenuhi rumus,
Barisan-barisan Menara Hanoi dan bunga majemuk merupakan 2 dari 3 contoh yang disajikan pada pembahasan relasi rekursif sebelumnya.
Metode Iterasi
Metode paling dasar dalam menentukan rumus eksplisit dari barisan yang didefinisikan secara rekursif adalah metode iterasi. Cara kerja iterasi seperti berikut: Diberikan barisana0, a1, a2, … yang didefinisikan oleh relasi rekursif dan kondisi awalnya, kita akan menentukan beberapa suku awal dari barisan tersebut untuk melihat pola yang terbentuk. Jika kita sudah menemukan polanya, kita dapat menebak rumus eksplisit dari barisan tersebut.
Contoh 1: Menentukan Rumus Eksplisit
Misalkan a0, a1, a2, … merupakan barisan yang didefinisikan secara rekursif sebagai berikut: Untuk setiap bilangan bulat k ≥ 1,
Gunakan metode iterasi untuk menebak rumus eksplisit dari barisan tersebut.
Pembahasan Perhatikan bahwa relasi rekursif,
berarti
berapapun bilangan bulat positif yang disubstitusikan ke kotak □. Secara lebih khusus,
dan seterusnya. Sekarang kita gunakan kondisi awal untuk memulai proses substitusi pada persamaan-persamaan tersebut. Tetapi, selain substitusi bilangan, kita juga akan menuliskan ekspresi numerik di dalamnya.
Alasan mengapa kita juga perlu menuliskan ekspresi numeriknya adalah agar kita menemukan pola yang ada dalam barisan tersebut. Dalam menuliskan ekspresi numerik tersebut sebaiknya kita melakukan penyingkatan notasi pada penjumlahan, pengurangan, atau perkalian yang berulang. Sehingga, sebagai contoh, kita sebaiknya menuliskan 5 ∙ 2 daripada 2 + 2 + 2 + 2 + 2 dan 25 daripada 2 ∙ 2 ∙ 2 ∙ 2 ∙ 2. Sebagai catatan, kita tidak akan kehilangan informasi apapun mengenai pola bilangan ketika kita menggunakan notasi tersebut.
Berikut ini proses yang kita gunakan untuk menentukan pola dari barisan di atas.
Karena akan lebih membantu jika kita menuliskan k ∙ 2 untuk menggantikan 2 + 2 + … + 2 (k kali), maka kita lakukan hal tersebut dimulai dari a0.
Jawaban di atas hanyalah suatu dugaan. Untuk menguji kebenaran dari dugaan di atas kita dapat mengujinya dengan menggunakan induksi matematika.
Barisan seperti pada contoh 1 di atas, yang masing-masing sukunya sama dengan suku sebelumnya ditambah dengan suatu konstanta tertentu, disebut barisan aritmetika.
Definisi Barisan Aritmetika
Suatu barisan a0, a1, a2, … disebut barisan aritmetika jika dan hanya jika ada suatu konstanta b sedemikian sehingga,
Akibat langsungnya adalah,
No comments:
Post a Comment