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