Lisa Laila Rafida_17205019_rr.docx

TUGAS INDIVIDU “RELASI REKURSIF 2.1 – 2.6”

Diajukan untuk Memenuhi Tugas Perkuliahan MATEMATIKA DISKRIT

Dosen Pengampu Mata Kuliah: Dr. Armiati, M.Pd Nama NIM Semeser Kelas

: LISA LAILA RAFIDA : 17205019 :2 :C

PROGRAM STUDI PENDIDIKAN MATEMATIKA PROGRAM PASCA SARJANA UNIVERSITAS NEGERI PADANG 2019

LISA LAILA RAFIDA_17205019_KELASC |

1. Misal an menyatakan banyaknya cara untuk menempatkan n obyek berbeda di dalam 5 kotak. Tulis dan selesaikan relasi rekursif untuk an. Penyelesaian: Misalkan an menyatakan banyaknya cara menyusun n objek yang berbeda, maka ada n cara meletakkan n objek pada urutan pertama di barisan. Dengan cara yang sama untuk 𝑎𝑛−1 , maka ada n – 1 cara. Oleh karena itu formula relasi rekursi dapat dinyatakan sebagai 𝑎𝑛= 𝑛𝑎𝑛−1an. 𝑎𝑛 = 𝑛𝑎𝑛−1 = 𝑛[(𝑛 − 1)𝑎𝑛−2 ] = 𝑛[(𝑛 − 1)(𝑛 − 2)𝑎𝑛−3 ] = 𝑛(𝑛 − 1)(𝑛 − 2)(𝑛 − 3) … .× 3 × 2 × 1 = 𝑛! Sehingga, untuk menempatkan obyek yang berbeda di dalam 5 kotak adalah : 𝑎𝑛 = 𝑛! 𝑎5 = 5! 𝑎5 = 5 × 4 × 3 × 2 × 1 𝑎5 = 120 cara 2. Sebuah tangga memiliki n buah anak tangga. Saudara diminta untuk menaiki tangga tersebut dengan aturan sebagai berikut: “Setiap kali melangkah, saudara diperbolehkan melangkah satu atau dua anak tangga sekaligus”. a. Jika bn menyatakan banyaknya cara yang berbeda saudara dapat menaiki tangga dengan n buah anak tangga tersebut, tulis relasi rekursif untuk bn. b. Selesaikan relasi rekursif pada soal a. Penyelesaian: a. Misalkan banyak anak tangga (𝑛) = 1,2,3,4, …

LISA LAILA RAFIDA_17205019_KELASC

Page 2

LISA LAILA RAFIDA_17205019_KELASC |

Cara yang dimaksud dengan mencoba-coba sehingga diperoleh: 1) Cara menaiki 1 anak tangga yaitu (1) maka ada 1 cara 2) Cara menaiki 2 anak tangga yaitu (1,1), (2) maka ada 2 cara 3) Cara menaiki 3 anak tangga yaitu (1,1,1), (1,2), (2,1) maka ada 3 cara 4) Cara menaiki 4 anak tangga yaitu(1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2) maka ada 5 cara. Dari percobaan 4 anak tangga, kita melihat suatu pada bilangan yaitu: 1,2,3,5, … Dari pola terlihat bahwa: 1) Banyak cara menaiki 3 anak tangga sama dengan banyak cara menaiki 1 𝑎𝑛𝑎𝑘 𝑡𝑎𝑛𝑔𝑔𝑎 + 2 𝑎𝑛𝑎𝑘 𝑡𝑎𝑛𝑔𝑔𝑎 2) Banyak cara menaiki 5 anak tangga sama dengan 2 𝑎𝑛𝑎𝑘 𝑡𝑎𝑛𝑔𝑔𝑎 + 3 𝑎𝑛𝑎𝑘 𝑡𝑎𝑛𝑔𝑔𝑎 Jika cara menaiki 𝑛 𝑎𝑛𝑎𝑘 𝑡𝑎𝑛𝑔𝑔𝑎 dimisalkan dengan 𝑎𝑛 maka diperoleh: 𝑎1 = 1 𝑎2 = 2 𝑑𝑎𝑛 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 ; 𝑛 ≥ 3 b. Selesaikan relasi rekursif pada soal (a) Penyelesaian : 𝑎1 = 1 𝑎2 = 2 𝑑𝑎𝑛 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 ; 𝑛 ≥ 3 𝑎𝑛 − 𝑎𝑛−1 − 𝑎𝑛−2 = 0 Misalkan 𝑎𝑛 = 𝑥 𝑛 diperoleh: 𝑎𝑛 − 𝑎𝑛−1 − 𝑎𝑛−2 = 0 𝑥 𝑛 − 𝑥 𝑛−1 − 𝑥 𝑛−2 = 0 Setiap suku dibagi dengan pangkat terendah yaitu 𝑥 𝑛−2 maka diperoleh persamaan karakteristiknya yaitu: 𝑥 2 − 𝑥 − 1 = 0 … (∗) 𝑥2 − 𝑥 − 1 = 0 Maka akar-akar karakteristiknya diperoleh: 𝑥1 =

𝑎 + √𝑏 2 − 4𝑎𝑐 1 + √(−1)2 − 4(1)(−1) 1 + √5 = = 2 2 2

LISA LAILA RAFIDA_17205019_KELASC

Page 3

LISA LAILA RAFIDA_17205019_KELASC |

𝑎 − √𝑏 2 − 4𝑎𝑐 1 − √(−1)2 − 4(1)(−1) 1 − √5 𝑥2 = = = 2 2 2 Sehinga solusi umum diperoleh: 𝑛

𝑛

𝑎𝑛 = 𝑝1 𝑥1 + 𝑝2 𝑥2

𝑛

𝑛

1 + √5 1 − √5 = 𝑝1 ( ) + 𝑝2 ( ) 2 2

Dengan mensubtitusikan kondisi awal 𝑎1 = 1, 𝑎2 = 2 ke solusi umum diperoleh: 1

1

2

2

1 + √5 1 − √5 1 + √5 1 − √5 𝑎1 = 𝑝1 ( ) + 𝑝2 ( ) →( ) 𝑝1 + ( ) 𝑝2 = 1 … (∗) 2 2 2 2 2

2

1 + √5 1 − √5 1 + √5 1 − √5 𝑎2 = 𝑝1 ( ) + 𝑝2 ( ) →( ) 𝑝1 + ( ) 𝑝2 = 2 … (∗∗) 2 2 2 2

Sehingga dari persamaan (*) dan (**) diperoleh: 𝑝1 =

5 + √5 5 − √5 𝑑𝑎𝑛 𝑝2 = 10 10

Subtitusikan 𝑝1 dan 𝑝2 ke dalam solusi umum sehingga diperoleh solusi homogen relasi rekursif sebagai berikut: 𝑛

𝑛

1 + √5 1 − √5 𝑎𝑛 = 𝑝1 ( ) + 𝑝2 ( ) 2 2 𝑛

𝑛

5 + √5 1 + √5 5 − √5 1 − √5 = ( ) + ( ) 10 2 10 2

3. berapa banyak daerah yang terbentuk jika terdapaat n-garis digambar pada bidang datar dengan syarat: a. setiap dua garis harus berpotongan di satu titik. b. Tidak boleh ada 3 garis yang melalui 1 titik Penyelesaian: Misalkan: 𝑎𝑛 = banyak daerah yang terbentuk, jika terdapat n-garis digambar pada bidang datar dengan syarat yang diberikan. Jelas bahwa 𝑎𝑛 = 1 Untuk 𝑛 ≥ 1, rr untuk 𝑎𝑛 dapat diperoleh dengan cara berikut:

LISA LAILA RAFIDA_17205019_KELASC

Page 4

LISA LAILA RAFIDA_17205019_KELASC |

kn

k1

kn-1 k2...

Misalkan telah tergambar (n-1) garis pada bidang datar dengan syarat tersebut, maka terbentuk 𝑎𝑛−1 daerah. Jika garis ke-n dibuat dengan dua syarat yang sama, maka garis ke-n akan memotong (n-1) garis sebelumnya di (n-1) titik potong yang berbeda, sehingga (n-1) titik potong tersebut mempartisi garis ke-n menjadi n bagian. Setiap bagian garis membagi 1 daerah sebelumnya menjadi 2 daerah, sehingga setiap bagian garis ke-n menambah satu daerah dari daerah sebelumnya. Akibatnya terjadi penambahan n daerah. Dengan demikian daerah yang terbentuk ditunjukkan dengan RR: 𝑎 = 𝑎𝑛−1 + 𝑛, 𝑛 ≥ 1 { 𝑛 𝑎0 = 0, 𝑎1 = 1 Menyelesaikan RR tersebut: Misalkan ∞

∞ 𝑛

𝑃(𝑥) = ∑ 𝑎𝑛 𝑥 = ∑ 𝑎𝑛−1 𝑥 𝑛−1 𝑛=0

𝑛=1

Kalikan kedua bagian rekursif dengan 𝑥 𝑛 , kemudian ‘disigma’ untuk 𝑛 ≥ 1, diperoleh: ∞

∞

∞

𝑛

∑ 𝑎𝑛 𝑥 = ∑ 𝑎𝑛−1 𝑥 + ∑ 𝑛𝑥 𝑛 𝑛=1

𝑛

𝑛=1

𝑛=1

∞

∞

∞

∑ 𝑎𝑛 𝑥 𝑛 − 𝑎0 𝑥 0 = 𝑥 ∑ 𝑎𝑛−1 𝑥 𝑛−1 + ∑ 𝑛𝑥 𝑛 𝑛=0

𝑛=1

𝑛=0

1

𝑛 Dari F2: 1−𝑥 = ∑∞ 𝑛=0 𝑥 1

𝑛−1 Dideferensial: (1−𝑥)2 = ∑∞ 𝑛=0 𝑛𝑥

LISA LAILA RAFIDA_17205019_KELASC

Page 5

LISA LAILA RAFIDA_17205019_KELASC |

𝑥

𝑛 Kalikan dengan x: (1−𝑥)2 ∑∞ 𝑛=0 𝑛𝑥

𝑥 (1 − 𝑥)2 𝑥 (1 − 𝑥)𝑃(𝑥) = 1 + (1 − 𝑥)2 𝑃(𝑥) − 1 = 𝑥. 𝑃(𝑥) +

𝑃(𝑥) =

1 𝑥 + 1 − 𝑥 (1 − 𝑥)3 ∞

∞

= ∑ 𝑥𝑛 + ∑ (

3+𝑛−1

∞

) 𝑥𝑛 = ∑ 𝑥𝑛 + ∑ (

𝑛=0

𝑛=0

𝑛

∞

∞

𝑛+1 ) 𝑥𝑛 𝑛−1

= ∑ 𝑥𝑛 + ∑ ( 𝑛=0

𝑛=0

∞

𝑛=0

𝑛=0

𝑛+2 ) 𝑥 𝑛+1 𝑛

Jadi solusi untuk RR adalah: 1

,𝑛 = 0 𝑛+1 1+( ),𝑛 ≥ 1 𝑛−1 1 ,𝑛 = 0 (𝑛 + 1)𝑛 𝑎𝑛 = { 1+( ),𝑛 ≥ 1 2 1 ,𝑛 = 0 2 𝑛 +𝑛 𝑎𝑛 = { 1+( ),𝑛 ≥ 1 2 𝑎𝑛 = {

1 ,𝑛 = 0 2 𝑎𝑛 = { 𝑛 + 𝑛 + 2 ,𝑛 ≥ 1 2 𝑎𝑛 =

𝑛2 + 𝑛 + 2 ,𝑛 ≥ 0 2

4. Misalkan 𝑥1 adalah sebuah akar karakteristik dari relasi rekursif (3.2.1) a. Bila 𝑥1 adalah akar karakteristik rangkap dua, tunjukkan bahwa 𝑥1 𝑛 dan 𝑛𝑥1 𝑛 adalah solusi-solusi dari (3.2.1) Penyelesaian : 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0

LISA LAILA RAFIDA_17205019_KELASC

Page 6

LISA LAILA RAFIDA_17205019_KELASC |

Misalkan 𝑎𝑛 = 𝑥 𝑛 diperoleh: 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0 𝑥 𝑛 + 𝑐1 𝑥 𝑛−1 + ⋯ + 𝑐𝑘 𝑥 𝑛−𝑘 = 0 Setiap suku dibagi dengan pangkat terendah yaitu 𝑥 𝑛−𝑘 maka diperoleh persamaan karakteristiknya yaitu: 𝑥 𝑘 + 𝑐1 𝑥 𝑘−1 + ⋯ + 𝑐𝑘 = 0 … (∗) Maka akar-akar karakteristiknya diperoleh: 𝑥1,2 = 𝑥1 (𝑟𝑎𝑛𝑔𝑘𝑎𝑝 2) Sehinga solusi umum diperoleh: 𝑎𝑛 = 𝑝1 (𝑛1−1 )𝑥1 𝑛 + 𝑝2 (𝑛2−1 )𝑥2 𝑛 = 𝑝1 (𝑥1 )𝑛 + 𝑝2 𝑛(𝑥1 )𝑛 Subtitusikan 𝑝1 dan 𝑝2 adalah sembarang konstanta ke dalam solusi umum sehingga diperoleh solusi homogen relasi rekursif sebagai berikut: 𝑎𝑛 = (𝑥1 )𝑛 + 𝑛(𝑥1 )𝑛 b. Bila 𝑥1 adalah akar karakteristik rangkap tiga, tunjukkan bahwa 𝑥1 𝑛 , 𝑛𝑥1 𝑛 𝑛

dan 𝑛2 𝑥1 adalah solusi-solusi dari (3.2.1) Penyelesaian: 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0 Misalkan 𝑎𝑛 = 𝑥 𝑛 diperoleh: 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0 𝑥 𝑛 + 𝑐1 𝑥 𝑛−1 + ⋯ + 𝑐𝑘 𝑥 𝑛−𝑘 = 0 Setiap suku dibagi dengan pangkat terendah yaitu 𝑥 𝑛−𝑘 maka diperoleh persamaan karakteristiknya yaitu: 𝑥 𝑘 + 𝑐1 𝑥 𝑘−1 + ⋯ + 𝑐𝑘 = 0 … (∗) Maka akar-akar karakteristiknya diperoleh:

𝑥1,2 = 𝑥1 (𝑟𝑎𝑛𝑔𝑘𝑎𝑝 3)

Sehinga solusi umum diperoleh: 𝑎𝑛 = 𝑝1 (𝑛1−1 )𝑥1 𝑛 + 𝑝2 (𝑛2−1 )𝑥2 𝑛 + 𝑝3 (𝑛3−1 )𝑥3 𝑛 = 𝑝1 (𝑥1 )𝑛 + 𝑝2 𝑛(𝑥1 )𝑛 + 𝑝3 𝑛2 (𝑥1 )𝑛

LISA LAILA RAFIDA_17205019_KELASC

Page 7

LISA LAILA RAFIDA_17205019_KELASC |

Subtitusikan 𝑝1 dan 𝑝2 adalah sembarang konstanta ke dalam solusi umum sehingga diperoleh solusi homogen relasi rekursif sebagai berikut: 𝑎𝑛 = (𝑥1 )𝑛 + 𝑛(𝑥1 )𝑛 + 𝑛2 (𝑥1 )𝑛 c. Perumum, untuk 𝑥1 adalah akar karakteristik rangkap 𝑚. Penyelesaian: 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0 Misalkan 𝑎𝑛 = 𝑥 𝑛 diperoleh: 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0 𝑥 𝑛 + 𝑐1 𝑥 𝑛−1 + ⋯ + 𝑐𝑘 𝑥 𝑛−𝑘 = 0 Setiap suku dibagi dengan pangkat terendah yaitu 𝑥 𝑛−𝑘 maka diperoleh persamaan karakteristiknya yaitu: 𝑥 𝑘 + 𝑐1 𝑥 𝑘−1 + ⋯ + 𝑐𝑘 = 0 … (∗) Maka akar-akar karakteristiknya diperoleh: 𝑥1,2,…,𝑚 = 𝑥1 (𝑟𝑎𝑛𝑔𝑘𝑎𝑝 𝑚) Sehinga solusi umum diperoleh: 𝑎𝑛 = 𝑝1 (𝑛1−1 )𝑥1 𝑛 + 𝑝2 (𝑛2−1 )𝑥2 𝑛 + 𝑝3 (𝑛3−1 )𝑥3 𝑛 + ⋯ + 𝑝𝑘 (𝑛𝑚−1 )𝑥𝑚 𝑛 = 𝑝1 (𝑥1 )𝑛 + 𝑝2 𝑛(𝑥1 )𝑛 + 𝑝3 𝑛2 (𝑥1 )𝑛 + ⋯ + 𝑝𝑚 (𝑛𝑚−1 )𝑥1 𝑛 Subtitusikan 𝑝1 dan 𝑝2 adalah sembarang konstanta ke dalam solusi umum sehingga diperoleh solusi homogen relasi rekursif sebagai berikut: 𝑎𝑛 = (𝑥1 )𝑛 + 𝑛(𝑥1 )𝑛 + 𝑛2 (𝑥1 )𝑛 + ⋯ + (𝑛𝑚−1 )𝑥1 𝑛 5. Berapa banyak daerah yang terbentuk, jika terdapat n-lingkaran digambar pada bidang datar dengan syarat: a. Setiap dua lingkaran harus berpotongan di dua titik b. Tidak boleh ada 3 lingkaran yang melalui 1 titik Penyelesaian: Misalkan: 𝑎𝑛 = banyak daerah yang terbentuk, jika terdapat n-lingkaran digambar pada bidang datar dengan syarat yang diberikan. Jelas bahwa 𝑎0 = 2

LISA LAILA RAFIDA_17205019_KELASC

Page 8

LISA LAILA RAFIDA_17205019_KELASC |

(daerah dalam dan daerah luar lingkaran). Untuk 𝑛 ≥ 1, rr untuk 𝑎𝑛 dapat diperoleh dengan cara berikut:

L2 . . . L. n-1

L1

Ln

Misalkan telah tergambar (n-1) lingkaran

pada bidang datar dengan syarat

tersebut, maka terbentuk 𝑎𝑛−1 daerah. Jika garis ke-n dibuat dengan dua syarat yang sama, maka lingkaran ke-n akan memotong (n-1) lingkaran sebelumnya di (n-1) titik potong yang berbeda, sehingga (2n-2) titik potong tersebut mempartisi garis ke-n menjadi (2n-2) bagian. Setiap bagian busur lingkaran membagi 1 daerah sebelumnya menjadi 2 daerah, sehingga setiap bagian busur lingkaran ken menambah satu daerah dari daerah sebelumnya. Akibatnya terjadi penambahan (2n-2) daerah. Dengan demikian daerah yang terbentuk ditunjukkan dengan RR: 𝑎 = 𝑎𝑛−1 + 2𝑛 − 2, 𝑛 ≥ 1 { 𝑛 𝑎0 = 0, 𝑎1 = 1 Menyelesaikan RR tersebut: Misalkan ∞

∞ 𝑛

𝑃(𝑥) = ∑ 𝑎𝑛 𝑥 = ∑ 𝑎𝑛−1 𝑥 𝑛−1 𝑛=0

𝑛=1

LISA LAILA RAFIDA_17205019_KELASC

Page 9

LISA LAILA RAFIDA_17205019_KELASC |

Kalikan kedua bagian rekursif dengan 𝑥 𝑛 , kemudian ‘disigma’ untuk 𝑛 ≥ 1, diperoleh: ∞

∞

∞

∞

∑ 𝑎𝑛 𝑥 𝑛 = ∑ 𝑎𝑛−1 𝑥 𝑛 + 2 ∑ 𝑛𝑥 𝑛 − 2 ∑ 𝑥 𝑛 𝑛=1

𝑛=1

∞

𝑛=1

∞ 𝑛

∞

0

∑ 𝑎𝑛 𝑥 − 𝑎0 𝑥 = 𝑥 ∑ 𝑎𝑛−1 𝑥 𝑛=0

𝑛=1

𝑛−1

∞

+ 2 ∑ 𝑛𝑥 − 2 ∑ 𝑥 𝑛 + 2𝑥 0

𝑛=1

𝑛

𝑛=0

𝑛=0

1

𝑛 Dari F2: 1−𝑥 = ∑∞ 𝑛=0 𝑥

Dideferensial:

1

𝑛−1 = ∑∞ 𝑛=0 𝑛𝑥

(1−𝑥)2

𝑥

𝑛 Kalikan dengan x: (1−𝑥)2 ∑∞ 𝑛=0 𝑛𝑥

𝑃(𝑥) − 2 = 𝑥. 𝑃(𝑥) + 2

(1 − 𝑥)𝑃(𝑥) =

𝑃(𝑥) =

𝑥 1 − 2 +2 (1 − 𝑥)2 1−𝑥

2𝑥 2 − +4 2 (1 − 𝑥) 1−𝑥

2𝑥 2 4 − + 3 2 (1 − 𝑥) (1 − 𝑥) 1−𝑥

∞

∞ ∞ 3+𝑛−1 2+𝑛−1 𝑛 𝑛 = 2𝑥 ∑ ( )𝑥 − 2∑( ) 𝑥 + 4 ∑ 𝑥𝑛 𝑛 𝑛 𝑛=0 𝑛=0 𝑛=0 ∞

∞ ∞ 𝑛+2 𝑛+1 𝑛 𝑛 = 2𝑥 ∑ ( )𝑥 − 2∑( ) 𝑥 + 4 ∑ 𝑥𝑛 𝑛 𝑛 𝑛=0 𝑛=0 𝑛=0 ∞

∞ ∞ 𝑛+1 𝑛+1 = 2𝑥 ∑ ( ) 𝑥𝑛 − 2 ∑ ( ) 𝑥𝑛 + 4 ∑ 𝑥𝑛 𝑛 𝑛=1 𝑛 − 1 𝑛=0 𝑛=0

Jadi solusi untuk RR adalah:

LISA LAILA RAFIDA_17205019_KELASC

Page 10

LISA LAILA RAFIDA_17205019_KELASC |

𝑛+1 −2 ( )+4 ,𝑛 = 0 𝑛 𝑎𝑛 = { 𝑛+1 𝑛+1 2( ) − 2( ) + 4, 𝑛 ≥ 1 𝑛−1 𝑛 −2(𝑛 + 1) + 4 ,𝑛 = 0 𝑎𝑛 = { (𝑛 + 1)𝑛 2( ) − 2(𝑛 + 1) + 4 , 𝑛 ≥ 1 2 𝑎𝑛 = {

−2𝑛 + 2 ,𝑛 = 0 2 𝑛 + 𝑛 − 2𝑛 − 2 + 4, 𝑛 ≥ 1

𝑎𝑛 = {

−2𝑛 + 2 𝑛2 − 𝑛 + 2

,𝑛 = 0 ,𝑛 ≥ 1

𝑎𝑛 = 𝑛2 − 𝑛 + 2, 𝑛 ≥ 0 6. Selesaikan relasi rekursif berikut dengan fungsi pembangkit! g. 𝑎0 = 2 ; 𝑎𝑛 = 𝑎𝑛−1 +n (n-1), n≥1 penyelesaian: misalkan p (x) adalah fungsi pembangkit biasa dari barisan (𝑎𝑛 ) . maka 𝑛 p(x) = ∑~ 𝑛=1 𝑎𝑛 𝑥

kalikan persamaan dengan 𝑥 𝑛 , sehingga : 𝑎𝑛 𝑥 𝑛 = 𝑎𝑛−1𝑥 𝑛 +n (n-1) 𝑥 𝑛 Karena n≥ 1 ~ 𝑛 𝑛 𝑛 ∑~ 𝑛=1 𝑎𝑛 𝑥 = ∑𝑛=1(𝑎𝑛−1 𝑥 + n (n-1) 𝑥 )

Ruas kiri 𝑛 1 2 3 ∑~ 𝑛=1 𝑎𝑛 𝑥 = 𝑎1 𝑥 + 𝑎2 𝑥 + 𝑎3 𝑥 + ⋯

= (𝑎0 + 𝑎1 𝑥1 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯) - 𝑎0 = p(x) – 2 Ruas kanan 1 1 2 3 ∑~ 𝑛=1 𝑎𝑛−1 = 𝑎0 𝑥 + 𝑎1 𝑥 + 𝑎2 𝑥 + ⋯

= 𝑥(𝑎0 + 𝑎1 𝑥1 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯)

LISA LAILA RAFIDA_17205019_KELASC

Page 11

LISA LAILA RAFIDA_17205019_KELASC |

= x p(x) Ruas kanan 2 ~

∑ 𝑛(𝑛 − 1) 𝑥 𝑛 = 2𝑥 2 + 6𝑥 3 + 12𝑥 4 + ⋯ 𝑛=1

= 2𝑥 2 (1 + 3𝑥 + 6𝑥 2 + ⋯ ) 7. Selesaikan relasi rekursif berikut dengan metode akar karakteristik

g. a 0  a1  a 2  0 a3  5 ; a n  10 a n  1  37 a n  2  60 a n  3  36 a n  4 , n  4 penyelesaian: Misalkan a n  x n

a n  10 a n 1  37 a n  2  60 a n  3  36 a n  4 x n  10 x n 1  37 x n  2  60 x n  3  36 x n  4

 xn4

x 4  10 x 3  37 x 2  60 x  36 x 4  10 x 3  37 x 2  60 x  36  0 x  2 x  2 x  3 x  3  0 x1, 2  2 , x3, 4  3

Sehingga solusi umum dari relasi rekursif adalah

a n  C0 2  C1 n 2  C2 3  C3 n 3 n

n

n

n

Substitusi nilai a0 , a1 , a2 , dan a3 ke persamaan umum relasi rekursif di atas a0  0  0  C0  C2  C2   C0 a1  0  0  2 C 0  2 C1  3 C 2  3 C 3 a 2  0  0  4 C 0  8 C1  9 C 2  18 C 3

............. (1) .............. (2) ............. (3)

a 3  5  5  8 C 0  24 C1  27 C 2  81 C 3 ............. (4)

Substitusikan (1) ke (2), (3), dan (4). Sehingga diperoleh  1 C 0  2 C1  3 C 3  0

.............. (5)

 5C 0  8 C1  18 C 3  0

.............. (6)

 19 C 0  19 C1  81 C 3  5

............. (7)

Eliminasi (5) dan (6) serta (5) dan (7), sehingga diperoleh 2C1  3 C3  0 .............. (8)

 14 C1  24 C3  5

.............. (9)

LISA LAILA RAFIDA_17205019_KELASC

Page 12

LISA LAILA RAFIDA_17205019_KELASC |

Substitusikan (8) ke (9), diperoleh C 3  5

3

Subtitusikan nilai C1 ke (8), diperoleh C1  5

2

Subtitusikan nilai C1 dan C3 ke (5), diperoleh C 0  10 Subtitusikan nilai C0 ke per 1, diperoleh C 2 = 10 Subtitusi nilai C0, C1, C2dan 34 ke dalam persamaan umum dari relasi rekursif sehingga diperoleh penyelesaian

a n   10 2  n

5 5 n n n n 2  10 3  n 3 2 3

8. Ilustrasi, misalkan:  𝑎𝑛 menyatakan banyaknya barisan binair n-angka yang memuat “0” sebanyak bilangan genap dan “1” sebanyak bilangan genap  𝑏𝑛 menyatakan banyaknya barisan binair n-angka yang memuat “0” sebanyak genap dan memuat “1”sebanyak ganjil  𝑐𝑛 menyatakan banyaknya barisan binair n-angka yang memuat “0” sebanyak ganjil dan “1” sebanyak genap Relasi rekursif untuk 𝑎𝑛 , 𝑏𝑛 , 𝑐, dan 𝑑𝑛 diberikan oleh sistem rekursif berikut: 𝑎𝑛 = 𝑏𝑛−1 + 𝑐𝑛−1 𝑏𝑛 = 𝑎𝑛−1 + 𝑏𝑛−1 𝑐𝑛 = 𝑎𝑛−1 + 𝑐𝑛−1 Dengan kondisi awal 𝑎0 = 1, 𝑏0 = 𝑐0 = 0 Fungsi pembangkit system rekursif diatas yakni :Misal𝐴(𝑥), 𝐵(𝑥), 𝑑𝑎𝑛 𝐶(𝑥) berturut-turut adalah fungsi pembangkit biasa dari 𝑎𝑛 , 𝑏𝑛 , 𝑑𝑎𝑛 𝑐𝑛 . Maka: 𝐴(𝑥) = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ = 𝑎0 + (𝑏0 + 𝑐0 )𝑥 + (𝑏1 + 𝑐1 )𝑥 2 + ⋯

LISA LAILA RAFIDA_17205019_KELASC

Page 13

LISA LAILA RAFIDA_17205019_KELASC |

= 𝑎0 + 𝑥(𝑏0 + 𝑏1 𝑥 + 𝑏2 𝑥 2 + ⋯ ) + 𝑥(𝑐0 + 𝑐1 𝑥 + 𝑐2 𝑥 2 + ⋯ ) = 1 + 𝑥 𝐵(𝑥) + 𝑥 𝐶(𝑥) 𝐵(𝑥) = 𝑏0 + 𝑏1 𝑥 + 𝑏2 𝑥 2 + ⋯ = 𝑏0 + (𝑎0 + 𝑏0 )𝑥 + (𝑎1 + 𝑏1 )𝑥 2 + ⋯ = 0 + 𝑥(𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ ) + 𝑥(𝑏0 + 𝑏1 𝑥 + 𝑏2 𝑥 2 + ⋯ ) = 𝑥 𝐴(𝑥) + 𝑥 𝐵(𝑥) 𝐵(𝑥) − 𝑥𝐵(𝑥) = 𝑥𝐴(𝑥) 𝐵(𝑥)(1 − 𝑥) 𝐵(𝑥) =

= 𝑥𝐴(𝑥)

𝑥 𝐴(𝑥) 1−𝑥

𝑥 𝐴(𝑥) 1−𝑥 (1 − 𝑥)𝐵(𝑥) 𝑚𝑎𝑘𝑎 𝐴(𝑥) = 𝑥 =

𝐶(𝑥) = 𝑐0 + 𝑐1 𝑥 + 𝑐2 𝑥 2 + … = 𝑐0 + (𝑎0 + 𝑐0 )𝑥 + (𝑎1 + 𝑐1 )𝑥 2 + … = 0 + 𝑥 ( 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + … ) + 𝑥 ( 𝑐0 + 𝑐1 𝑥 + 𝑐2 𝑥 2 + … ) = 𝑥𝐴(𝑥) + 𝑥𝐶(𝑥) 𝐶(𝑥) − 𝑥𝐶(𝑥) = 𝑥𝐴(𝑥) 𝐶(𝑥)(1 − 𝑥) 𝐶(𝑥) =

= 𝑥𝐴(𝑥)

𝑥 𝐴(𝑥) 1−𝑥

Dengan demikian kita punya system persamaan : 𝐴 (𝑥) = 1 + 𝑥 𝐵 (𝑥) + 𝑥 𝐶 (𝑥) 𝐵 (𝑥) = 𝑥 𝐴(𝑥) + 𝑥 𝐵(𝑥) 𝐶 (𝑥) = 𝑥𝐴(𝑥) + 𝑥𝐶(𝑥) Maka:

LISA LAILA RAFIDA_17205019_KELASC

Page 14

LISA LAILA RAFIDA_17205019_KELASC |

𝐴 (𝑥) = 1 + 𝑥 𝐵 (𝑥) + 𝑥 𝐶 (𝑥) Karena 𝐵 (𝑥) = 𝐶 (𝑥), maka: 𝐴 (𝑥) = 1 + 𝑥 𝐵 (𝑥) + 𝑥 𝐵 (𝑥) 𝐴 (𝑥) = 1 + 2𝑥 𝐵 (𝑥) (1 − 𝑥)𝐵(𝑥) = 1 + 2𝑥 𝐵 (𝑥) 𝑥 (1 − 𝑥)𝐵(𝑥) = 𝑥 + 2𝑥 2 𝐵(𝑥) 𝐵(𝑥) − 𝑥𝐵(𝑥) = 𝑥 + 2𝑥 2 𝐵(𝑥) 𝐵(𝑥) − 𝑥𝐵(𝑥) − 2𝑥 2 𝐵(𝑥) = 𝑥 𝑥 −𝑥 𝐵(𝑥) = 𝑎𝑡𝑎𝑢 𝐵(𝑥) = 1 − 𝑥 − 2𝑥 2 2𝑥 2 + 𝑥 − 1 −𝑥 𝐵(𝑥) = 2 2𝑥 + 𝑥 − 1 −𝑥 = 2 2𝑥 − 𝑥 + 2𝑥 − 1 −𝑥 = 𝑥(2𝑥 − 1) + 1(2𝑥 − 1) −𝑥 = (2𝑥 − 1)(𝑥 + 1) =

−𝑥 1 . (2𝑥 − 1) (𝑥 + 1)

=

𝑥 1 . (1 − 2𝑥) (𝑥 + 1)

Karena 𝐵 (𝑥) = 𝐶 (𝑥) maka: 𝐶 (𝑥) =

𝑥 1 . (1 − 2𝑥) (𝑥 + 1)

Dari persamaan 𝐴 (𝑥) = 1 + 2𝑥 𝐵 (𝑥) diperoleh: 𝐴 (𝑥) = 1 + 2𝑥(

𝑥 1 . ) (1 − 2𝑥) (𝑥 + 1)

𝐴 (𝑥) = 1 + 2𝑥 2 (

1 1 . ) (1 − 2𝑥) (𝑥 + 1)

sehinggadiperoleh :

LISA LAILA RAFIDA_17205019_KELASC

Page 15

LISA LAILA RAFIDA_17205019_KELASC |

𝐴 (𝑥) = 1 + 2𝑥 2 (

1 1 . ) (1 − 2𝑥) (𝑥 + 1)

𝐵(𝑥) = 𝑥(

1 1 . ) (1 − 2𝑥) (𝑥 + 1)

𝐶(𝑥) = 𝑥(

1 1 . ) (1 − 2𝑥) (𝑥 + 1)

Selanjutnya kita cari koefisien𝑥 𝑛 dalam A (x), B (x), dan C (x) Karena, 𝐴 (𝑥) = 1 + 2𝑥 2 (

1 1 . ) (1 − 2𝑥) (𝑥 + 1)

∞

∞ 𝑘

𝐴 (𝑥) = 1 + 2 ∑(2) ( 𝑥 )

𝑘+1

𝑘=0

∑(−1)𝑘 ( 𝑥 )𝑘+1 𝑘=0

Maka, 𝑎𝑛 = 1 + 2. (2 )𝑛−1 (−1)𝑛−1 atau, 1 𝑎𝑛 = {1 − 2𝑛 1 + 2𝑛

,

𝑗𝑖𝑘𝑎 𝑛 = 0 , 𝑗𝑖𝑘𝑎 𝑛 𝑔𝑒𝑛𝑎𝑝 𝑑𝑎𝑛 𝑛 ≥ 2} , 𝑗𝑖𝑘𝑎 𝑛 𝑔𝑎𝑛𝑗𝑖𝑙

Karena, 𝐵 (𝑥) = 𝑥(

1 1 . ) (1 − 2𝑥) (𝑥 + 1)

∞

∞ 𝑘

= 𝑥 ∑(2) ( 𝑥 ) ∑(−1)𝑘 ( 𝑥 )𝑘 𝑘=0 ∞

𝑘

𝑘=0 ∞

= ∑(2)𝑘 ( 𝑥 )𝑘+1 ∑(−1)𝑘 ( 𝑥 )𝑘 𝑘=0

𝑘=0

Maka 𝑏𝑛 = (2 )𝑛−1 (−1)𝑛 atau,

LISA LAILA RAFIDA_17205019_KELASC

Page 16

LISA LAILA RAFIDA_17205019_KELASC |

0 𝑏𝑛 = { 2𝑛−1 −(2𝑛−1 )

, 𝑗𝑖𝑘𝑎 𝑛 = 0 , 𝑗𝑖𝑘𝑎 𝑛 𝑔𝑒𝑛𝑎𝑝 𝑑𝑎𝑛 𝑛 ≥ 2 } , 𝑗𝑖𝑘𝑎 𝑛 𝑔𝑎𝑛𝑗𝑖𝑙

Karena C (x) = B (x), maka𝑐𝑛 = 𝑏𝑛 9. Selesaikan sistem rekursif berikut. b. a0  1 , b0  c0  0

a n  2a n1  bn 1  cn 1 , n  1 bn  bn 1  c n 1  4 n 1

, n 1

cn  cn 1  bn 1  4 n 1

, n 1

Misalkan A(x), B(x) dan C(x) berturut-turut adalah fungsi pembangkit biasa dari an, bn dan cn. maka

A( x)  a 0 x  a1 x 2  a 2 x 3    a 0 x  (2a 0  b0  c0  ) x 2  (2a1  b1  c1  ) x 3    x  2 x (a 0 x  a1 x 2  )  x (a 0 x  a1 x 2  )  x (a 0 x  a1 x 2  )  x  2 x A( x)  x B( x)  x C ( x) B( x)  b0 x  b1 x 2  b2 x 3    b0 x  (b0  c0  4 0 ) x 2  (b1  c1  41 ) x 3    0  x (b0 x  b1 x 2  )  x (c0 x  c1 x 2  )  x (4 0 x  41 x 2  ) 

 x B( x)  x C ( x)  x  (4 x) n n 0

 1   x B ( x )  x C ( x )  x   1  4x 

LISA LAILA RAFIDA_17205019_KELASC

Page 17

LISA LAILA RAFIDA_17205019_KELASC |

C ( x)  c0 x  c1 x 2  c 2 x 3    c0 x  (c0  b0  4 0 ) x 2  (c1  b1  41 ) x 3    0  x (c0 x  c1 x 2  )  x (b0 x  b1 x 2  )  x (4 0 x  41 x 2  ) 

 x C ( x)  x B( x)  x  (4 x) n n 0

 1   x C ( x )  x B ( x )  x   1  4x  Sehingga diperoleh

A( x)  x  2 x A( x)  B( x)  x C ( x)  1  B ( x )  x B ( x )  x C ( x )  x   1  4x   1  C ( x )  x C ( x )  x B ( x )  x   1  4x  Dengan penyelesaian

x 1  2x 1 B( x)  2  5x 1 C ( x)   2  5x A( x) 

Cari koefisien xn dalam A(x), B(x) dan C(x). Karena

LISA LAILA RAFIDA_17205019_KELASC

Page 18

LISA LAILA RAFIDA_17205019_KELASC |

x 1  2x  1   x   1  2x 

A( x) 



 x 2 n x n n 0



  2 n x n 1 n 0 

  2 n 1 x n n 1

Maka a n  2 n 1 Atau

, n 1 1 a n   n 1 , n2 2 Karena 1 2  5x   1  1   5  2 1 x  2  

B( x) 

n

1  5    xn 2 n 0  2 

Maka bn 

15   22

n

Atau

LISA LAILA RAFIDA_17205019_KELASC

Page 19

LISA LAILA RAFIDA_17205019_KELASC |

1 , n0  2 bn   n  1  5  , n  1  2  2  Karena 15 C ( x)   B( x) maka c n     22

n

Atau

 1 , n0   2 cn   n 1 5      , n  1  2  2 

LISA LAILA RAFIDA_17205019_KELASC

Page 20