RELASI REKURSIF
Isnaini Rosyida, Emi Pudjiastuti, Mulyono
UNNES-2018
Relasi Rekursif
■
■ Definisi
1. Relasi Rekursif untuk barisan didefinisikan sebagai sebuah persamaan yang
menyatakan dalam salah satu atau lebih suku-suku sebelumnya, yaitu , untuk semua
dengan dengan bilangan bulat tak negatif. Selanjutnya, barisan dikatakan sebagai solusi
dari relasi rekursif ini bila memenuhi relasi rekursif.
■ Contoh 11.
■ Misal barisan memenuhi relasi rekursif untuk Serta diberikan nilai awal: dan . Diperoleh:
■ Dan seterusnya. Jelas bahwa mengaitkan dua suku sebelumnya.
Relasi Rekursif
■
■ Apakah
barisan dengan merupakan solusi dari relasi rekursif
untuk
dengan n bilangan bulat tak negatif?
Penyelesaian: Dengan mensubtitusi ke ruas kanan relasi rekursif, diperoleh:
Dapat dibuktikan bahwa memenuhi relasi rekursif.
Jadi merupakan solusi dari relasi rekursif.
■ Bagaimana dengan barisan dengan ? Apakah barisan ini merupakan solusi
dari relasi rekursif
untuk
Penyelesaian: Dengan mensubtitusi ke ruas kanan relasi rekursif, diperoleh:
Dapat dibuktikan bahwa tidak memenuhi relasi rekursif.
■ adi bukan solusi dari relasi rekursif.
Relasi Rekursif
■
■ Contoh 2.
■ Barisan Fibonacci: Sepasang kelinci diletakkan di sebuah pulau.
Pasangan kelinci ini tidak akan beranak sampai berumur 2 bulan,
Setelah 2 bulan, setiap pasang kelinci akan menghasilkan sepasang
kelinci lainnya setiap bulan. Misal menyatakan banyaknya pasangan
kelinci setelah bulan, relasi rekursif untuk barisan adalah
Relasi Rekursif
■ Definisi
5. Bentuk umum relasi rekursif linear homogen
berderajat dengan koefisien-koefisien konstan sebagai berikut:
(3)
dengan bilangan-bilangan real dan .
■ Untuk lebih memahami bentuk relasi rekursif linear homogen
berderajat dengan koefisien konstan, diperhatikan contoh
berikut ini.
1. , merupakan relasi rekursif linear homogen berderajat 1
2. , merupakan relasi rekursif linear homogen berderajat 2
3. , merupakan relasi rekursif linear homogen
berderajat 3
4. , merupakan relasi rekursif linear homogen berderajat 4.
Relasi Rekursif
■
Langkah untuk menentukan solusi relasi rekursif
homogen linear adalah dengan mensubtitusi bentuk
dengan konstanta. Bentuk solusi dari relasi
rekursif (3) jika dan hanya jika memenuhi relasi
rekursif (3). Dengan cara mensubtitusi ke relasi
rekursif (3), diperoleh persamaan karakteristik
sebagai berikut:
dan akar dari persamaan tersebut di atas disebut
akar-akar karakteristik.
Relasi Rekursif
■
■ Beberapa
teorema yang dapat digunakan untuk
menentukan bentuk solusi homogen relasi rekursif linear
homogen berderajat disajikan berikut ini.
■ Teorema 1. Misal bilangan real dan persamaan
mempunyai dua akar berbeda dan . Barisan solusi dari
relasi rekursif jika dan hanya jika
dengan dan konstanta.
Relasi Rekursif
■
■ Jika
akar karakteristik dari relasi rekursif (3) berderajat 2
merupakan akar rangkap 2, dapat digunakan Teorema 2
untuk menentukan bentuk solusinya.
■ Teorema 2. Misal bilangan real dan persamaan
mempunyai satu akar (rangkap) . Barisan solusi dari
relasi rekursif jika dan hanya jika
dengan dan konstanta.
Relasi Rekursif
■
Bentuk solusi homogen dari relasi rekursif (3)
berderajat-k dengan semua akar karakteristik
berbeda, dapat ditentukan berdasarkan Teorema 3.
■ Teorema 3. Misal bilangan real dan persamaan
mempunyai akar berbeda . Barisan solusi dari
relasi rekursif jika dan hanya jika
■ dengan konstanta.
Relasi Rekursif
■ Bentuk solusi homogen dari relasi rekursif (3) berderajat-k
dengan akar karakteristik rangkap, dapat ditentukan berdasarkan
Teorema 4.
■ Teorema 4. Misal bilangan real dan persamaan mempunyai
mempunyai akar berbeda dengan multiplisitas dengan . Barisan
solusi dari relasi rekursif jika dan hanya jika
dengan dan konstanta untuk dan .
Relasi Rekursif
■
Contoh
3
■ Tentukan solusi dari relasi rekursif dengan kondisi awal
Penyelesaian. Langkah pertama, ditentukan persamaan karakteristik dengan
mensubtitusi
dengan konstanta:
Diperoleh akar-akar persamaan karakteristik: dan
Dengan demikian, bentuk solusinya sebagai berikut: .
Dengan kondisi awal yang diberikan, diperoleh
Dari tiga persamaan di atas, diperoleh solusi homogen:
Relasi Rekursif
■
Contoh
4
■ Tentukan solusi dari relasi rekursif dengan kondisi awal
Penyelesaian. Langkah pertama, ditentukan persamaan karakteristik dengan
mensubtitusi
dengan konstanta:
Diperoleh akar-akar persamaan karakteristik: dgn multiplisitas 3.
Dengan demikian, bentuk solusinya sebagai berikut:
.
Dengan kondisi awal yang diberikan, diperoleh
,
Diperoleh:
Dengan subtitusi nilai kedua persamaan terakhir, diperoleh solusi homogen
soal
■ Kerjakan dengan tuntas soal-soal berikut ini.
1. Tentukan solusi relasi rekursif: dengan
.
2. Tentukan solusi relasi rekursif: dengan dan