Untuk menyelesaikan relasi rekurensi, terdapat beberapa metode yang sering digunakan:
- Metode Iterasi: Dalam metode ini, kita menghitung suku-suku urutan secara bertahap, dimulai dari kondisi awal, hingga menemukan pola yang dapat dinyatakan sebagai fungsi eksplisit.
- Metode Karakteristik: Untuk relasi linear homogen, kita dapat menggunakan metode karakteristik. Langkah pertama adalah menulis persamaan karakteristik:
$$r_n=c_1r_{n−1}+c_2r_{n−2}+⋯+c_kr_{n−k}r^{n-k}$$ dengan $r$ sebagai akar dari persamaan karakteristik. Solusi umum akan bergantung pada apakah akar tersebut unik atau berulang. - Metode Undetermined Coefficients: Untuk relasi non-homogen, metode ini melibatkan asumsi solusi khusus yang memiliki bentuk mirip dengan suku non-homogen $f(n)$, kemudian menentukan koefisien yang tidak diketahui dengan substitusi.
Contoh Penyelesaian Relasi Rekurensi
Berikut ini adalah contoh bagaimana menyelesaikan relasi rekurensi linear homogen:
Soal: Diberikan relasi rekurensi $a_n=3a_{n−1}−2a_{n−2}$ dengan kondisi awal $a_0=2$ dan $a_1=3$. Temukan solusi umumnya.
Langkah Penyelesaian:
- Tuliskan persamaan karakteristik: $r^2−3r+2=0$
- Temukan akar-akar persamaan: $r=1,2$
- Solusi umum untuk relasi ini adalah:
$$a_n=C_1 1^n+C_2 2^n=C1+C2 2^n$$ - Substitusikan kondisi awal $a_0=2 dan $a_1 = 3$ untuk menemukan nilai $C_1$ dan $C_2$. Dari $a_0=2$, kita dapatkan: $C_1 + C_2 = 2$