ELOMPOK 4
RELASI
REKURSIF
ANGGOTA
M. YUSUF ARDINAL MASHA (1305622023)
LIZA RACHELYA (1305622044)
LEILA AULIA YASMIN (1305622059)
ALDONA WIJAYANTHI (1305622061)
VINATA ANGGRAENI (1305622069)
AUDREY SYAHADA MAULIA (1305622075)
PENGERTIAN
Relasi rekursif adalah persamaan yang secara
rekursif mendefinisikan barisan yang sukunya
ditentukan oleh satu atau beberapa suku sebelumnya.
CONTOH RELASI
REKURSIF LINEAR
BILANGAN FIBONACCI BARISAN PADOVAN
F1 = F2 = 1 F1 = F2 = F3= 1
FN = FN-1 + FN-2 FN= F N-2+ FN-3
2
2
5 3
1 1 1
7
8
1 1 4 5
3
2
BILANGAN PELL BILANGAN PELL-LUCAS
F1 = 0 F1 = 0
F2= 1 F2= 2
FN = 2FN-1 + FN-2 FN = 2FN-1 + FN-2
2 6
5 1 1 5 14 2 2 14
2 6
JENIS-JENIS RELASI
REKURSIF
LINEAR HOMOGEN
TIDAK ADA SUKU YANG DIPANGKATKAN HASIL PENJUMLAHAN DARI SUKU
ATAU DIKALIKAN DENGAN SUKU LAIN PERTAMA HINGGA SUKU KE-N SAMA
FN = 2FN-1 + 1 DENGAN NOL
FN = FN-1 + FN-2 F1 + F2 + F3 + ... + FN = 0
NON-LINEAR NON-HOMOGEN
ADA SUKU YANG DIPANGKATKAN ATAU
HASIL PENJUMLAHAN DARI SUKU
DIKALIKAN DENGAN SUKU LAIN
PERTAMA HINGGA SUKU KE-N TIDAK
FN = FN-1 FN-2 SAMA DENGAN NOL
FN = (FN-1 ) - 1
2
F1 + F2 + F3 + ... + FN =/ 0
KOEFISIEN KONSTANTA KOEFISIEN BUKAN
SETIAP SUKU MEMILIKI KONSTANTA KONSTANTA
TETAP SEBAGAI KOEFISIENNYA KOEFISIEN DARI BEBERAPA SUKU DAPAT
FN = 2FN-1 BERUBAH
FN = FN-1 + FN-2 FN = NFN-1
RELASI REKURSIF LINEAR
DENGAN KOEFISIEN
KONSTANTA
Dari jenis-jenis relasi rekursif Hasil penjumlahan dari semua suku
tersebut, dapat disimpulkan bahwa pada relasi rekursif
relasi rekursif linear dengan
f(n) = F 1 + F2 + F 3+ ... + Fn
koefisien konstanta memiliki sifat
jika f(n) = 0, maka relasi rekursif
linear dan memiliki konstanta tetap
tersebut homogen
sebagai koefiesien dari setiap
sukunya
≠
jika f(n) 0, maka relasi
rekursif tersebut non-homogen
Bentuk umum relasi rekursif linear
dengan koefisien konstanta
berderajat k
Fn = A1F n-1 + A2 Fn-2 + A 3Fn-3 + ...
+ A k Fn-k
A = Konstanta
TEOREMA 3.2.1
(Prinsip Superposisi)
Relasi Rekursif Linear Homogen Dengan Koefisien Konstanta
Jika g 1(n) dan g2(n) berturut-turut adalah solusi dari:
a n + c 1 a n-1 + c 2 a n-2 + ... c k a n-k = f 1 (n)
dan
a n + c 1 a n-1 + c 2 a n-2 + ... c k a n-k = f 2 (n)
maka untuk sebarang konstanta b1 dan b 2 ,
b 1 g 1 (n) + b 2 g 2 (n)
adalah solusi dari
a n+ c 1a n-1+ ... c k a n-k = b 1 f 1 (n) + b 2 f2 (n)
TEOREMA 3.2.2
PENYELESAIAN MENGGUNAKAN
PERSAMAAN KARAKTERISTIK
Persamaan Fn = A 1 Fn-1 + A 2 Fn-2 + A3 Fn-3 + ... + A k Fn-k
Memiliki bentuk karakteristik polinomial x - A 1 x - A 2 x - A 3 x - ... - Ak x
n n-1 n-2 n-3 n-k
=0
Yang memiliki akar-akar karakteristik x 1 , x 2 , x3 , ... , x k
Yang sedemikian sehingga Fn = b1 x1n + b 2 x 2n+ b3 x3n + ... + bk xnk
Untuk suatu b1 , b 2 , b3 , ... , bk
Jika ada beberapa akar yang sama, maka semua akar
tersebut tetap ditulis
Contoh soal
Temukan solusi dari relasi rekursif Fn = 5Fn-1 - 6Fn-2
_ 3, F1 = 1, dan F2 = 4
Dimana n >
Jawab :
Buat persamaan karakteristik Buat persamaan F baru
A1 = 5 x 2 - 5x + 6 = 0 Fn = b1 x1+ b2 x2
A 2 = -6 Fn = b1 2n + b2 3 n
Mencari akar karakteristik
2
x - 5x + 6 = 0 x1 = 2
(x-2)(x-3) = 0 x =32
Contoh soal
Substitusi F dan F ke persamaan baru
1 1 2 2
F1 = b 1 2 + b2 3 F2 = b 1 2 + b2 3
1 = 2b1 + 3b2 4 = 4b 1 + 9b2
Dari sistem persamaan tersebut diperoleh
_ 1
__ 2
__
b1 = dan b2 =
2 3
Sehigga solusi dari sistem relasi tersebut adalah
_ 1
__ n 2
__ n
Fn = (2 ) + (3 )
2 3
TEOREMA 3.2.3
Jika persamaan karakterisik dari relasi rekursif mempunyai akar, x1
katakan, rangkap m ≤k, maka solusi umum yang melibatkan x1
mempunyai bentuk:
dengan c0, c1, c2, ..., cm-1 adalah sembarang konstanta.
LATIHAN SOAL
1
2 a n = 4a n-1 - 3a n-2 untuk n >
adalah
_ 2 dengan nilai awal a 0 = 5 dan a 1 = 8. Nilai dari a 5
3
LATIHAN SOAL
4
6
THANK YOU