Menyelesaikan Relasi Rekursif dengan Iterasi

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,

Barisan Menara Hanoi

dan barisan bunga majemuk akan memenuhi rumus,

Barisan Bunga Majemuk

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 barisan a0, 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,

Contoh 1 Barisan

Gunakan metode iterasi untuk menebak rumus eksplisit dari barisan tersebut.

Pembahasan Perhatikan bahwa relasi rekursif,

Contoh 1 Relasi Rekursif

berarti

Contoh 1 Bentuk Lain RR

berapapun bilangan bulat positif yang disubstitusikan ke kotak □. Secara lebih khusus,

Contoh 1 Tiga Suku Pertama

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.

Contoh 1 Lima Suku Pertama

Karena akan lebih membantu jika kita menuliskan k ∙ 2 untuk menggantikan 2 + 2 + … + 2 (k kali), maka kita lakukan hal tersebut dimulai dari a0.

Contoh 1 Menentukan an

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,
Barisan Aritmetika I
Akibat langsungnya adalah,
Barisan Aritmetika II

Iklan

Tentang Yosep Dwi Kristanto

Tahun 2012 memulai blogging untuk menyediakan sumber belajar matematika online, yang semoga dapat memberikan kontribusi bagi pendidikan di Indonesia. Pengagum pendekatan kontekstual dalam proses pembelajaran.
Pos ini dipublikasikan di Matematika Diskrit, Topik Matematika dan tag , , , , , , . Tandai permalink.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s