10a. Relasi Rekurrens Derajat Tinggi Homogen Dan Nonhomogen

Teknik Perhitungan:
Relasi Rekurrens/
Recurrence Relations
Relasi Rekurrens Homoge
dengan Derajat Lebih Tinggi
Matematika Diskrit
Solusi Relasi Rekurrens Linier Homogen dengan
Koefisien Konstan Berderajat Tinggi
Teorema 3:
Asumsikan 𝑐1 , 𝑐2 , … , 𝑐𝑘 adalah bilangan real.

Asumsikan persamaan karakteristik
𝑟 𝑘 − 𝑐1 𝑟 𝑘−1 − ⋯ − 𝑐𝑘 = 0
memiliki sebanyak 𝑘 akar yang berbeda, yaitu 𝑟1 , 𝑟2 , … , 𝑟𝑘 .
Maka barisan {𝑎𝑛 } adalah solusi dari relasi rekurrens
𝑎𝑛 = 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + … + 𝑐𝑘 𝑎𝑛−𝑘
jika dan hanya jika
𝑎𝑛 = 𝛽1 𝑟1𝑛 + 𝛽2 𝑟2𝑛 + ⋯ + 𝛽𝑘 𝑟𝑘𝑛
untuk 𝑛 = 0, 1, 2, … , di mana 𝛽1 , 𝛽2 , … , 𝛽𝑘 adalah konstan.
Contoh 4: Relasi Rekurrens Bederajat Tiga
Temukan solusi dari relasi rekurrens :

𝒂𝒏 = 𝟔𝒂𝒏−𝟏 − 𝟏𝟏𝒂𝒏−𝟐 + 𝟔𝒂𝒏−𝟑 , dengan 𝒂𝟎 = 𝟐, 𝒂𝟏 = 𝟓 and 𝒂𝟐 = 𝟏𝟓
Pembahasan:
𝑎𝑛 = 6𝑎𝑛−1 − 11𝑎𝑛−2 + 6𝑎𝑛−3 ⟹ 𝑎𝑛 − 6𝑎𝑛−1 + 11𝑎𝑛−2 − 6𝑎𝑛−3 = 0
Sehingga persamaan karakteristiknya adalah: 𝑟 3 − 6𝑟 2 + 11𝑟 − 6 = 0
Solusi persamaan karakteristik : 𝑟 = 1, 𝑟 = 2 atau 𝑟 = 3
Sehingga solusi umum dari relasi rekurrens:
𝒂𝒏 = 𝜷𝟏 𝟏𝒏 + 𝜷𝟐 𝟐𝒏 + 𝜷𝟑 𝟑𝒏
= 𝜷𝟏 + 𝜷𝟐 𝟐𝒏 + 𝜷𝟑 𝟑𝒏
Contoh 4: Relasi Rekurrens Bederajat Tiga
Solusi Umum : Solusi Khusus :

𝒂𝒏 = 𝜷𝟏 + 𝜷𝟐 𝟐𝒏 + 𝜷𝟑 𝟑𝒏 𝒂 𝒏 = 𝟏 − 𝟏 ∙ 𝟐𝒏 + 𝟐 ∙ 𝟑𝒏
= 𝟏 − 𝟐𝒏 + 𝟐 ∙ 𝟑𝒏
𝑎0 = 2 𝑎0 = 𝛽1 + 𝛽2 ∙ 20 + 𝛽3 ∙ 30
𝑛=0 ⟹ 𝛽1 + 𝛽2 + 𝛽3 = 2
SPL
Nilai awal: 𝑎1 = 5 𝑎1 = 𝛽1 + 𝛽2 ∙ 21 + 𝛽3 ∙ 31 𝛽1 = 1
𝛽2 = −1
𝑛=1 ⟹ 𝛽1 + 2𝛽2 + 3𝛽3 = 5
𝛽3 = 2
𝑎2 = 15 𝑎2 = 𝛽1 + 𝛽2 ∙ 22 + 𝛽3 ∙ 32
𝑛=2 ⟹ 𝛽1 + 4𝛽2 + 9𝛽3 = 15
Relasi Rekurrens Linier NONHOMOGEN
dengan Koefisien Konstan
Bentuk Umum Relasi Rekurrens Linier Nonhomogen
Definisi :
Suatu relasi rekurrens linier NONHOMOGEN berderajat 𝒌 dengan koefisien

konstanta merupakan relasi rekurrens yang berbentuk
𝒂𝒏 = 𝒄𝟏 𝒂𝒏−𝟏 + 𝒄𝟐 𝒂𝒏−𝟐 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌 + 𝑭 𝒏
dengan 𝑐1 , 𝑐2 , … ∈ ℝ dan 𝑐𝑘 ≠ 0, dan 𝐹 𝑛 ≠ 0. 𝐹 𝑛 merupakan suatu fungsi yang
hanya tergantung pada 𝑛.
Dan relasi rekurrens
𝒂𝒏 = 𝒄𝟏 𝒂𝒏−𝟏 + 𝒄𝟐 𝒂𝒏−𝟐 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌
disebut relasi rekurrens homogennya, yang berperan penting untuk menemukan
solusi nonhomogennya.
Contoh Relasi Rekurrens Linier Nonhomogen
Contoh Relasi Rekurrens Relasi Rekurrens Homogennya

Nonhomogen
𝑃𝑛 = 2𝑃𝑛−1 + 2𝑛 𝑃𝑛 = 2𝑃𝑛−1
𝑓𝑛 = 𝑓𝑛−1 + 𝑓𝑛−2 + 𝑛2 + 𝑛 + 1 𝑓𝑛 = 𝑓𝑛−1 + 𝑓𝑛−2
𝑎𝑛 = 𝑎𝑛−5 + 𝑛3𝑛 𝑎𝑛 = 𝑎𝑛−5

Teorema Solusi Relasi Rekurrens Linier Nonhomogen
Teorema
(𝑝)
Jika {𝑎𝑛 } adalah solusi partikulir dari relasi rekurrens linier nonhomogen dengan koefis
ien konstan. Maka solusi dari relasi rekurrens nonhomogen tersebut adalah berbentuk
ℎ (𝑝)
𝑎𝑛 + 𝑎𝑛 ,
(ℎ)
dengan {𝑎𝑛 } merupakan solusi homogen dari relasi rekurrens
𝑎𝑛 = 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + … + 𝑐𝑘 𝑎𝑛−𝑘
Contoh 5: Relasi Rekurrens Linier Nonhomogen
Temukan solusi dari relasi rekurrens linier nonhomogen:

𝒂𝒏 = 𝟑𝒂𝒏 −𝟏 + 𝟐𝒏, dengan 𝒂𝟏 = 𝟑
Pembahasan:
Tahap 1: Menemukan solusi homogen
Perhatikan bentuk homogen dari relasi rekurrens tersebut:

𝑎𝑛 = 3𝑎𝑛 −1 ⟹ 𝑎𝑛 − 3𝑎𝑛−1 = 0.
Persamaan karakteristik : 𝑟 − 3 = 0
Solusi persamaan karakteristik 𝑟 = 3.
(𝒉)
Sehingga solusi homogen dari relasi rekurrens: 𝒂 𝒏 = 𝜷 𝟑𝒏
Tahap 2: Menemukan solusi partikulir
Relasi Rekurrens nonhomogen : 𝑎𝑛 = 3𝑎𝑛 −1 + 2𝑛 ⟹ 𝑎𝑛 −3𝑎𝑛 −1 = 2𝑛

Perhatikan bagian nonhomogen dari relasi rekurrens adalah 𝐹 𝑛 = 2𝑛.
(𝑝)
 Asumsi solusi partikulir : 𝑎𝑛 = 𝐴𝑛 + 𝐵
𝑝
Maka 𝑎𝑛−1 = 𝐴 𝑛 − 1 + 𝐵
𝒑 𝟑
Relasi rekurrens: 𝑎𝑛 − 3𝑎𝑛 −1 = 2𝑛 ∴ 𝒂𝒏 = −𝒏 −
𝟐
𝐴𝑛 + 𝐵 − 3 𝐴 𝑛 − 1 + 𝐵 = 2𝑛
Ruas kiri Ruas Kanan 2
𝐴𝑛 + 𝐵 − 3 𝐴𝑛 − 𝐴 + 𝐵 = 2𝑛
⟹𝐴= = −1
Koefisien 𝑛 −2𝐴 2 −2
𝐴𝑛 + 𝐵 − 3𝐴𝑛 + 3𝐴 − 3𝐵 = 2𝑛
konstanta 3𝐴 − 2𝐵 0 ⟹ 2𝐵 = 3𝐴
𝐴 − 3𝐴 𝑛 + 𝐵 + 3𝐴 − 3𝐵 = 2𝑛 = 3 −1
−2𝐴𝑛 + 3𝐴 − 2𝐵 = 2𝑛 = −3
3
𝐵=−
2
Tahap 3: Solusi umum dari relasi rekurrens
Solusi Solusi Solusi

homogen partikulir umum
𝒑
(𝒉) 𝒂𝒏 𝟑
𝒂𝒏 𝟑 𝒂 𝒏 = 𝜷 𝟑𝒏 − 𝒏 −
= 𝜷 𝟑𝒏 = −𝒏 − 𝟐
𝟐
Tahap 4: Solusi khusus dari relasi rekurrens

Solusi Umum : Solusi Khusus :
𝟑
𝒂 𝒏 = 𝜷 𝟑𝒏 − 𝒏 − 𝟏𝟏 𝒏 𝟑
𝟐 𝒂𝒏 = 𝟑 −𝒏−
𝟔 𝟐
1
3
Nilai awal: 𝑎1 = 3 𝑎1 = 𝛽 ∙ 3 −1−
2
𝑛=1 5
3 = 3𝛽 −
2
5 11
⟹ 3𝛽 = 3 + =
2 2
11 11 11
⟹𝛽= :3 = 𝛽=
2 6 6
Asumsi Solusi Partikulir Untuk Beberapa Suku Nonhomogen
Contoh 𝑭 𝒏 Asumsi 𝒂𝒏
𝒑
2𝑛 𝐴 ∙ 2𝑛
3𝑛 𝐴𝑛 + 𝐵
𝑛2 − 1 𝐴𝑛2 + 𝐵𝑛 + 𝐶

10a. Relasi Rekurrens Derajat Tinggi Homogen Dan Nonhomogen

Diunggah oleh

Hak Cipta:

Format Tersedia

10a. Relasi Rekurrens Derajat Tinggi Homogen Dan Nonhomogen

Diunggah oleh

Informasi Dokumen

Judul Asli

Hak Cipta

Format Tersedia

Bagikan dokumen Ini

Bagikan atau Tanam Dokumen

Opsi Berbagi

Apakah menurut Anda dokumen ini bermanfaat?

Apakah konten ini tidak pantas?

Hak Cipta:

Format Tersedia

10a. Relasi Rekurrens Derajat Tinggi Homogen Dan Nonhomogen

Diunggah oleh

Hak Cipta:

Format Tersedia

Teknik Perhitungan:

Asumsikan 𝑐1 , 𝑐2 , … , 𝑐𝑘 adalah bilangan real.

Temukan solusi dari relasi rekurrens :

Solusi Umum : Solusi Khusus :

Suatu relasi rekurrens linier NONHOMOGEN berderajat 𝒌 dengan koefisien

Contoh Relasi Rekurrens Relasi Rekurrens Homogennya

𝑓𝑛 = 𝑓𝑛−1 + 𝑓𝑛−2 + 𝑛2 + 𝑛 + 1 𝑓𝑛 = 𝑓𝑛−1 + 𝑓𝑛−2

𝑎𝑛 = 𝑎𝑛−5 + 𝑛3𝑛 𝑎𝑛 = 𝑎𝑛−5

Temukan solusi dari relasi rekurrens linier nonhomogen:

Tahap 1: Menemukan solusi homogen

Perhatikan bentuk homogen dari relasi rekurrens tersebut:

Tahap 2: Menemukan solusi partikulir

Relasi Rekurrens nonhomogen : 𝑎𝑛 = 3𝑎𝑛 −1 + 2𝑛 ⟹ 𝑎𝑛 −3𝑎𝑛 −1 = 2𝑛

Tahap 3: Solusi umum dari relasi rekurrens

Solusi Solusi Solusi

Tahap 4: Solusi khusus dari relasi rekurrens

Anda mungkin juga menyukai