Download - Matematika Diskrit Relasi Rekursif
Relasi RekursifOleh:
Adhitya Himawan (4111412014)
Rahmad Ramadhon (4111412019)
Hengky Tri Ikhsanto (4111412025)
Ayuk Wulandari (4111412026)
Pengantar
Relasi rekursif untuk barisan (an) adalah persamaan yang menyatakan an
dalam salah satu atau lebih bentuk a0, a1, β¦, an-1 untuk semua n dengan n n0
dimana n0 bilangan bulat non-negatif.
contoh.
Apakah barisan (ππ) dimana ππ=3n, dengan n bilangan bulat non-negatif,
merupakan solusi dari an = 2an-1 - an-2 untuk n = 2, 3, 4, β¦ ?
Bagaimana dengan barisan an = 2n dan an =5 ?
Relasi rekursif homogen linear berderajat k
dengan koefisien konstan
Bentuk umum:
an = c1 an-1 + c2 an-2 + β¦ + ck an-k,
dengan c1, c2, β¦, ck bilangan real dan ck 0.
Contoh.
1. Pn = 12Pn-1
2. fn = fn-1 + fn-2
3. Hn = 2Hn-1 + 1
4. an = an-1 + (ππβ2)2
5. Tn = nTn-2
Contoh 1,2 merupakan relasi rekursif homogen linear sedangkan 3,4,5 merupakan
relasi tak homogen linear.
Solusi Relasi Rekursif
Langkah dasar dalam memecahkan relasi rekursif homogen linear berderajad k dengan koefisien konstan adalah mencari solusi dalam bentuk an = rn dengan rkonstan.
an = rn adalah solusi dari
an = c1 an-1 + c2 an-2 + β¦ + ck an-k
jika dan hanya jika
rn = c1 rn-1 +c2 r
n-2 + β¦ + ck rn-k.
Bila kedua ruas dibagi dengan rn-k diperoleh:
rk - c1 rk-1 - c2 r
k-2 - β¦ - ck-1 r - ck = 0.
Persamaan ini disebut persamaan karakteristik dari relasi rekursif. Solusidari persamaan ini disebut akar karakteristik.
Teorema 1
Misalkan c1, c2 bilangan real dan r2 - c1r - c2 = 0 mempunyai dua akar
berbeda r1 dan r2.
Maka semua solusi dari relasi rekursif
an = c1 an-1 + c2 an-2
berbentuk
an = 1r1n + 2r2
n, n=0,1,2,β¦
dengan 1 dan 2 konstan.
Contoh
Carilah solusi dari an = an-1 + 2an-2 dengan a0 = 2 dan a1 =7.
Solusi.
Persamaan karakteristiknya
r2 - r - 2 = 0,
mempunyai akar r = 2 dan r = -1.
Menurut Teorema 1, solusi relasi rekursif berbentuk
an= 1 2n + 2 (-1)n .
Karena a0= 2 dan a1= 7, diperoleh
an = 32n - (-1)n .
Teorema 2
Misalkan c1, c2 bilangan real dengan c2 0 dan r2 - c1r - c2 = 0 mempunyai
hanya satu akar r0.
Maka semua solusi dari relasi rekursif
an = c1 an-1 + c2 an-2
berbentuk
an = 1 r0n + 2 nr0
n, n=0,1,2,β¦
dengan 1 dan 2 konstan.
Contoh
Tentukan solusi dari relasi rekursif an = 6an-1- 9an-2 dengan kondisi awal a0 = 1 dan a1 = 6.
Solusi.
Dari soal dapat diketahui bahwa Persamaan karakteristiknya adalah : r2 β 6r + 9 = 0.
Akar-akarnya: (r β 3)(r β 3 ) = 0 r1 = r2 = 3 r0
an = 1rn0 + 2nrn
0 an = 13n + 2n3n
a0 = 1 a0 = 1 = 130 + 2 030 = 1
a1 = 6 a1 = 6 = 131 + 213
1 = 31 + 32
Diperoleh dua persamaan: 1 = 1 dan 31 + 32 = 6,
solusinya adalah 1 = 1 dan 2 = 1
menurut teorema 2 diperoleh:
Jadi, solusi relasi rekursif adalah:
an = 3n + n3n
Teorema 3
Misalkan c1, c2, β¦, ck bilangan real dan persamaan karakteristik
rk - c1 rk-1 - c2 r
k-2 - β¦ - ck-1 r - ck = 0, mempunyai k akar r1, r2, β¦, rk yang berbeda.
Maka, solusi relasi rekursif
an = c1an-1 + c2an-2 + β¦ + ckan-k
selalu berbentuk
an = 1r1n + 2r2
n + β¦ + krkn , n=0,1,2,β¦
dengan i , i=0,1,β¦,k konstan.
Contoh.Tentukan solusi dari relasi rekursif an = 6an-1 β 11an-2 + 6an-3 dengan kondisi awal
a0=2, a1=5 dan a2=15.
Solusi:
Persamaan karakteristiknya
r3 - 6r2 + 11r - 6 = 0.
Jadi akar-akarnya r=1, r=2 dan r=3.
Dengan demikian, menurut teorema 3 solusinya berbentuk:
an = 11n + 22
n + k3n .
Dari kondisi awalnya diperoleh:
an = 1 - 2n + 2 3n .
Teorema 4
Misal c1, c2, β¦, ck bilangan real dan persamaan karakteristik
rk - c1 rk-1 - c2 r
k-2 - β¦ - ck-1 r - ck = 0
mempunyai t akar r1, r2, β¦ , rt berbeda dengan multiplisitas m1, m2, β¦ , mt
(m1+m2 + β¦ + mt = k).
Maka solusi relasi rekursif
an = c1 an-1 + c2 an-2 + β¦ + ck an-k
selalu berbentuk
an = (0 + 1n + 2n2 + β¦ + m1-1 nm1-1)r1
n
+ (0 + 1n + 2n2 β¦ + m2-1 nm2-1)r2
n
+ β¦ + (0 + 1n + β¦ + mt-1 nmt-1)rtn
ContohTentukan solusi dari relasi rekursif
an = -3an-1 - 3an-2 - an-3 dengan kondisi awal a0 = 1, a1 = -2 dan a2 = -1.
Solusi:
Persamaan karakteristiknya
r3 + 3r2 + 3r +1 = 0.
Jadi akarnya r = -1 dgn multiplisitas 3.
Dengan demikian, menurut teorema 4 solusinya berbentuk:
an = 1,0 (-1)n + 1,1 n (-1)n + 1,2 n2 (-1)n .
Dengan memandang kondisi awalnya diperoleh
an = (1 +3n-2n2) (-1)n.
Silahkan Dikerjakan.
1. Tentukan formula eksplisit dari bilangan Fibonacci dengan kondisi awal f0=1,
f1=1.
2. Selesaikan relasi rekurens berikut: an = 2anβ1 ; a0 = 3.
3. Selesaikan relasi rekurens berikut: an = 5anβ1 β 6anβ2 ; a0 = 1 dan a1 = 0.
Penyelesaian1. Jelas bahwa bilangan Fibonacci fn memenuhi relasi fn = fn-1 + fn-2. Dengan kondisi
awal f0=1, f1=1. Dari dari relasi tersebut dapat diidentifikasikan persamaan karakteristknya yaitu: π2 β π β 1 = 0.
Dari persamaan karakteristik tersebut dapat diketahui akar-akar karakteristiknya yaitu
π1 =1+ 5
2, π2 =
1β 5
2.
Maka diperoleh solusi relasi rekursif berbentuk:ππ = π1π1π + π2π2
π =
π1(1+ 5
2)π+π2(
1β 5
2)π.
Dari kondisi awal maka diperoleh:
π11 + 5
2+ π2
1 β 5
2= 1
π1(1 + 5
2)2+π2(
1 β 5
2)2= 1
Dari kedua persamaan tersebut dapat diketahui nilai π1 =5
5πππ π2 = β
5
5.
Lalu disubstitusikan ke ππ, maka diperoleh solusi khususnya:
ππ =5
5(1+ 5
2)πβ
5
5(1β 5
2)π.
3. Jelas an = 5anβ1 β 6anβ2 ; a0 = 1 dan a1 = 0.
Maka dapat diketahui bahwa persamaan karakteristiknya adalah π2 β 5π + 6 = 0.
Dari persamaan tersebut dapat diketahui bahwa akar karakteristiknya adalah:
π1 = 6 πππ π2 = β1.
Jelas solusi relasi rekursif berbentuk: ππ = π1π1π + π2π2
π = π16π + π2(β1)
π.
Dari kondisi awal diperoleh:
π1 + π2 = 16π1 β π2 = 0
Dari kedua persamaan tersebut dapat diketahui nilai π1 =1
7πππ π2 =
6
7.
Kedua nilai tersebut dimasukkan ke ππ, maka solusi khususnya adalah:
ππ =6π
7+6(β1)π
7=6π + 6(β1)π
7
4. Selesaikan relasi rekurensi di bawah ini lewat persamaan karakteristiknya:
a. an = 3 an-1 + 4 an-2 untuk n β₯ 2 dengan kondisi awal
a0 = 1 dan a1 = 3.
b. an + 9 an-2 = 0 untuk n β₯ 2 dengan kondisi awal
a0 = 1 dan a1 = 4.
c. 2 an -2 an-1 +1
2an-2 = 0 untuk n β₯ 2 dengan kondisi awal
a0 = 6 dan a1 = 8.
d. an + 6 an-1 + 9 an-2 = 0 untuk n β₯ 2 dengan kondisi awal
a0 = 1 dan a1 = 3.
e. an β 3 an-1 + 3 an-2 β an-3 = 0 untuk n β₯ 3 dengan kondisi awal
a0 = 1; a1 = 2 dan a2 = 4
a. an = 3 an-1 + 4 an-2 untuk n β₯ 2 dengan kondisi awal
a0 = 1 dan a1 = 3.
Penyelesaian:
an = 3 an-1 + 4 an-2
β an - 3 an-1 - 4 an-2 = 0
Kita cari akar β akarnya
r2 β 3r β 4 = 0
(r β 4) atau (r + 1) = 0
Maka r1 = 4, r2 = -1 dengan penyelesaian menurut teorema 1, solusi relasi rekursifnya berbentuk:
an = Ξ±1(4)n + Ξ±2(-1)n ...(*)
karena a0= 1 dan a1 = 3 kita subtitusikan kepersamaan (*)
a0= 1 menjadi a0 = 1 = Ξ±1 (4)0 + Ξ±2 (-1)0 = Ξ±1 +Ξ±2 ...(1)
a1= 3 menjadi a1 = 3 = Ξ±1 (4)1 + Ξ±2 (-1)1 = 4Ξ±1 - Ξ±2 ...(2)
kita eliminasi persamaan (1) dan persamaan (2) untuk mencari nilai Ξ±1 dan Ξ±2.
Ξ±1 +Ξ±2 = 1
4Ξ±1 - Ξ±2 = 3 +
5Ξ±1 = 1
Ξ±1= 4/5
subtitusikan kepersamaan (1) diperoleh:
Ξ±1 + Ξ±2 = 1 β 4/5 + Ξ±2 = 1
Ξ±2 = 1 β 4/5
Ξ±2 = 1/5
maka penyelesaian relasi rekursifnya an - 3 an-1 - 4 an-2 = 0 adalah
an = Ξ±(4)n + Ξ±(-1)n
an = 4/5 (4)n + 1/5 (-1)n
b. an + 9 an-2 = 0 untuk n β₯ 2 dengan kondisi awal
a0 = 1 dan a1 = 4.
Penyelesaian:
an + 9 an-2 = 0
Kita cari akar β akarnya yaitu:
r2 + 9 = 0
β r2 = -9
β r = Β± 3
Maka akar - akarnya r1 = 3, r2 = -3 dengan penyelesaian menurut teorema 1, solusi relasi rekursifnya berbentuk:
an = Ξ±1(3)n + Ξ±2(-3)n ...(*)
karena a0= 1 dan a1 = 4 kita subtitusikan kepersamaan (*)
a0= 1 menjadi a0 = 1 = Ξ±1 (3)0 + Ξ±2 (-3)0 = Ξ±1 +Ξ±2 ...(1)
a1= 4 menjadi a1 = 4 = Ξ±1 (3)1 + Ξ±2 (-3)1 = 3Ξ±1 - 3Ξ±2 ...(2)
kita eliminasi persamaan (1) dan persamaan (2) untuk mencari nilai Ξ±1 dan Ξ±2.
Ξ±1 +Ξ±2 = 1 x 3 3Ξ±1 +3Ξ±2 = 3
3Ξ±1 - 3Ξ±2 = 4 + x 1 3Ξ±1 - 3Ξ±2 = 4 +
6Ξ±1 = 7
Ξ±1= 7/6
subtitusikan kepersamaan (1) diperoleh:
Ξ±1 + Ξ±2 = 1 β 7/6 + Ξ±2 = 1
Ξ±2 = 1 β 7/6
Ξ±2 = - 1/6
maka penyelesaian relasi rekursifnya an + 9 an-2 = 0 adalah
an = Ξ±(3)n + Ξ±(-3)n
an = 7/6 (3)n β 1/6 (-3)n
c. 2 an -2 an-1 +1
2an-2 = 0 untuk n β₯ 2 dengan kondisi awal
a0 = 6 dan a1 = 8.
Penyelesaian:
2 an -2 an-1 +1
2an-2 = 0
β 4 an β 4 an-1 + an-2 = 0
Kita cari akar β akarnya
(2r β 1) atau (2r - 1) = 0
β (2r β 1)2 = 0
β r1 = r2 = Β½ yaitu r0
Dengan penyelesaian menurut teorema 2, solusi relasi rekursifnya berbentuk:
an = Ξ±1r0n + Ξ±2nr0
n
maka diperoleh an = Ξ±1(1/2)n + Ξ±2n(1/2)n ...(*)
karena a0= 6 dan a1 = 8 kita subtitusikan kepersamaan (*)
a0= 6 menjadi a0 = 6 = Ξ±1 ( Β½ )0 + Ξ±2 0. ( Β½ )0 = Ξ±1
a1= 8 menjadi a1 = 8 = Ξ±1 ( Β½ )1 + Ξ±2 1. ( Β½ )1 = Β½ Ξ±1 + Β½ Ξ±2 ...(1)
didapat Ξ±1 = 6, kita subtitusikan kepersamaan (1).
Β½ Ξ±1 + Β½ Ξ±2 = 1
Β½ 6 + Β½ Ξ±2 = 8
Β½ Ξ±2 = 8 β 3
Ξ±2 = 5
Β½
Ξ±2 = 10
maka penyelesaian relasi rekursifnya 2 an -2 an-1 +1
2an-2 = 0 adalah
an = Ξ±1(1/2)n + Ξ±2n(1/2)n
β an = 6 (1/2)n + 10n(1/2)n
d. Tentukan solusi rekursif ππ + 6ππβ1 + 9ππβ2 = 0 untuk π β₯ 2 dengan π0 = 1 dan
π1 = 3.
Penyelesaian :
Diketahui : ππ + 6ππβ1 + 9ππβ2 = 0 , π β₯ 2π0 = 1, π1 = 3
Ditanya : Solusi relasi rekursif ?
Jawab :
Persamaan Karakteristik
π2 + 6π + 9 = 0
Akar β akar karakteristik
π + 3 π + 3π1,2 = β3
Solusi rekusif (umum)
ππ = πΌ1ππ + πΌ2ππ
π
ππ = πΌ1(β3)π+πΌ2π(β3)
πβ¦β¦ β
Karena π0 = 1 πππ π1 = 3π0 = 1 β π0 = 1 = πΌ1(β3)
0+πΌ20(β3)0= πΌ1β¦(1)
π1 = 2 β π1 = 3 = πΌ1(β3)1+πΌ21(β3)
1= β3πΌ1 β 3πΌ2β¦(2)
Subtitusikan persamaan (1) dan (2)
β3πΌ1 β 3πΌ2 = 3βΊ β3(1) β 3πΌ2 = 3
βΊβ3πΌ2 = 6βΊ πΌ2 = β2
Jadi solusi relasi rekursifnya
ππ = πΌ1(β3)π+πΌ2π(β3)
π
ππ = (β3)πβ2π(β3)π
e. Tentukan relasi rekursif ππ β 3ππβ1 + 3ππβ2 β ππβ3 = 0 untuk π β₯ 3 dengan
π0 = 1, π1 = 2, πππ π2 = 4
Penyelesaian :
Diketahui : ππ β 3ππβ1 + 3ππβ2 β ππβ3 = 0, untuk π β₯ 3π0 = 1, π1 = 2, πππ π2 = 4
Ditanya : Solusi relasi rekursif ?
Jawab :
Persamaan Karakteristik
π3 β 3π2 + 3π β 1 = 0
Akar β akar karakteristik
π β 1 π β 1 π β 1π1,2,3 = 1
Solusi rekursif (umum)
ππ = πΌ1ππ + πΌ2ππ
π + πΌ3π2ππ
ππ = πΌ11π + πΌ2π1
π + πΌ3π21πβ¦(β)
Karena π0 = 1, π1 = 2, πππ π2 = 4π0 = 1 βΊ π0 = 1 = πΌ11
0 + πΌ2010 + πΌ30
210 = πΌ1β¦(1)π1 = 2 βΊ π1 = 2 βΊ πΌ11
1 + πΌ21. 11 + πΌ31
211 = πΌ1 + πΌ2 + πΌ3β¦(2)π2 = 4 βΊ π2 = 4 βΊ πΌ11
2 + πΌ22. 12 + πΌ32
212 = πΌ1 + 2πΌ2+4πΌ3β¦ 3
Dari persamaan di (1),(2) dan (3) diperoleh :1 + πΌ2 + πΌ3 = 2
1 + 2πΌ2+4πΌ3 = 4Γ 4Γ 1
4 + 4πΌ2 + 4πΌ3 = 8
1 + 2πΌ2+4πΌ3 = 43 + 2πΌ2 = 4
2πΌ2 = 1
πΌ2 =1
2
1 + πΌ2 + πΌ3 = 2
βΊ 1 +1
2+ πΌ3 = 2
βΊ3
2+ πΌ3 = 2
βΊ πΌ3 =1
2
Jadi solusinya adalah πΌ1 = 1, πΌ2 =1
2, πΌ3 =
1
2
Solusi Relasi Rekursif
ππ = πΌ11π + πΌ2π1
π + πΌ3π21π
ππ = 1(1)π +1
2π1π +
1
2π21π
5. Misalkan {an} adalah barisan yang memenuhi relasi rekurensif berikut:
an = 2anβ1 β anβ2 ; a0 = 1 dan a1 = 2
Periksa apakah an = 3n merupakan solusi relasi rekurensi tersebut ?
Penyelesaian:
Penyelesaian: 2anβ1 β anβ2 = 2[3(n β 1)] β 3(n β 2)
= 6n β 6 β 3n + 6
= 3n = an
Jadi, an = 3n merupakan solusi dari relasi rekurens tersebut.
27
Soal relasi rekurensi homogen
6. Tentukan solusi homogen dari relasi rekurensi ππ + ππβ1 β 6ππβ2 = 0 dengan
kondisi batas π0 = 0, π1 = 1.
7. Tentukan solusi dari relasi rekurensi ππ + 4ππβ1 + 4ππβ2 = 2π.
8. Tentukan solusi homogen dari relasi rekurensi 4ππ β 20ππβ1 + 17ππβ2 β4ππβ3 = 0
PENYELESAIAN :
No.6
ππ + ππβ1 β 6ππβ2 = 0
Persamaan karakteristik
πΌ2 + πΌ β 6 = 0βΊ πΌ + 3 πΌ β 2 = 0
Akar karakteristik
πΌ1 = β3 dan πΌ2 = 2
Solusinya
ππ(β)
= π΄1πΌ1π + π΄2πΌ2
π
βΊ ππ(β)
= π΄1(β3)π+π΄22
π
Dengan kondisi batas π0 = 0 dan π1 = 1, maka
ππ(β)
= π΄1(β3)0+π΄22
0 βΉ 0 = π΄1 + π΄2
ππ(β)
= π΄1(β3)1+π΄22
1 βΉ 1 = β3π΄1 + 2π΄2
Sehingga diperoleh
π΄1 = β1
5πππ π΄2 =
1
5
Solusi homogen
ππ(β)
= β1
5β3 π +
1
52π
7. ππ + 4ππβ1 + 4ππβ2 = 2π
Persamaan karakteristik
πΌ2 + 4πΌ + 4 = 0βΊ πΌ + 2 πΌ + 2
Akar karakteristik
πΌ1,2 = β2
Karena akar 1,2 sama maka
Solusi homogen
ππ(β)
= (π΄1ππβ1 + π΄2π
πβ2)πΌ1π
ππ(β)
= (π΄1π + π΄2)(β2)π
8. 4ππ β 20ππβ1 + 17ππβ2 β 4ππβ3 = 0
Persamaan Kuadrat
4πΌ3 β 20πΌ2 + 17πΌ β 4 = 0βΊ 2πΌ β 1 2πΌ β 1 πΌ β 4
Akar karakteristik
πΌ1,2 =1
2πΌ3 = 4
Solusi homogen
ππ(β)
= π΄1π + π΄21
2
π
+ π΄3. 4