Bab I-iii Fix Rev Terakhirr.docx

MATEMATIKA DISKRIT RELASI REKURSIF 2.1 – 2.3

OLEH : 1. LISA LAILA RAFIDA

( 17205019 )

2. NOVIA MAULINA

( 18205064 )

DOSEN : Dr. Armiati, M.Pd

PROGRAM STUDI PENDIDIKAN MATEMATIKA PROGRAM PASCASARJANA UNIVERSITAS NEGERI PADANG FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM 2019

1

. BAB I PENDAHULUAN 1.1

Pendahuluan

Makalah ini membahas mengenai relasi rekursif beserta jenis-jenisnya. Terdapat pula pembahasan untuk memodelkan suatu masalah dengan relasi rekursif dan penyelesaian masalah menggunakan homogen dan non homogen dengan koefisien konstanta beserta penyelesaian dengan fungsi pembangkit. 1.2

Tujuan

Setelah kegiatan belajar bersama, diharapkan mahasiswa dapat : a. mengetahui definisi relasi rekursif dan jenis-jenisnya. b. memodelkan suatu masalah dengan relasi rekursif. c. menjelaskan relasi rekursif homogen dengan koefisien konstanta. d. menyelesaikan masalah dengan relasi rekursif homogen dengan koefisien konstanta. e. menjelaskan relasi rekursif non homogen dengan koefisien konstanta. f. menyelesaikan masalah relasi rekursif non homogen dengan koefisien konstanta. g. menyelesaikan masalah relasi rekursif dengan fungsi pembangkit. 1.3

Pendahuluan

Relasi rekursif adalah suatu topik penting dan menarik dalam kombinatorik. Banyak permasalahan dalam matematika, khususnya kombinatorik dapat dimodelkan kedalam bentuk relasi rekursif. Misalkan Pn menyatakan banyaknya permutasi dari n obyek berbeda. Jelas P1=1 karena hanya ada satu permutasi dari 1 obyek. Untuk n ≥ 2, Pn diperoleh dengan cara berikut: Terdapat kemungkinan posisi dari obyek tertentu, dan setiap kemungkinan posisi dari obyek ini akan diikuti oleh permutasi dari n-1 obyek. Karena banyaknya permutasi dari n-1 obyek ini adalah Pn-1 maka terdapat hubungan Pn = Pn-1.untuk lebih jelasnya, akan dibahas pada makalah ini.

2

BAB II PEMBAHASAN

2.1

Pengertian Relasi Rekursif

Relasi rekursif adalah suatu topik penting dan menarik dalam kombinatorik. Banyak permasalahan dalam matematika, khususnya kombinatorik dapat dimodelkan kedalam bentuk relasi rekursif. Misalkan Pn menyatakan banyaknya permutasi dari n obyek berbeda. Jelas P1=1 karena hanya ada satu permutasi dari 1 obyek. Untuk n ≥ 2, Pn diperoleh dengan cara berikut: Terdapat kemungkinan posisi dari obyek tertentu, dan setiap kemungkinan posisi dari obyek ini akan diikuti oleh permutasi dari n-1 obyek. Karena banyaknya permutasi dari n-1 obyek ini adalah Pn-1 maka terdapat hubungan Pn = Pn-1 Dengan demikan, P1 = 1; Pn = Pn-1, n ≥ 2

(2.1.1)

Bentuk (2.1.1) di sebut relasi rekursif untuk Pn, banyak permutasi dari n obyek, P1 = 1 di sebut kondisi awal sedangkan Pn = Pn-1 disebut bagian rekursif dari relasi rekursif tersebut. Contoh: Relasi rekursif dari banyaknya barisan biner n digit dengan syarat tidak ada angka 1 yang saling berdekatan. Misalkan an adalah banyaknya barisan yang dimaksud, dan berikut adalah ilustrasi untuk n = 1, n = 2, n = 3, dan n = 4. n=1

n=2

n=3

n=4

0

00

000

000

1

10

100

1000

01

010

0100

001

0010

3

101

1010 0001 1001 0101

Jelas a1 = 2, dan a2 = 3, dan an = an-1 + an-2 (n ≥ 3) Kondisi Awal

bagian rekursif

Relasi Rekursif Kalau kondisi awal ini kita ubah nilainya, maka barisan yang kita peroleh tentu akan berbeda dari barisan diatas. Contoh Misalkan a1, a2, ...., b1, b2,...., c1, c2, ...,adalah 3 barisan yang semuanya memenuhi relasi rekursif, nilai suatu suku sama dengan 3 kali nilai suku sebelumnya. Jadi, an = 3 an-1, , bn = 3 bn-1, , cn = 3 cn-1, Tetapi kondisi awal ketiga barisan berbeda, a1 = 0, b1 = 1, c1 = 2 yatakan barisan-barisan tersebut dengan cara menuliskan beberapa suku awal barisan tersebut, apakah ketiganya merupakan barisan yang sama? Penyelesaian: Barisan an adalah 0,0,0,... Barisan bn adalah 3, 9, 27, ... Barisan cn adalah 6, 18, 54, ... Tampak bahwa ketiga barisan berbeda

4

Contoh Suatu barisan c0, c1, c2,... didefinisikan secara rekursif sebagai berikut: Ck = Ck-1+ kCk-2+1 Dengan kondisi awal c0 = 1 dan c1 = 2, hitunglah c5 Penyelesaian: Karena barisan didefinisikan secara rekursif, maka c5 tidak bisa dihitung secara langsung, tetapi harus terlebih dahulu menghitung c2, c3, dan c4. C2= C1 + 2C0 + 1=2 + 2.1 + 1=5 C3 = C2+ 3C1+1= 5 + 3.2 + 1= 12 C4 = C3+ 4C2+1= 12 + 4.5 + 1= 33 C5 = C4+ 5C3+1= 33 + 5.12 + 1= 94 Jadi C5 = 94 Contoh Tentukan relasi rekursif untuk menentukan banyaknya cara menyusun n buah obyek berbeda dalam suatu barisan. Tentukan banyak cara untuk menyusun 8 buah obyek. Penyelesaian: Misalkan Pn menyatakan banyak cara menyusun n obyek yng berbeda, maka ada n obyek pada urutan pertama pada barisan. Dengan cara yang sama untuk Pn-1 maka ada n-1 cara. Oleh karena itu formula relasi rekursif dapat dinyatakan: P8 = nPn-1 Pn-2 Pn-3 Pn-4 Pn-5 Pn-6 Pn-7 = n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7) = (8)(8-1)(8-2)(8-3)(8-4)(8-5)(8-6)(8-7) = (8)(7)(6)(5)(4)(3)(2)(1) = 8!

5

Jadi, Banyaknya cara untuk menyusun 8 buah obyek ada 8! Barisan Fibbonacci Relasi rekursif yang paling terkenal dan sering digunakan yaitu barisan Fibbonacci. Relasi rekursi ini merupakan salah satu relasi rekursi yang paling tua di dunia, dibahas pada buku liber Abbaci yang ditulis oleh Leonardo of Pisa atau yang lebih dikenal dengan nama Fibonacci pada tahun 1202. Sekarang, perhatikan barisan bilangan Fibbonacci (1,1,2,3,5,8,13,21,34,55,89,...). Misal Fn menyatakan suku ke n dari bilangan tersebut. Perhatikan bahwa n ≥ 3 , suku ke-n dari barisan adaah jumlah dua suku berurutan persis didepannya. Sehingga reasi rekursif untuk Fn dapat dituis sebagai berikut: F1 = F2 = 1; Fn = Fn-1 + Fn-2 , n ≥ 3 Daam relasi ini terdapat dua kondisi awal yaitu F1 dan F2. Kalau kondisi awal ini kita ubah nilainya, maka barisan Fibonacci yang kita peroleh tentu akan berbeda dari barisan Fibonacci diatas. Ilustrasi: Suku ke n → F3 = F3-1 + F3-2 = F2 + F1 F4 = F4-1 + F4-2 = F3 + F2 F1 = F2 = 1; F3 = F3-1 + F3-2; F4 = F4-1 + F4-2,...

F1 = F2 = 1; F3 = F2 + F1, F4 = F3 + F2,..., Fn = Fn-1 + Fn-2 , n ≥ 3 Kondisi awal

bagian rekursif

Relasi Rekursif

6

2.2

Relasi Rekursif Linear dengan Koefisien Konstanta

Bentuk umum Bagian Rekursif dari RR linear berderajat 𝑘 berbentuk: 𝑎𝑛 + ℎ1 (𝑛) 𝑎𝑛−1 + ℎ2 (𝑛) 𝑎𝑛−2 + … + ℎ𝑘 (𝑛) 𝑎𝑛−𝑘 = 𝑓(𝑛), yang mana ℎ𝑖(𝑛) dan 𝑓(𝑛) adalah fungsi dalam n dan ℎ𝑘 (𝑛) ¹ 0 Jika 𝑓(𝑛) = 0 maka RR nya disebut homogen, jika tidak demikian disebut non homogen. Selanjutnaya jika untuk setiap 𝑖 ∈ {1,2,3, … 𝑘}, ℎ𝑖 (𝑛) = 𝑘𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑎, maka relasi rekrusif tersebut dinamakan relasi rekrusif dengan koefisien konstanta. Misalnya: 𝑎1 = 𝑎2 = 0; 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 1, 𝑛 ≥ 3 adalah relasi rekursif linear nonhomogen

a.

derajat dua dengan koefisien konstanta. 𝑎1 = 𝑎2 = 1; 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 , 𝑛 ≥ 3

b.

adalah

relasi

rekursif

linear

homogen

adalah

relasi

rekursif

berderajat dua dengan koefisien konstanta. 𝑎0 = 𝑎1 = 1; 𝑎𝑛 = 𝑎0 𝑎𝑛−1 + 𝑎2 𝑎𝑛−2 + 𝑎𝑛−1 𝑎0 , 𝑛 ≥ 1

c.

nonlinear. 𝐷1 = 1; 𝐷𝑛 = 𝑛𝐷𝑛−1 + (−1)𝑛 , 𝑛 ≥ 1 adalah relasi rekursif nonhomogen derajat satu

d.

dengan koefisien bukan konstanta. 1.

Relasi Rekursif Linear Homogen Dengan Koefisien Konstanta

Bentuk umum dari relasi rekursif linear homogen dengan koefisien konstanta adalah sebagai berikut: 𝒂𝒏 + 𝒄𝟏 𝒂𝒏−𝟏 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌 = 𝟎 ; 𝒄𝒌 ≠ 𝟎

(2.2.1)

dan 𝒌 adalah kondisi awal. Dimana untuk 𝟏 ≤ 𝒊 ≤ 𝒌, 𝒄𝒊 = konstanta. Pada bagian ini akan dikembangkan suatu teknik untuk menyelesaikan relasi rekursif (2.2.1). Untuk maksud tersebut diperlukan teorema berikut Teorema 2.2.1 (Prinsip Superposisi) Jika 𝒈𝟏 (𝒏) dan 𝒈𝟐 (𝒏) berturut-turut adalah solusi dari 𝒂𝒏 + 𝒄𝟏 𝒂𝒏−𝟏 + 𝒄𝟐 𝒂𝒏−𝟐 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌 = 𝒇𝟏 (𝒏)

(2.2.2)

dan Bukti: 𝒂𝒏 + 𝒄𝟏 𝒂𝒏−𝟏 + 𝒄𝟐 𝒂𝒏−𝟐 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌 = 𝒇𝟐 (𝒏)

(2.2.3)

Karena dan 𝒈𝟐 (𝒏) berturut-turut solusi darî 𝟐(2.2.2) (2.2.3) maka maka 𝒈 untuk konstanta 𝒄̂𝟏 danadalah 𝒄̂𝟐 , 𝒄̂𝟏 𝒈 𝒈𝟐 (𝒏)dan adalah solusi dari 𝟏 (𝒏)sebarang 𝟏 (𝒏) + 𝒄 𝒂𝒏 + 𝒄𝟏 𝒂𝒏−𝟏 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌 = 𝒄̂𝟏 𝒇𝟏 (𝒏) + 𝒄̂𝟐 𝒇𝟐 (𝒏)

(2.2.4)

7

Misal

𝒂𝒏 = 𝒄̂𝟏 𝒈𝟏 (𝒏) + 𝒄̂𝟐 𝒈𝟐 (𝒏)

Maka 𝒂𝒏 + 𝒄𝟏 𝒂𝒏−𝟏 + 𝒄𝟐 𝒂𝒏−𝟐 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌 = 𝒄̂𝟏 𝒈𝟏 (𝒏) + 𝒄̂𝟐 𝒈𝟐 (𝒏) + 𝒄𝟏 (𝒄̂𝟏 𝒈𝟏 (𝒏 − 𝟏) + 𝒄̂𝟐 𝒈𝟐 (𝒏 − 𝟏))+ 𝒄𝟐 (𝒄̂𝟏 𝒈𝟏 (𝒏 − 𝟐) + 𝒄̂𝟐 𝒈𝟐 (𝒏 − 𝟐))+...+ 𝒄𝒌 (𝒄̂𝟏 𝒈𝟏 (𝒏 − 𝒌) + 𝒄̂𝟐 𝒈𝟐 (𝒏 − 𝒌)) = 𝒄̂𝟏 (𝒈𝟏 (𝒏) +𝒄𝟏 𝒈𝟏 (𝒏 − 𝟏)+𝒄𝟐 𝒈𝟐 (𝒏 − 𝟐) + ⋯ + 𝒄𝒌 𝒈𝟏 (𝒏 − 𝒌) )+ 𝒄̂𝟐 (𝒈𝟐 (𝒏) + 𝒄𝟐 𝒈𝟐 (𝒏 − 𝟏)+𝒄𝟐 𝒈𝟐 (𝒏 − 𝟐) + ⋯ + )+...+ 𝒄𝒌 𝒈𝟐 (𝒏 − 𝒌) ) = 𝒄̂𝟏 𝒇𝟏 (𝒏) + 𝒄̂𝟐 𝒇𝟐 (𝒏) Sehingga 𝒄̂𝟏 𝒈𝟏 (𝒏) + 𝒄̂𝟐 𝒈𝟐 (𝒏) Merupakan solusi. Sebagai akibat dari teorema Prinsip Superposisi diperoleh teorema sebagai berikut: Akibat Teorema Prinsip Superposisi 2.2.2 Jika 𝒈𝟏 (𝒏), 𝒈𝟐 (𝒏), …,𝒈𝒌 (𝒏) adalah solusi-solusi dari 𝒂𝒏 + 𝒄𝟏 𝒂𝒏−𝟏 + 𝒄𝟐 𝒂𝒏−𝟐 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌 = 𝟎

(2.2.5)

Maka 𝒄̂𝟏 𝒈𝟏 (𝒏) + 𝒄̂𝟐 𝒈𝟐 (𝒏) + ⋯ + 𝒄̂𝒌 𝒈𝒌 (𝒏) juga solusi dari (2.2.5) untuk sebarang konstanta 𝒄̂𝟏 , 𝒄̂𝟐 , … , 𝒄̂𝒌 . Persamaan karakteristik dari relasi rekursif (2.2.1) Untuk menyelesaikan relasi (2.2.1), pertama-tama kita misalkan𝑎𝑛 = 𝑥 𝑛 . Untuk menentukan 𝑥, kita substitusikan 𝑎𝑖 dengan 𝑥 𝑖 pada (2.2.1) dimana 𝑖 ∈ {𝑛, 𝑛 − 1, 𝑛 − 2, … , 𝑛 − 𝑘}.Diperoleh 𝑥 𝑛 + 𝑐1 𝑥 𝑛−1 + 𝑐2 𝑥 𝑛−2 + ⋯ + 𝑐𝑘 𝑥 𝑛−𝑘 = 0 Bagi kedua ruas persamaan terakhir dengan 𝑥 𝑛−𝑘 diperoleh 𝒙𝒌 + 𝒄𝟏 𝒙𝒌−𝟏 + 𝒄𝟐 𝒙𝒌−𝟐 + ⋯ + 𝒄𝒌 = 𝟎

(2.2.6)

Persamaan (2.2.6) disebut persamaan karakteristik dari relasi rekursif (2.2.1). Pada umumnya persamaan (2.2.6) menjadi 𝑘 akar, beberapa di antaranya mungkin bilangan kompleks.Jika 𝑥1 , 𝑥2 , … , 𝑥1 adalah 𝑘 akar-akar (yang berbeda) dari persamaan (2.2.6), maka 𝑎𝑛 = 𝑥𝑖 𝑛 ; 1 ≤ 𝑖 ≤ 𝑘 adalah penyelesaian dari persamaan (2.2.6). Sehingga berdasar Teorema 2.2.2, untuk sebarang konstanta 𝑐̂1 , 𝑐̂2 , … , 𝑐̂𝑘 ;

8

𝑐̂1 𝑥1 𝑛 + 𝑐̂2 𝑥2 𝑛 + ⋯ + 𝑐̂𝑘 𝑥𝑘 𝑛 adalah penyelesaian dari (2.2.1). Dengan demikian solusi umum dari relasi rekursif adalah 𝒂𝒏 = 𝒄̂𝟏 𝒙𝟏 𝒏 + 𝒄̂𝟐 𝒙𝟐 𝒏 + ⋯ + 𝒄̂𝒌 𝒙𝒌 𝒏

(2.2.7)

Dari persamaan (2.2.7) dan 𝑘 kondisi awal akan terbentuk suatu sistem persamaan dengan 𝑘 variabel 𝑐̂1 , 𝑐̂2 , … , 𝑐̂𝑘 . Jika penyelesaian dari sistem persamaan ini kita substitusikan ke persamaan (2.2.7), diperoleh solusi dari relasi rekursif (2.2.1). Contoh Soal. Selesaikan relasi rekursif berikut dengan metode akar-akar karakteristik. a0  0 , a1   1 ; an  7 an1  12 an2 , n  2 1) 2)

a0  a1  1

; an  2 an1  3 an2 , n  2

Penyelesaiannya. a0  0 , a1   1 1)

; an  7 an1  12 an2 , n  2

Misalkan a n  x n

a n  7 a n 1  12 a n  2 x n  7 x n 1  12 x n 2 x 2  7 x  12 x 2  7 x  12  0 x  3x  4  0 x1  3 , x 2  4 Sehingga solusi umum dari relasi rekursif adalah

an  C1 3  C2 4 n

n

Substitusi nilai a0 dan a1 ke persamaan umum relasi rekursif di atas a0  0  0  C1  C 2 a1   1   1  3C1  4C 2

3 1

0  3 C1  3 C 2  1  3 C1  4 C 2 1

  C2

C2   1 C1  C 2  0 C1   1  0 C1  1

Subtitusi nilai C1 dan C2 ke dalam persamaan umum dari relasi rekursif sehingga diperoleh penyelesaian a n  1 3   14  n

n

an  3n  4 n

2) a0  a1  1

; an  2 an1  3 an2 , n  2

Misalkan a n  x n

9

a n  2a n 1  3 a n 2 x n  2 x n1  3 x n 2 x 2  2x  3 x 2  2x  3  0 x  3x  1  0 x1  3 , x 2   1 Sehingga solusi umum dari relasi rekursif adalah

an  C1 3  C2  1 n

n

Substitusi nilai a0 dan a1 ke persamaan solusi umum dari relasi rekursif diatas a0  1  1  C1  C 2

a1  1 1  3C1  C 2 2

 4 C1

C1 

1 2

C1  C 2  0 1  C2  1 2 1 C2  2

Subtitusi nilai C1 dan C2 ke dalam persamaan umum dari relasi rekursif sehingga diperoleh penyelesaian 1 n 1 n a n  3   1 2 2 1 n n a n  3   1 2 Perlu dicatat bahwa untuk setiap 𝑛 ≥ 1, 𝑎𝑛 adalah bilangan bulat non negatif,





walaupun formula dari melibatkan bilangan irasional.

10

Metode Akar Rangkap dari Relasi Rekursif (2.2.6) Penyelesaian Relasi Rekursif dengan Metode Akar Rangkap Misalkan persamaan karakteristik (2.2.6) mempunyai sebuah akar rangkap, katakan 𝑥1 akar rangkap 𝑚 (artinya dari ke-𝑘 akar-akar dari (2.2.6) terdapat 𝑚 akar yang masing-masing 𝑛

nilainya 𝑥1 ). Maka dapat ditunjukkan bahwa masing-masing dari 𝑥1 𝑛 , 𝑛 𝑥1 𝑛 , 𝑛2 𝑥1 , … , 𝑛𝑚−1 𝑥1 𝑛 adalah penyelesaian dari relasi (2.2.1). Ini berarti dengan Teorema 2.2.2, menghasilkan teorema berikut. Teorema 2.2.3 karakteristik (2.2.6) dari relasi rekursif (2.2.1) mempunyai sebuah akar Jika persamaan katakan 𝒙𝟏 , rangkap 𝒎 ≤ 𝒌, maka solusi umum dari (2.2.1) yang melibatkan 𝒙𝟏 mempunyai bentuk: 𝒏

𝒄𝟎 𝒙𝟏 𝒏 + 𝒄𝟏 𝒏 𝒙𝟏 𝒏 + 𝒄𝟐 𝒏𝟐 𝒙𝟏 + ⋯ + 𝒄𝒎−𝟏 𝒏𝒎−𝟏 𝒙𝟏 𝒏

Contoh Soal. (1)

Misalkan kita akan mencari formula solusi untuk 𝑎𝑛 yang memenuhi relasi berikut: 𝑎𝑛 = 3𝑎𝑛−1 + 6𝑎𝑛−2 − 28𝑎𝑛−3 + 24𝑎𝑛−4 Dengan 𝑎0 = 1 ; 𝑎1 = 2 ; 𝑎3 = 3 ; 𝑎4 = 4 Penyelesaiannya. Persamaan karakteristik dari rekursif 𝑥 𝑛 = 3𝑥 𝑛−1 + 6𝑥 𝑛−2 − 28𝑥 𝑛−3 + 24𝑥 𝑛−4 Ruas kiri dan ruas kanan sama-sama dibagi 𝑥 𝑛−4 , diperoleh 𝑥 𝑛−(𝑛−4) = 3𝑥 𝑛−1−(𝑛−4) + 6𝑥 𝑛−2−(𝑛−4) − 28𝑥 𝑛−3−(𝑛−4) + 24𝑥 𝑛−4−(𝑛−4) 𝑥 4 = 3𝑥 3 + 6𝑥 2 − 28𝑥1 + 24𝑥 0 𝑥 4 = 3𝑥 3 + 6𝑥 2 − 28𝑥 + 24 𝑥 4 − 3𝑥 3 − 6𝑥 2 + 28𝑥 − 24 = 0 Ekuivalen dengan (𝑥 − 2)3 (𝑥 + 3) = 0 Sehingga akar-akarnya adalah 𝑥 = 2 (rangkap 3)

atau

𝑥 = −3

Dengan demikian solusi umum dari rekursif di atas adalah

11

𝑎𝑛 = 𝑐0 2𝑛 + 𝑐1 𝑛2𝑛 + 𝑐2 𝑛2 2𝑛 + 𝑐3 (−3)𝑛 Karena 𝑎0 = 1 ; 𝑎1 = 2 ; 𝑎2 = 3 ; 𝑎3 = 4 , maka:  Untuk 𝑎0 = 1 𝑎0 = 𝑐0 . 20 + 𝑐1 . 0. 20 + 𝑐2 . 02 . 20 + 𝑐3 (−3)0 1 = 𝑐0 . 1 + 𝑐1 . 0 + 𝑐2 . 0 + 𝑐3 . 0 1 = 𝑐0 + 𝑐3  Untuk 𝑎1 = 2 𝑎1 = 𝑐0 . 21 + 𝑐1 . 1. 21 + 𝑐2 . 12 . 21 + 𝑐3 (−3)1 2 = 𝑐0 . 2 + 𝑐1 . 2 + 𝑐2 . 2 + 𝑐3 (−3) 2 = 2𝑐0 + 2𝑐1 + 2𝑐2 − 3𝑐3  Untuk 𝑎2 = 3 𝑎2 = 𝑐0 . 22 + 𝑐1 . 2. 22 + 𝑐2 . 22 . 22 + 𝑐3 (−3)2 3 = 𝑐0 . 4 + 𝑐1 . 8 + 𝑐2 . 16 + 𝑐3 . 9 3 = 4𝑐0 + 8𝑐1 + 16𝑐2 + 9𝑐3  Untuk 𝑎3 = 4 𝑎3 = 𝑐0 . 23 + 𝑐1 . 23 + 𝑐2 . 32 . 23 + 𝑐3 (−3)3 4 = 𝑐0 . 8 + 𝑐1 . 24 + 𝑐2 . 72 + 𝑐3 . (−27) 4 = 8𝑐0 + 24𝑐1 + 72𝑐2 − 27𝑐3 Maka diperoleh: 𝑐0 + 𝑐3 = 1 (i) 2𝑐0 + 2𝑐1 + 2𝑐2 − 3𝑐3 = 2 (ii) 4𝑐0 + 8𝑐1 + 16𝑐2 + 9𝑐3 = 3 (iii) 8𝑐0 + 24𝑐1 + 72𝑐2 − 27𝑐3 = 4 (iv Penyelesaian persamaan: 𝑐0 + 𝑐3 = 1 𝑐3 = 1−𝑐0 (v) Substitusikan (v) ke (ii) 2𝑐0 + 2𝑐1 + 2𝑐2 − 3(1 − 𝑐0 ) = 2 2𝑐0 + 2𝑐1 + 2𝑐2 − 3 + 3𝑐0 = 2 5𝑐0 + 2𝑐1 + 2𝑐2 = 5 (𝑣𝑖) Substitusikan (v) ke (iii) 4𝑐0 + 8𝑐1 + 16𝑐2 + 9(1 − 𝑐0 ) = 3 4𝑐0 + 8𝑐1 + 16𝑐2 + 9 − 9𝑐0 = 3 −5𝑐0 + 8𝑐1 + 16𝑐2 = −6 (𝑣𝑖𝑖) Substitusikan (v) ke (iv) 8𝑐0 + 24𝑐1 + 72𝑐2 − 27(1 − 𝑐0 ) = 4

12

8𝑐0 + 24𝑐1 + 72𝑐2 − 27 + 27𝑐0 = 4 35𝑐0 + 24𝑐1 + 72𝑐2 = 31 (𝑣𝑖𝑖𝑖) Eliminasi 𝑐0 dari (vi) dan (vii) 5𝑐0 + 2𝑐1 + 2𝑐2 = 5 −5𝑐0 + 8𝑐1 + 16𝑐3 = −6 10𝑐1 + 18𝑐2 = −1 (ix) Eliminasi 𝑐0 dari (vi) dan (viii) 5𝑐0 + 2𝑐1 + 2𝑐2 = 5 (× 7) 35𝑐0 + 24𝑐1 + 72𝑐2 = 31 35𝑐0 + 14𝑐1 + 14𝑐2 = 35 35𝑐0 + 24𝑐1 + 72𝑐2 = 31 −10𝑐1 − 58𝑐2 = 4 (x) Eliminasi 𝑐1 dari (ix) dan (x) 10𝑐1 + 18𝑐2 = −1 −10𝑐1 − 58𝑐2 = 4 −40𝑐2 = 3 𝑐2 = −

3 40

3

Substitusi 𝑐2 = − 40 ke (ix) 3 ) = −1 40 27 10𝑐1 − = −1 20

10𝑐1 + 18 (−

10𝑐1 = −1 + 7 20 7 𝑐1 = 200

27 20

10𝑐1 =

7

3

Substitusi 𝑐1 = 200 dan 𝑐2 = 40 ke (vi) 7 3 ) + 2 (− ) = 5 200 40 7 3 5𝑐0 + ( )−( )=5 100 20 2 5𝑐0 − ( ) = 5 25

5𝑐0 + 2 (

5𝑐0 = 5 + ( 𝑐0 =

127 125

2 ) 25

13 127

Substitusi 𝑐1 = 125 ke (v) 127 125 2 𝑐3 = − 125 𝑐3 = 1 −

Maka diperoleh 1 7 3 2 ; 𝑐1 = ; 𝑐2 = − ; 𝑐3 = − 125 200 40 125 Substitusikan nilai 𝑐0 , 𝑐1 , 𝑐2 , 𝑑𝑎𝑛𝑐3 ke persamaan 1 𝑛 7 3 2 (−3)𝑛 𝑎𝑛 = 1 2 + 𝑛2𝑛 − 𝑛2 2𝑛 − 125 200 40 125 𝑐0 = 1

(2). Selesaikan relasi rekursif berikut dengan metode akar rangkap. a. a1  2 , a 2  6 b.

; a n  4 a n1  4 a n 2  0 , n  3

a 0  0 , a1  1 , a 2  2 ; a n  9 a n  1  15 a n  2  7 a n  3 , n  3

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 c. Penyelesaiannya. a.

a1  2 , a2  6 Misalkan

; an  4 an1  4 an2  0 , n  3

an  x n

a n  4 a n 1  4 a n 2  0 x n  4 x n 1  4 x n 2  0 x 2  4x  4  0

 x  2 2

0

x1, 2  2 Sehingga solusi umum dari relasi rekursif adalah

a n  C0 2  C1 . n. 2 n

n

Substitusi nilai a1 dan a2 ke persamaan solusi umum dari relasi rekursif diatas

a1  2  2  2C 0  2C 1 a 2  6  6  4C 0  8C1

2 1

4  4 C 0  4 C1 6  4 C 0  8 C1

 2   4 C2 C1 

1 2

14

2 C 0  2 C1  2 1 2 C0  2    2 2 2 C0  1 C0 

1 2

Subtitusi nilai C1 dan C2 ke dalam persamaan umum dari relasi rekursif sehingga diperoleh penyelesaian

1 n 1 2  . n . 2n 2 2 1 a n  2 n 1  n  2 a n  2 n 1 1  n 

an 

b.

a 0  0 , a1  1 , a 2  2 ; a n  9 a n  1  15 a n  2  7 a n  3 , n  3

Misalkan

an  x n

a n  9 a n  1  15 a n  2  7 a n  3 x n  9 x n  1  15 x n  2  7 x n  3 x 3  9 x 2  15 x  7 x 3  9 x 2  15 x  7  0

x  12 x  7   0 x1, 2  1 , x 3  7

Sehingga solusi umum dari relasi rekursif adalah an 

C 0 1  C1 . n. 1 n

n

 C 2 7 

n

Substitusi nilai a0 , a1 dan a2 ke persamaan solusi umum dari relasi rekursif diatas a0  0  0  C0  C2  C2   C0 a1  1  1  C 0  C1  7 C 2 a 2  2  2  C 0  2 C1  49 C 2

................ (i)

................. ii 

................. iii 

Substitusi persamaan (i) ke persamaan (ii) dan (iii) sehingga diperoleh

 6 C 0  C1  1

............ (iv )

 48 C 0  2 C1  2 ........... (v) Eliminasi persamaan (iv) dan (v)  6 C 0  C1  1  2  12 C 0  2 C1  2  48 C 0  2 C1  2  1  48 C 0  2 C1  2

15 36 C 0  0 C0  0

Substitusi nilai C0 ke persamaan (i) dan (iv) sehingga diperoleh C2 = 0 dan C1 = 1 Subtitusi nilai C0, C1 dan C2 ke dalam persamaan umum dari relasi rekursif sehingga diperoleh penyelesaian a n  0  n . 1  0 7

n

an  n

c.

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

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

............. (1)

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

.............. (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)

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

16

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

2.

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

Relasi Rekursif Linear NonHomogen dengan Koefisien Konstanta Bentuk umum dari relasi rekursif linear tidak homogen dengan koefisien konstanta adalah sebagai berikut. 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 𝑓(𝑛); 𝑐𝑘 ≠ 0, 𝑓(𝑛) ≠ 0, Dengan 𝑘 kondisi awal (syarat batas), dan untuk 1 ≤ 𝑖 ≤ 𝑘, 𝑐𝑖 = 𝑘𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑎. Kasus 1 Bila𝑓(𝑛) merupakan suatu polinom berderajat t di dalam n yaitu: 𝐴1 𝑛𝑡 + 𝐴2 𝑛𝑡−1 + ⋯ + 𝐴𝑡 𝑛 + 𝐴𝑡+1 ............... (1) Maka bentuk umum solusi khususnya, yaitu: 𝑎𝑛 = 𝐵1 𝑛𝑡 + 𝐵2 𝑛𝑡−1 + ⋯ + 𝐵𝑡 𝑛 + 𝐵𝑡+1 ................. (2) Contoh: Misalkan kita akan mencari solusi khusus untuk relasi rekursif tidak homogen 𝑎𝑛 + 5𝑎𝑛−1 + 6𝑎𝑛−2 = 3𝑛2 − 2𝑛 + 1 Solusi khususnya mempunyai bentuk 𝐵1 𝑛2 + 𝐵2 𝑛 + 𝐵3 Dengan mensubstitusikan (2) ke dalam (1), maka kita peroleh: (𝐵1 𝑛2 + 𝐵2 𝑛 + 𝐵3 ) + 5(𝐵1 (𝑛 − 1)2 + 𝐵2 (𝑛 − 1) + 𝐵3 ) + 6(𝐵1 (𝑛 − 2)2 + 𝐵2 (𝑛 − 2) + 𝐵3 ) = 3𝑛2 − 2𝑛 + 1 Setelah disederhanakan menjadi: 12𝐵1 𝑛2 − (34𝐵1 + 3𝐵2 )𝑛 + (29𝐵1 − 3𝐵2 + 3𝐵3 ) = 3𝑛2 − 2𝑛 + 1...............(3) Dengan membandingkan koefisien kedua ruas (3), kita memperoleh persamaanpersamaan: 12𝐵1 = 3 34𝐵1 + 3𝐵2 = 2 29𝐵1 − 3𝐵2 + 3𝐵3 = 1

17

Yang menghasilkan 1

𝐵1 = 4 ; 𝐵2 =

−13 2

; 𝐵3 =

−103 4

Jadi, solusi khususnya adalah 1

𝑎𝑛 (𝑃) = 4 𝑛2 +

−13 2

𝑛+

−103 4

Kasus 2 Bila 𝑓(𝑛) berbentuk 𝛽 𝑛 , maka solusi khususnya akan berbentuk umum 𝐵𝛽 𝑛 , dengan syarat 𝛽 bukan akar karakteristik relasi rekursif tersebut.

Contoh: Misalkan kita akan mencari solusi khusus untuk relasi rekursif tidak homogen 𝑎𝑛 + 5𝑎𝑛−1 + 6𝑎𝑛−2 = 42. 4𝑛 .......................... (1) Solusi khususnya mempunyai bentuk umum 𝐵. 4𝑛 .......................... (2) Dengan mensubstitusikan (2) ke dalam (1), maka kita peroleh: 𝐵. 4𝑛 + 5𝐵. 4𝑛−1 + 6𝐵. 4𝑛−2 = 42.4𝑛 ↔ 𝐵. 4𝑛 + 5𝐵. 4𝑛 . 4−1 + 6𝐵. 4𝑛 . 4−2 = 42.4𝑛 5

6

↔ 𝐵. 4𝑛 + 4 . 𝐵. 4𝑛 + 16 . 𝐵. 4𝑛 = 42.4𝑛 ↔

42 16

. 𝐵. 4𝑛 = 42.4𝑛

↔ 𝐵 = 16 Jadi, solusi khususnya adalah 𝑎𝑛 (𝑃) = 16.4𝑛 1) Misalkan kita akan mencari solusi khusus untuk relasi rekursif tidak homogen 𝑎𝑛 − 6𝑎𝑛−1 + 9𝑎𝑛−2 = 3𝑛 .......... (1) Persamaan karakteristiknya: 𝑥 2 − 6𝑥 + 9 = 3𝑛 ↔ (𝑥 − 3)2 = 3𝑛 Ternyata 3 merupakan akar karakteristik kembarnya. Karena itu bentuk umum solusi khususnya adalah 𝐵𝑛2 . 3𝑛 .......... (2) Dengan mensubstitusikan (2) ke dalam (1), maka kita peroleh:

18

𝐵𝑛2 . 3𝑛 − 6𝐵(𝑛 − 1)2 . 3𝑛−1 + 9𝐵(𝑛 − 2)2 . 3𝑛−2 = 3𝑛 ↔ 𝐵𝑛2 . 3𝑛 − 6𝐵(𝑛2 − 2𝑛 + 1). 3𝑛 . 3−1 + 9𝐵(𝑛2 − 4𝑛 + 4). 3𝑛 . 3−2 = 3𝑛 ↔ 𝐵𝑛2 . 3𝑛 − 2𝐵𝑛2 . 3𝑛 + 4𝐵𝑛. 3𝑛 − 2𝐵. 3𝑛 + 𝐵𝑛2 . 3𝑛 − 4𝐵𝑛. 3𝑛 + 4𝐵. 3𝑛 = 3𝑛 ↔ 2𝐵. 3𝑛 = 3𝑛 1

↔𝐵=2 Jadi, solusi khususnya adalah 1

𝑎𝑛 (𝑃) = 2 𝑛2 . 3𝑛

2.3

Menyelesaikan Relasi Rekursif dengan Fungsi Pembangkit

Pada bagian ini akan kita bahas penyelesaian RR dengan Fungsi Pembangkit. Agar dapat dibandingkan, kita gunakan contoh yang sama dengan contoh pertama dalam penyelesaian RR dengan Metode Akar Karakteristik. Contoh 1.

Selesaikan relasi rekursif berikut dengan fungsi pembangkit eksponen 𝑎𝑛 − 9𝑎𝑛−1 + 20𝑎𝑛−2 = 0, dengan 𝑎0 = −3 dan 𝑎1 = −10 Penyelesaian: 𝑎𝑛 = 9𝑎𝑛−1 − 20𝑎𝑛−2 𝑛 Misal: 𝑃(𝑥) = ∑∞ 𝑛=0 𝑎𝑛 𝑥

Kalikan kedua ruas dengan 𝑥 𝑛 kemudian dijumlahkan untuk 𝑛 = 2 sampai 𝑛 = ∞ sehingga diperoleh ∞

∞

∞

𝑛

∑ 𝑎𝑛 𝑥 = ∑ 9𝑎𝑛−1 𝑥 − ∑ 20𝑎𝑛−2 𝑥 𝑛 𝑛=2

𝑛

𝑛=2

𝑛=2

 Ruas kiri dari persamaan (i) ∞

∞ 𝑛

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

𝑛=0

= 𝑃(𝑥) + 3 + 10𝑥  Suku pertama ruas kanan dari persamaan (i) ∞

∞ 𝑛

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

𝑛=2 ∞

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

(𝑖)

19 ∞

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

= 9𝑥(𝑃(𝑥) + 3) = 9𝑥 ∙ 𝑃(𝑥) + 27𝑥  Suku kedua ruas kanan dari persamaan (i) ∞

∞

∑ 20𝑎𝑛−2 𝑥 𝑛 = 20 ∑ 𝑎𝑛−2 𝑥 𝑛 𝑛=2

𝑛=2 ∞ 2

= 20𝑥 ∑ 𝑎𝑛−2 𝑥 𝑛−2 𝑛=2

= 20𝑥 2 ∙ 𝑃(𝑥) Sehingga, ∞

∞

∑ 𝑎𝑛 𝑥

𝑛

∞ 𝑛

= ∑ 9𝑎𝑛−1 𝑥 − ∑ 20𝑎𝑛−2 𝑥 𝑛

𝑛=2

𝑛=2

𝑛=2

= 9𝑥 ∙ 𝑃(𝑥) + 27𝑥 − 20𝑥 2 ∙ 𝑃(𝑥)

𝑃(𝑥) + 3 + 10𝑥

𝑃(𝑥) − 9𝑥 ∙ 𝑃(𝑥) + 20𝑥 2 ∙ 𝑃(𝑥) = 27𝑥 − 10𝑥 − 3 𝑃(𝑥)(1 − 9𝑥 + 20𝑥 2 ) = 17𝑥 − 3

17𝑥 − 3 𝑎 𝑏 = + (1 − 5𝑥)(1 − 4𝑥) 1 − 5𝑥 1 − 4𝑥

17𝑥 − 3 𝑃(𝑥) = 1 − 9𝑥 + 20𝑥 2 17𝑥−3

=

𝑃(𝑥) = (1−5𝑥)(1−4𝑥) 𝑃(𝑥) =

2 5 − 1 − 5𝑥 1 − 4𝑥

∞

∞ 𝑛

=

𝑛=0

∑ 𝑎𝑛 𝑥

𝑛 𝑛

𝑛=0

∞

𝑛=0

∞ 𝑛

𝑎 − 4𝑎𝑥 + 𝑏 − 5𝑏𝑥 (1 − 5𝑥)(1 − 4𝑥)

∞

∑ 𝑎𝑛 𝑥 = 2 ∑ 5 𝑥 − 5 ∑ 4𝑛 𝑥 𝑛

𝑛=0

𝑎(1 − 4𝑥) + 𝑏(1 − 5𝑥) (1 − 5𝑥)(1 − 4𝑥)

𝑛

𝑛)

= ∑(2 ∙ 5 − 5 ∙ 4

𝑥

𝑛

𝑛=0

=

𝑎 + 𝑏 + (−4𝑎 − 5𝑏)𝑥 (1 − 5𝑥)(1 − 4𝑥)

𝑎 + 𝑏 = −3 −4𝑎 − 5𝑏 = 17

Dengan metode eliminasi substitusi diperoleh nilai 𝑎 = 2 dan 𝑏 = −5

Karena 𝑎𝑛 adalah koefisien 𝑥𝑛 dalam 𝑃(𝑥), maka penyelesaian relasi rekursif yang dimaksud adalah 𝑎𝑛 = 2 ∙ 5𝑛 − 5 ∙ 4𝑛 2.

Selesaikan relasi rekursif berikut dengan fungsi pembangkit eksponen 𝑎0 = 2, 𝑎𝑛 = 2𝑛 𝑎𝑛−1 + 4𝑛 dengan 𝑛 ≥ 1.

20

Penyelesaian: Misal : 𝑃(𝑥) = ∑∞ 𝑛=0 𝑎𝑛

𝑥𝑛 𝑛!

Kalikan kedua ruas dengan

𝑥𝑛 𝑛!

kemudian dijumlahkan untuk 𝑛 = 1 sampai 𝑛 = ∞

∞

∞

∞

𝑛=1

𝑛=1

𝑛=1

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

 Ruas kiri ∞

∞

𝑛=1

𝑛=0

𝑥𝑛 𝑥𝑛 𝑥0 ∑ 𝑎𝑛 = ∑ 𝑎𝑛 − 𝑎0 𝑛! 𝑛! 0! ∞

= ∑ 𝑎𝑛 𝑛=0

𝑥𝑛 − 𝑎0 𝑛!

= 𝑃(𝑥) − 2  Suku pertama Ruas kanan ∞

∞

𝑛=1

𝑛=1

𝑥𝑛 𝑥𝑛 ∑ 2𝑛 𝑎𝑛−1 = 2 ∑ 𝑛𝑎𝑛−1 𝑛! 𝑛! ∞

𝑥 𝑛−1 = 2𝑥 ∑ 𝑎𝑛−1 (𝑛 − 1)! 𝑛=1

= 2𝑥 ∙ 𝑃(𝑥)  Suku kedua Ruas kanan ∞

∞

𝑥𝑛 𝑥𝑛 𝑥0 𝑛 𝑛 0 ∑4 = ∑4 −4 𝑛! 𝑛! 0!

𝑛=1

∞

=∑ 𝑛=0

𝑛=0

(4𝑥)𝑛 −1 𝑛!

= 𝑒 4𝑥 − 1 Sehingga ∞

∞

∞

𝑛=1

𝑛=1

𝑛=1

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

𝑃(𝑥) − 2 = 2𝑥 ∙ 𝑃(𝑥) + 𝑒 4𝑥 − 1 𝑃(𝑥) − 2𝑥 ∙ 𝑃(𝑥) = 𝑒 4𝑥 − 1 + 2 𝑃(𝑥) (1 − 2𝑥)

= 𝑒 4𝑥 + 1

21

𝑃(𝑥)

1 + 𝑒 4𝑥 = 1 − 2𝑥

𝑃(𝑥)

1 𝑒 4𝑥 = + 1 − 2𝑥 1 − 2𝑥 ∞

∞

∞

𝑛

𝑛

= ∑(2𝑥) + ∑(2𝑥) ∑ 4𝑛 𝑛=0

𝑛=0

∞

∞

𝑛=0

𝑥𝑛 𝑛!

∞

4𝑛 𝑥 𝑛 = ∑2 𝑥 +∑2 𝑥 ∑ 𝑛! 𝑛 𝑛

𝑛 𝑛

𝑛=0

𝑛=0

∞

∞

𝑛=0

𝑛

= ∑ 2𝑛 𝑥 𝑛 + ∑ (∑ 𝑛=0

𝑛=0 𝑛

∞

= ∑ (2𝑛 + ∑ 𝑛=0

𝑘=0

𝑘=0

2𝑘 4𝑘 𝑛 )𝑥 𝑘!

2𝑘 4𝑘 𝑛 )𝑥 𝑘! 𝑛

∞

2𝑘 4𝑘 𝑥 𝑛 = ∑ 𝑛! (2 + ∑ ) 𝑘! 𝑛! 𝑛

𝑛=0

𝑘=0

Jadi, solusinya adalah 𝑛 𝑛

𝑎𝑛 = 𝑛! (2 + ∑ 𝑘=0

3.

2𝑘 4𝑘 ) 𝑘!

Selesaikan RR berikut dengan Fungsi Pembangkit Biasa. 𝑎0 = 0, 𝑎1 = −1, dan 𝑎𝑛 = 7𝑎𝑛−1 − 12𝑎𝑛−2 , 𝑛 ≥ 2

Penyelesaian: 𝑛 Misalkan 𝑃(𝑥) = ∑∞ 𝑛=0 𝑎𝑛 𝑥

Kalikan setiap suku pada bagian rekursif dengan 𝑥 𝑛 , kemudian ambil sigmanya dari n = 2 sampai ∞, sehingga diperoleh: ∞

∞ 𝑛

∞

∑ 𝑎𝑛 𝑥 = ∑ 7𝑎𝑛−1 𝑥 − ∑ 12𝑎𝑛−2 𝑥 𝑛 𝑛=2

𝑛

𝑛=2

𝑛=2

Selanjutnya, kita usahakan untuk merubah setiap ekspresi sigma menjadi ekspresi yang melibatkan P(x) atau ekspresi-ekspresi lain yang telah kita daftarkan pada Bab VI. Agar proses perubahan lebih mudah dimengerti, maka kita akan melakukannya satu persatu. ∞ ∞ 𝑛 𝑛 𝑛 a. ∑∞ 𝑛=2 𝑎𝑛 𝑥 = ∑𝑛=0 𝑎𝑛 𝑥 − 𝑎0 − 𝑎1 𝑥 = ∑𝑛=0 𝑎𝑛 𝑥 − 0 + 𝑥 = 𝑃(𝑥) + 𝑥 ∞ 𝑛 𝑛−1 𝑛−1 b. ∑∞ = 7𝑥[∑∞ − 𝑎0 ] = 7𝑥[𝑃(𝑥) − 0] = 𝑛=2 7𝑎𝑛−1 𝑥 = 7𝑥 ∑𝑛=2 𝑎𝑛−1 𝑥 𝑛=1 𝑎𝑛−1 𝑥

7𝑥𝑃(𝑥)

22 𝑛 2 ∞ 𝑛−2 c. ∑∞ = 12𝑥 2 𝑃(𝑥) 𝑛=2 12𝑎𝑛−2 𝑥 = 12𝑥 ∑𝑛=2 𝑎𝑛−2 𝑥

Diperoleh: 𝑃(𝑥) + 𝑥 = 7𝑥𝑃(𝑥) − 12𝑥 2 𝑃(𝑥) (1 − 7𝑥 + 12𝑥 2 )𝑃(𝑥) = −𝑥 −𝑥 𝑃(𝑥) = 1 − 7𝑥 + 12𝑥 2 −𝑥 𝑃(𝑥) = (1 − 4𝑥)(1 − 3𝑥) Menggunakan kesamaan fungsi Aljabar, bentuk terakhir dapat kita nyatakan dalam bentuk:

𝑃(𝑥) = 𝑃(𝑥) =

−𝑥 (1−4𝑥)(1−3𝑥) −𝑥 (1−4𝑥)(1−3𝑥)

=

=

𝐴 1−4𝑥

+

𝐵 1−3𝑥

𝐴(1−3𝑥)+𝐵(1−4𝑥) (1−4𝑥)(1−3𝑥)

=

𝐴−3𝐴𝑥+𝐵−4𝐵𝑥 (1−4𝑥)(1−3𝑥)

=

(−3𝐴−4𝐵)𝑥+(𝐴+𝐵) (1−4𝑥)(1−3𝑥)

Dengan menyelesaikan persamaan untuk koefisien ruas kiri dan ruas kanan, diperoleh 𝐴 = −1 dan 𝐵 = 1 (coba jelaskan), sehingga: 𝑃(𝑥) =

−1 1 + 1 − 4𝑥 1 − 3𝑥 ∞

∞

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

Karena pada awalnya kita memisalkan 𝑃(𝑥) = diperoleh solusi khusus dari RR, yaitu:

𝑛=0 𝑛 ∑∞ 𝑛=0 𝑎𝑛 𝑥 ,

maka dari ekspresi terakhir

𝑎𝑛 = −4𝑛 + 3𝑛 = 3𝑛 − 4𝑛 . Setelah melalui

proses yang cukup panjang, diperoleh hasil yang sama dengan hasil pada latihan 1 metode karakteristik halaman 6.

23

BAB III PENUTUP 3.1 1.

Kesimpulan Relasi rekursif adalah suatu topik penting dan menarik dalam kombinatorik. Banyak permasalahan dalam matematika, khususnya kombinatorik dapat dimodelkan kedalam bentuk relasi rekursif. Misalkan Pn menyatakan banyaknya permutasi dari n obyek berbeda. Jelas P1=1 karena hanya ada satu permutasi dari 1 obyek. Untuk n ≥ 2, Pn diperoleh dengan cara berikut:Terdapat kemungkinan posisi dari obyek tertentu, dan setiap kemungkinan posisi dari obyek ini akan diikuti oleh permutasi dari n-1 obyek. Karena banyaknya permutasi dari n-1 obyek ini adalah Pn-1 maka terdapat hubungan Pn = Pn-1Dengan demikan,

P1 = 1; Pn = Pn-1, n ≥ 2

(2.1.1)

Bentuk (2.1.1) di sebut relasi rekursif untuk Pn, banyak permutasi dari n obyek, P1 = 1 di sebut kondisi awal sedangkan Pn = Pn-1 disebut bagian rekursif dari relasi rekursif tersebut. 2.

Bentuk umum Bagian Rekursif dari RR linear berderajat 𝑘 berbentuk: 𝑎𝑛 + ℎ1 (𝑛) 𝑎𝑛−1 + ℎ2 (𝑛) 𝑎𝑛−2 + … + ℎ𝑘 (𝑛) 𝑎𝑛−𝑘 = 𝑓(𝑛), yang mana ℎ𝑖(𝑛) dan 𝑓(𝑛) adalah fungsi dalam n dan ℎ𝑘 (𝑛) ¹ 0

3.

Bentuk umum dari relasi rekursif linear homogen dengan koefisien konstanta adalah sebagai berikut: 𝒂𝒏 +awal. 𝒄𝟏 𝒂𝒏−𝟏 + ⋯+ 𝒄𝒌 𝒂𝒏−𝒌 𝟎 ;𝒌,𝒄𝒄𝒌 ≠ 𝟎 (2.2.1) dan 𝒌 adalah kondisi Dimana untuk 𝟏 ≤= 𝒊≤ 𝒊 = konstanta. Pada bagian ini akan dikembangkan suatu teknik untuk menyelesaikan relasi rekursif (2.2.1). Untuk maksud tersebut diperlukan teorema berikut.

Teorema 2.2.1 (Prinsip Superposisi) Jika 𝒈𝟏 (𝒏) dan 𝒈𝟐 (𝒏) berturut-turut adalah solusi dari 𝒂𝒏 + 𝒄𝟏 𝒂𝒏−𝟏 + 𝒄𝟐 𝒂𝒏−𝟐 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌 = 𝒇𝟏 (𝒏)

(2.2.2)

dan 𝒂𝒏 + 𝒄𝟏 𝒂𝒏−𝟏 + 𝒄𝟐 𝒂𝒏−𝟐 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌 = 𝒇𝟐 (𝒏)

(2.2.3)

maka untuk sebarang konstanta 𝒄̂𝟏 dan 𝒄̂𝟐 , 𝒄̂𝟏 𝒈𝟏 (𝒏) + 𝒄̂𝟐 𝒈𝟐 (𝒏) adalah solusi dari 𝒂𝒏 + 𝒄𝟏 𝒂𝒏−𝟏 + ⋯ + 𝒄𝒌 𝒂𝒏−𝒌 = 𝒄̂𝟏 𝒇𝟏 (𝒏) + 𝒄̂𝟐 𝒇𝟐 (𝒏)

(2.2.4)

24

4.

Persamaan (2.2.6) disebut persamaan karakteristik dari relasi rekursif (2.2.1). Pada umumnya persamaan (2.2.6) menjadi 𝑘 akar, beberapa di antaranya mungkin bilangan kompleks.Jika 𝑥1 , 𝑥2 , … , 𝑥1adalah 𝑘 akar-akar (yang berbeda) dari persamaan (2.2.6), maka 𝑎𝑛 = 𝑥𝑖 𝑛 ; 1 ≤ 𝑖 ≤ 𝑘 adalah penyelesaian dari persamaan (2.2.6). Sehingga berdasar Teorema 2.2.2, untuk sebarang konstanta 𝑐̂1 , 𝑐̂2 , … , 𝑐̂𝑘 ; 𝑐̂1 𝑥1 𝑛 + 𝑐̂2 𝑥2 𝑛 + ⋯ + 𝑐̂𝑘 𝑥𝑘 𝑛 adalah penyelesaian dari (2.2.1). Dengan demikian solusi umum dari relasi rekursif adalah 𝒂𝒏 = 𝒄̂𝟏 𝒙𝟏5.𝒏 + 𝒄̂𝟐 𝒙𝟐 𝒏 + ⋯ + 𝒄̂𝒌 𝒙𝒌 𝒏

(2.2.7)

Dari persamaan (2.2.7) dan 𝑘 kondisi awal akan terbentuk suatu sistem persamaan dengan 𝑘 variabel 𝑐̂1 , 𝑐̂2 , … , 𝑐̂𝑘 . Jika penyelesaian dari sistem persamaan ini kita substitusikan ke persamaan (2.2.7), diperoleh solusi dari relasi rekursif (2.2.1). 5.

Penyelesaian Relasi Rekursif dengan Metode Akar Rangkap Misalkan persamaan karakteristik (2.2.6) mempunyai sebuah akar rangkap, katakan 𝑥1 akar rangkap 𝑚 (artinya dari ke-𝑘 akar-akar dari (2.2.6) terdapat 𝑚 akar yang masing-masing nilainya 𝑥1 ). Maka dapat ditunjukkan bahwa masing-masing dari 𝑥1 𝑛 , 𝑛

𝑛 𝑥1 𝑛 , 𝑛2 𝑥1 , … , 𝑛𝑚−1 𝑥1 𝑛 adalah penyelesaian dari relasi (2.2.1). Ini berarti dengan Teorema 2.2.2, menghasilkan teorema berikut. Teorema 2.2.3 Jika persamaan karakteristik (2.2.6) dari relasi rekursif (2.2.1) mempunyai sebuah akar katakan 𝒙𝟏 , rangkap 𝒎 ≤ 𝒌, maka solusi umum dari (2.2.1) yang melibatkan 𝒙𝟏 mempunyai bentuk: 𝒏

𝒄𝟎 𝒙𝟏 𝒏 + 𝒄𝟏 𝒏 𝒙𝟏 𝒏 + 𝒄𝟐 𝒏𝟐 𝒙𝟏 + ⋯ + 𝒄𝒎−𝟏 𝒏𝒎−𝟏 𝒙𝟏 𝒏

6.

Relasi Rekursif Linear NonHomogen dengan Koefisien Konstanta Bentuk umum dari relasi rekursif linear tidak homogen dengan koefisien konstanta adalah sebagai berikut. 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 𝑓(𝑛); 𝑐𝑘 ≠ 0, 𝑓(𝑛) ≠ 0, Dengan 𝑘 kondisi awal (syarat batas), dan untuk 1 ≤ 𝑖 ≤ 𝑘, 𝑐𝑖 = 𝑘𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑎.

25

Kasus 1 Bila𝑓(𝑛) merupakan suatu polinom berderajat t di dalam n yaitu: 𝐴1 𝑛𝑡 + 𝐴2 𝑛𝑡−1 + ⋯ + 𝐴𝑡 𝑛 + 𝐴𝑡+1 ............... (1) Maka bentuk umum solusi khususnya, yaitu: 𝑎𝑛 = 𝐵1 𝑛𝑡 + 𝐵2 𝑛𝑡−1 + ⋯ + 𝐵𝑡 𝑛 + 𝐵𝑡+1 ................. (2)

Kasus 2 Bila 𝑓(𝑛) berbentuk 𝛽 𝑛 , maka solusi khususnya akan berbentuk umum 𝐵𝛽 𝑛 , dengan syarat 𝛽 bukan akar karakteristik relasi rekursif tersebut.

7.

Menyelesaikan Relasi Rekursif dengan Fungsi Pembangkit penyelesaian RR dengan Fungsi Pembangkit dapat dilihat pada halaman 18