Relasi Rekurensi [PDF]

Citation preview

Relasi Rekurensi Matematika Diskrit II



Relasi Rekurensi Bentuk umum an = c1 an-1 + c2 an-2 + … + ck an-k dengan c1, c2, …, ck bilangan real dan ck  0.



Solusi Relasi Rekurensi Homogen Linear Solusi dalam Bentuk an = rn dengan r Konstan an = rn solusi dari an = c1 an-1 + c2 an-2 + … + ck an-k jika dan hanya jika rn = c1 rn–1 +c2 rn–2 + … + ck rn–k



rn – c1 rn–1 – c2 rn–2 – … – ck rn–k = 0 rk – c1 rk–1 – c2 rk–2 – … – ck–1 r – ck = 0



Solusi Relasi Rekurensi Homogen Linear



rk – c1 rk–1 – c2 rk–2 – … – ck–1 r – ck = 0 Persamaan Karakteristik



SOLUSI 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 rekurensi an = c1 an-1 + c2 an-2 berbentuk an = 1r1n + 2r2n 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 karakteristik Akar karakteristik Solusi Nilai awal a0= 2 dan a1= 7



: r2 – r – 2 = 0, : r = 2 dan r = – 1. : an= 1 2n + 2 (–1)n . : an = 32n – (–1)n .



Teorema 2 Misalkan c1, c2 bilangan real dengan c2  0 dan r2 – c1r – c2 = 0 mempunyai akar kembar r0. Maka semua solusi dari relasi rekurensi an = c1 an-1 + c2 an-2 berbentuk an = 1 r0n + 2 nr0n, n = 0,1,2,… dengan 1 dan 2 konstan.



Soal Tentukan solusi dari relasi rekurensi an = 6an-1 – 9an-2 dengan kondisi awal a0 = 1 dan a1 = 6.



Teorema 3 Misalkan c1, c2, …, ck bilangan real dan persamaan karakteristik rk – c1 rk-1 – c2 rk-2 – … – ck-1 r – ck = 0 mempunyai k akar r1, r2, …, rk yang berbeda. Maka, solusi relasi rekurensi an = c1an-1 + c2an-2 + … + ckan-k selalu berbentuk an = 1r1n + 2r2n + … + krkn , n=0,1,2,… dengan i , i=0,1,…, k konstan.



Soal Tentukan solusi dari relasi rekurensi an = 6an-1 – 11an-2 + 6an-3 dengan kondisi awal a0=2, a1=5 dan a2=15. Solusi. Persamaan karakteristik r3 – 6r2 + 11r – 6 = 0 Akar-akarnya r = 1, r = 2 dan r = 3 Solusi an = 11n + 22n + 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 rk-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 rekurensi an = c1 an-1 + c2 an-2 + … + ck an-k selalu berbentuk an = (1,0 + 1,1n + … + 1,m1-1 nm1-1)r1n + (2,0 + 2,1n + … + 2,m2-1 nm2-1)r2n + … + (t,0 + t,1n + … + t,mt-1 nmt-1)rtn



Soal Tentukan solusi dari relasi rekurensi an = –3an-1 – 3an-2 – an-3 dengan kondisi awal a0 = 1, a1 = –2 dan a2 = –1. Solusi. Persamaan karakteristik r3 + 3r2 + 3r +1 = 0. Akar r = –1 dgn multiplisitas 3. Solusi 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.



Relasi Rekurensi Tak Homogen Linear dengan Koefisien Konstan Secara umum, an = c1 an-1 + c2 an-2 + … + ck an-k + F(n) dengan ci , i = 0,1,2,… konstan dan F(n) fungsi tak nol. an = c1an-1 + c2an-2 + … + ck an-k disebut relasi rekurensi homogen yang berkaitan. Contoh. an = an-1 + 2n an = an-1 + an-2 + an-3 + n! an = 3an-2 + 5n



Teorema 5 Jika {an(p)} adalah solusi khusus dari relasi rekurensi tak homogen linear dengan koefisien konstan an = c1an-1 + c2an-2 + … + ckan-k + F(n) maka setiap solusi berbentuk {an(p) + an(h)}, dengan {an(h)} solusi relasi rekurensi homogen yang berkaitan an = c1an-1 + c2an-2 + … + ckan-k.



Soal Tentukan semua solusi dari relasi rekurensi an = 3an-1 + 2n. Solusi. Karena F(n) = 2n adalah polinom berderajat satu, maka kita coba polinom berderajat satu pn = cn + d, dengan c dan d konstan untuk mendapatkan solusi khusus. Didapat, pn = 3pn-1 + 2n cn+d = 3(c(n-1)+d) + 2n (-2c-2)n + (3c-2d) = 0 Sehingga c = -1 dan d = -3/2. Jadi, solusi khususnya an(p) = -n - 3/2.



Soal Solusi homogen dari relasi homogen yang berkaitan, an = 3an-1 adalah an(h) = 3n, dengan  konstan. Menurut Teorema 5, solusi umum dari an = 3an-1 + 2n adalah an = an(p) + an(h) = -n - 3/2 + 3n. Jika diketahui a1 = 3, maka solusi menjadi an = -n - 3/2 + (11/6) 3n.



Soal Tentukan semua solusi dari relasi rekurensi: an = 5an-1 - 6an-2 + 7n. Solusi. Solusi homogennya adalah an(h) = 13n + 22n. Karena F(n) = 7n, solusi khusus yg perlu dicoba adalah an(p) = c 7n. Maka, c 7n = 5c 7n-1 – 6c 7n-2 + 7n. Diperoleh c = 49/20. Jadi, solusi umumnya: an = 13n + 22n + 49/20 7n.



Teorema 6 Misalkan {an} memenuhi relasi rekurensi tak homogen linear an = c1an-1 + c2an-2 + … + ckan-k + F(n) dengan ci , i=1,2,…,k bilangan real dan F(n) = (btnt + bt-1nt-1 + … + b1n + b0) sn dengan bi , i=0,1,…,t dan s bilangan real. Jika s bukan akar dari persamaan karakteristik relasi rekurensi homogen yang berkaitan, maka terdapat solusi khusus yang berbentuk (ptnt + pt-1nt-1 + … + p1n + p0) sn Jika s akar dari persamaan karakteristik dengan multiplisitas m, maka terdapat solusi khusus yang berbentuk F(n) = nm (ptnt + pt-1nt-1 + … + p1n + p0) sn



Soal Carilah solusi khusus dari relasi rekurensi an = 6an-1 - 9an-2 + F(n) bila 1. F(n) = 3n, 2. F(n) = n 3n, 3. F(n) = n2 2n, dan 4. F(n) = (n2+1) 3n Solusi. Solusi homogennya adalah an(h) = 13n + 2n3n. Dan solusi khususnya adalah 1. an(p) = p0 n2 3n. 2. an(p) = n2 (p1n+p0)3n. 3. an(p) = (p2n2+p1n+p0)2n. 4. an(p) = n2(p2n2+p1n+p0)3n.



Soal Tentukan solusi dari relasi rekurensi Hn = 2Hn-1 + 1, H1 = 1, dan H2 = 3 Solusi. Relasi homogen yang berkaitan adalah Hn = 2Hn-1 dan solusi homogennya Hn(h) =  2n. Karena F(n) = 1 = 1n, maka solusi khususnya adalah Hn(p) = p0 1n = p0. Sehingga solusi umumnya adalah Hn =  2n + p0 Dengan memandang H1 = 1 dan H2 = 3 diperoleh =1 dan p0= -1. Jadi, Hn = 2n - 1



Fungsi Pembangkit dalam Relasi Rekurensi



Soal Cari solusi relasi rekurensi ak = 3ak-1 untuk k = 1, 2, 3, … dengan kondisi awal a0 = 2



Referensi Struktur Diskrit, Rinaldi Munir