Matematika Diskrit : Penyelesaian Relasi Rekurensi dengan Persamaan Karakteristik

Penyelesaian dengan Persamaan Karakteristik

Misalkan n dan k adalah bilangan-bilangan bulat tidak negatif dengan nโ‰ฅk. Relasi rekurensi linier derajat k adalah relasi berbentuk:

c0(n) an + c1(n) an-1 + โ€ฆ + ck(n) an-k = f(n), c0(n) dan ck(n) โ‰  0

Jika c0(n), c1(n), โ€ฆ, ck(n) semuanya konstanta, maka relasi rekurensi disebut relasi rekurensi linier dengan koefisien konstan.

Jadi, relasi rekurensi linier dengan koefisien konstan adalah:
c0 an + c1 an-1 + โ€ฆ + ck an-k = f(n)

Apabila dalam persamaan tersebut, f(n) = 0, maka disebut relasi rekurensi homogen linier dengan koefisien konstan.


CONTOH

Tentukan apakah persamaan di bawah ini merupakan relasi rekurensi linier, linier dengan koefisien konstan atau homogen linier dengan koefisien konstan. Jika demikian, tentukan derajatnya!

a. an โ€“ 7an-1 + 10an-2 = 0

b. bk = bk-1 + bk-2 + bk-3

c. ck = 2ck-2

d. dk = dk-12 + dk-2

e. ek = ek – 1 โ€ข ek-2

f. fk โ€“ 2fk-1 + 1 = 0

g. hk = -hk-1 + (k-1) hk-2

Penyelesaian

a. Relasi rekurensi homogen linier dengan koefisien konstan derajat 2

b. Relasi (b) dapat dinyatakan dengan bk โ€“ bk-1 โ€“ bk-2 โ€“ bk-3 = 0, yang merupakan relasi rekurensi homogen linier dengan koefisien konstan derajat 3

c. Relasi rekurensi homogen linier dengan koefisien konstan derajat 2

d. Bukan relasi rekurensi linier karena memuat suku kuadratis dk-12

e. Bukan relasi rekurensi linier karena memuat pergandaan suku (ek-1 โ€ข ek-2)

f. Relasi rekurensi linier dengan koefisien konstan derajat 1(f(n) = -1)

g. Relasi rekurensi linier dengan derajat 2 (koefisien tidak konstan).


Relasi Rekurensi Homogen Linier dengan Koefisien Konstan

Misalkan diberikan suatu relasi rekurensi homogen linier dengan koefisien konstan:

an + c1 an-1 + โ€ฆ + ck an-k = 0, ck โ‰  0 dan n โ‰ฅ k

Persamaan karakteristik yang sesuai dengan relasi rekurensi tersebut adalah:

tk + c1 tk-1 + โ€ฆ + ck = 0

Solusi persamaan karakteristik disebut akar-akar karakteristik, dan merupakan komponen solusi relasi
rekurens yang kita cari.


Misalkan ฮฑ1, ฮฑ2, โ€ฆ, ฮฑk adalah akar-akar karakteristik dari persamaan karakteristik atas. Ada 2 kemungkinan akar, yakni sebagai berikut :

Semua akar berbeda

Penyelesaiannya: an = c1 ฮฑ1n + c2 ฮฑ2n + โ€ฆ + ck ฮฑkn,dengan c1, c2, โ€ฆ , ck adalah konstanta yang nilainya
ditentukan berdasarkan kondisi awal.

Ada akar yang kembar

Misalkan terdapat p buah akar yang sama.

Jadi, akar-akarnya adalah: ฮฑ1 = ฮฑ2 = โ€ฆ = ฮฑp, ฮฑp+1, โ€ฆ, ฮฑk

Maka penyelesaian relasi rekurensi tersebut:

an = (c1 + c2n +โ€ฆ+ cpnp-1) ฮฑ1n + cp+1 ฮฑp+1n + โ€ฆ + ckฮฑkn


CONTOH 1

Selesaikan relasi rekurensi di bawah ini lewat persamaan karakteristiknya

an = 3an-1 + 4an-2 untuk n โ‰ฅ 2 dengan kondisi awal a0 = 1 dan a1 = 3.

Penyelesaian

Relasi rekurensi an – 3an-1 – 4an-2 = 0 merupakan relasi rekurensi homogen linier dengan koefisien konstan.

Persamaan karakteristik yang sesuai adalah t2 – 3t -4 = (t-4)(t+1) = 0 yang mempunyai akar-akar karakteristik ฮฑ1 = 4 dan ฮฑ2 = -1

Karena semua akar-akar karakteristik berbeda, maka penyelesaiannya adalah:

an = c1 4n + c2 (-1)n

Untuk menentukan c1 dan c2, digunakan kondisi awal :

a0 = 1 sehingga 1 = c1 (4)0 + c2 (-1)0

1 = c1 + c2

a1 = 3 sehingga 3 = c1 (4)1 + c2 (-1)1

3 = 4c1 – c2

Didapat sistem persamaan linier :

c1 + c2 = 1

4c1 – c2 = 3

yang mempunyai penyelesaian c1 = โ…˜ dan c2 = โ…•

Maka, penyelesaian relasi rekurensi an – 3an-1 – 4an-2 = 0 adalah an = โ…˜ (4)n + โ…• (-1)n


CONTOH 2

Selesaikan relasi rekurensi di bawah ini lewat persamaan karakteristiknya

an โ€“ 3 an-1 + 3an-2 โ€“ an-3 = 0 untuk n โ‰ฅ 3 dengan kondisi awal a0 = 1 a1 = 2 dan a2 = 4

Penyelesaian

Persamaan karakteristik yang sesuai dengan relasi rekurensi an – 3an-1 + 3an-2 โ€“ an-3 = 0 adalah t3 – 3t2 + 3t-1 = (t-1)3 = 0

Persamaan karakteristik mempunyai 3 akar kembar yaitu ฮฑ1 = ฮฑ2 = ฮฑ3 = 1

sehingga penyelesaiannya adalah

an = (c1 + c2n + c3n2).1n = c1 + c2n + c3n2

Untuk menentukan koefisien-koefisien c1, c2, dan c3, digunakan kondisi awalnya:

a0 = 1 sehingga 1 = c1 + c2 (0) + c3(0)2

1 = c1

a1 = 2 sehingga 2 =c1 + c2 (1) + c3(1)2

2 = c1 + c2 + c3

a2 = 4 sehingga 4 =c1 + c2 (2) + c3(2)2

4 = c1 + 2c2 + 4c3

Didapat sistem persamaan linier :

c1 = 1

c1 + c2 + c3 = 2

c1 + 2c2 + 4c3 = 4

yang mempunyai penyelesaian c1 = 1 c2 = ยฝ c3= ยฝ

Maka, penyelesaian relasi rekurensi an – 3 an-1 + 3 an-2 โ€“ an-3 = 0 adalah an = 1 + ยฝn + ยฝn2


Penyelesaian Khusus

Penyelesaian untuk relasi rekurensi linier (tidak homogen) dengan koefisien konstan adalah gabungan dari penyelesaian homogen dan penyelesaian khusus (disebut penyelesaian total).

Hanya saja tidak ada metode yang pasti untuk menentukannya. Yang dapat dilakukan hanyalah memperkirakan bentuk umumnya. Metode perkiraan tersebut dikenal dengan nama koefisien tak tentu (Undetermined Coefficients).

Misalkan,
an + c1 an-1 + โ€ฆ + ck an-k = f(n) โ†’ relasi rekurensi linier dengan koefisien konstan.

c(t) = tk + c1 tk-1 + โ€ฆ + ck โ†’ persamaan karakteristik yang sesuai.

Untuk beberapa jenis fungsi f(n), pola perkiraan penyelesaian khusus yang sesuai dapat dilihat dalam tabel sebagai berikut:

f(n)
(D,a: konstan)
Sifat Persamaan Karakteristik C(t)Bentuk Penyelesaian Khusus
D ana bukan akar persamaan karakteristik c(t)
(c(a) โ‰  0)
P an
D ana adalah akar persamaan karakteristik c(t)
kelipatan m
P nm an
D ns ana bukan akar persamaan karakteristik c(t)
(c(a) โ‰  0)
(P0 + P1n +…+ Psns) an
D ns ana adalah akar persamaan karakteristik c(t)
kelipatan m
(P0 + P1n +…+ Psns) nman
D ns1 bukan akar persamaan karakteristik c(t)
(c(1)โ‰  0)
P0 + P1n +…+ Psns
D ns1 adalah akar persamaan karakteristik c(t)
kelipatan m
(P0 + P1n +…+ Psns) nm
(P, P0, P1, โ€ฆ, Ps adalah koefisien yang harus dicari)

CONTOH 1

Carilah penyelesaian total relasi rekurensi dari

an – 7 an-1 + 10 an-2 = 4n untuk n โ‰ฅ 2 dengan kondisi awal a0 = 8 dan a1 = 36

Penyelesaian

Relasi rekurensi homogennya adalah : an – 7 an-1 + 10 an-2 = 0

Persamaan karakteristik : t2 – 7t + 10 = (t-2) (t-5) = 0

Akar-akar karakteristiknya adalah ฮฑ1 = 2, ฮฑ2 = 5

Penyelesaian homogen : an = c1 2n + c2 5n

Karena f(n) = 4n dan 4 bukan akar karakteristik, maka untuk mencari penyelesaian khusus dicoba bentuk

\[ a_{n}^{k} = P \space (4)^{n} \]

Penyelesaian khusus ini selanjutnya disubstitusikan ke relasi rekurensi mula-mula. Didapat :

P 4n -7(P 4n-1) + 10 (P 4n-2) = 4n

P 4n-2 (42-7.4 + 10) = 4n

-2 P 4n-2 = 4n

-2 P = 16

p = -8

Sehingga penyelesaian khususnya adalah

\[ a_{n}^{k} = P-8 (4)^{n} \]

Penyelesaian Total = Penyelesaian homogen + Penyelesaian khusus

an = c1.2n + c2.5n – 8(4)n

Untuk mencari harga c1 dan c2, digunakan kondisi awal yang diberikan :

ao = 8 sehingga 8 = c1(2)0 + c2(5)0 -8(4)0

8 = c1 + c2 -8

16 = c1 + c2

a1 = 36 sehingga 36 = c1(2)1 + c2(5)1 -8(4)1

36 = 2c1 + 5c2 – 32

68 = 2c1 + 5c2

didapat sistem persamaan linier :

c1 + c2 = 16

2c1 + 5c2 = 68

yang bila diselesaikan akan menghasilkan c1=4 dan c2 = 12

Jadi, penyelesaian relasi rekurensi mula-mula adalah

an = 4(2)n +12(5)n – 8(4)n


CONTOH 2:

Carilah penyelesaian total relasi rekurensi dari

an – 7 an-1 + 10 an-2 = 7.3n + 4n untuk n โ‰ฅ 2

Penyelesaian

Karena relasi rekurensi homogennya sama dengan soal pada contoh 1 maka penyelesaian homogennya juga sama yaitu an = c12n + c25n

Kaena f(n) = 7(3)n + 4n, maka penyelesaian khususnya adalah jumlah dari penyelesaian khusus relasi rekurensi an – 7 an-1 + 10 an-2 = 7.3n dengan

an – 7 an-1 + 10 an-2 = 4n (dari soal contoh 1)

Sekarang tinggal mencari penyelesaian khusus untuk f(n) = 7(3)n

Karena 3 juga bukan akar karakteristik, maka dicoba bentuk

\[ a_{n}^{k} = P \space (3)^{n} \]
\[ Jika \space \space a_{n}^{k} = P \space (3)^{n} \space disubstitusikan \space ke \space relasi \space mula-mula \]

maka di dapat :

P.3n – 7 (P.3n-1) + 10 (P.3n-2) = 7.3n

P.3n-2 (32 – 7.3 + 10) = 7.3n

\[P(-2) = 7.3^{2} \space atau \space P = \frac{-63}{2} \]

Jadi..

\[ a_{n}^{k} = \frac{-63}{2} \space (3)^{n} \]

Penyelesaian khusus yang sesuai dengan f(n) = 7.3n + 4n adalah

\[ a_{n}^{k} = \frac{-63}{2} \space (3)^{n} \space – \space 8(4)^{n} \]

Sehingga penyelesaian totalnya adalah

\[ a_{n} \space = \space c_{1}(2)^{n} \space + \space c_{2}.(5)^{n} \space – \space \frac{-63}{2}(3)^{n} \space – \space 8(4)^{n} \]

CONTOH 3

Carilah penyelesaian total relasi rekurensi dari

an – 4 an-1 + 4 an-2 = 2n untuk n โ‰ฅ 2

Penyelesaian

Relasi rekurensi homogennya adalah an – 4 an-1 + 4 an-2 = 0

Persamaan karakteristik : t2 – 4t + 4 = (t-2)2 = 0

Akar-akar karakteristik : ฮฑ1 = ฮฑ2 = 2

Penyelesaian homogennya adalah an = (c1 + c2n)2n

f(n) = 2n dan 2 merupakan akar karakteristik kelipatan m=2 (ada 2 buah ฮฑ yang sama).

Maka bentuk penyelesaian khusus yang dicoba adalah :

\[ a_{n}^{k} \space = \space P \space n^{m}a^{n} \space = \space P \space n^{2}2^{n} \]
\[ Dengan \space mensubstitusikan \space \space a_{n}^{k} \space ke \space dalam \space rekurensi \space mula-mula\]

maka di dapat persamaan :

Pn22n – 4 {P(n-1)2 2n-1} + 4 {P(n-2)2 2n-2} = 2n

P 2n-2{n2.22 – 4(n-1)22 + 4 (n-2)2} = 2n

P {4n2 – 8(n2 – 2n + 1) + 4 (n2 – 4n + 4)} = 22

P(8) = 4

P = ยฝ

Sehingga

\[ a_{n}^{k} \space = \space \frac{1}{2} n^{2}\space 2^{n} \]

Dan penyelesaian totalnya adalah an = (c1 + c2n) 2n + ยฝ n2 2n


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Matematika Diskrit – Rekursi, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up