Relasi rekurensi adalah hubungan matematis yang mendefinisikan elemen-elemen suatu deret atau urutan berdasarkan elemen-elemen sebelumnya. Dalam matematika diskrit, relasi rekurensi sering digunakan untuk memodelkan masalah yang melibatkan pengulangan atau pemrosesan berulang, seperti dalam algoritma, teori graf, dan struktur data.
Secara umum, relasi rekurensi sangat penting untuk memahami pola dan perilaku dari urutan-urutan yang dapat didefinisikan secara berulang. Dengan menggunakan relasi ini, kita bisa memprediksi nilai elemen-elemen yang jauh di dalam suatu urutan tanpa perlu menghitung semuanya secara manual.
Secara umum, relasi rekurensi didefinisikan sebagai:
$a_n=f(a_{n−1},a_{n−2},\dots,a_{n−k})$
Di sini, $a_n$ adalah suku ke-$n$ dalam suatu urutan, dan $f$ adalah fungsi yang menghubungkan suku sebelumnya. Untuk dapat memecahkan relasi rekurensi ini, diperlukan kondisi awal yang memberikan nilai awal urutan tersebut.
Contoh Relasi Rekurensi
- Deret Fibonacci: Salah satu contoh relasi rekurensi yang terkenal adalah deret Fibonacci, yang didefinisikan sebagai:
$F_n=F_{n−1}+F_{n−2}$
dengan kondisi awal $F_0=0$ dan $F_1=1$.
Relasi ini digunakan untuk menghitung suku-suku selanjutnya dalam deret Fibonacci. - Relasi Linear Homogen:
Sebuah relasi rekurensi linear homogen adalah relasi yang hanya melibatkan suku-suku sebelumnya tanpa ada tambahan konstanta. Contohnya:
$a_n=2a_{n-1}-a_{n-2}$.
dengan kondisi awal $a_0=1$ dan $a_1=2$.
Solusi dari relasi ini dapat ditemukan dengan metode karakteristik.
Klasifikasi Relasi Rekurensi
Relasi rekurensi dapat diklasifikasikan berdasarkan sifatnya:
1. Relasi Linear Homogen:
Sebuah relasi rekurensi linear homogen adalah relasi yang berbentuk:
$$a_n=c_1a_{n−1}+c_2a_{n−2}+\dots+c_ka_{n−k}$$
dengan $c_1,c_2,\dots,c_k$ adalah konstanta. Solusi untuk jenis relasi ini biasanya dicari dengan metode karakteristik.
2. Relasi Linear Non-Homogen:
Dalam relasi rekurensi linear non-homogen, terdapat tambahan suku yang bukan merupakan kombinasi linear dari suku-suku sebelumnya. Bentuk umum dari relasi ini adalah:
$$a_n=c_1a_{n−1}+c_2a_{n−2}+\dots+c_ka_{n−k}+f(n)$$
dimana $f(n)$ adalah fungsi tertentu. Untuk menyelesaikannya, kita perlu menggunakan metode khusus seperti metode undetermined coefficients atau substitusi.
3. Relasi Non-Linear
Jika relasi tidak linier, misalnya jika melibatkan kuadrat atau eksponensial dari suku sebelumnya, maka penyelesaiannya bisa lebih kompleks dan sering memerlukan metode iteratif atau numerik.