Matematika Diskrit : Penyelesaian Relasi Rekurensi dengan Persamaan Karakteristik

📋 Daftar Isi

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:

c₀(n) a_n + c₁(n) a_n-1 + … + c_k(n) a_n-k = f(n), c₀(n) dan c_k(n) ≠ 0

Jika c₀(n), c₁(n), …, c_k(n) semuanya konstanta, maka relasi rekurensi disebut relasi rekurensi linier dengan koefisien konstan.

Jadi, relasi rekurensi linier dengan koefisien konstan adalah:
c₀ a_n + c₁ a_n-1 + … + c_ka_n-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. a_n – 7a_n-1 + 10a_n-2 = 0

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

c. c_k = 2c_k-2

d. d_k = d_k-1² + d_k-2

e. e_k = e_{k – 1} • e_k-2

f. f_k – 2f_k-1 + 1 = 0

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

Penyelesaian

a. Relasi rekurensi homogen linier dengan koefisien konstan derajat 2

b. Relasi (b) dapat dinyatakan dengan b_k – b_k-1 – b_k-2 – b_k-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 d_k-1²

e. Bukan relasi rekurensi linier karena memuat pergandaan suku (e_k-1 • e_k-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:

a_n + c₁ a_n-1+ … + c_k a_n-k = 0, c_k ≠ 0 dan n ≥ k

Persamaan karakteristik yang sesuai dengan relasi rekurensi tersebut adalah:

t_k + c₁ t_k-1 + … + c_k= 0

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

Misalkan α₁, α₂, …, α_k adalah akar-akar karakteristik dari persamaan karakteristik atas. Ada 2 kemungkinan akar, yakni sebagai berikut :

Semua akar berbeda

Penyelesaiannya: a_n= c₁ α₁ⁿ + c₂ α₂ⁿ + … + c_k α_kⁿ,dengan c₁, c₂, … , c_k adalah konstanta yang nilainya
ditentukan berdasarkan kondisi awal.

Ada akar yang kembar

Misalkan terdapat p buah akar yang sama.

Jadi, akar-akarnya adalah: α₁ = α₂ = … = α_p, α_p+1, …, α_k

Maka penyelesaian relasi rekurensi tersebut:

a_n= (c₁ + c₂n +…+ c_pn^p-1) α₁ⁿ+ c_p+1 α_p+1ⁿ + … + c_kα_kⁿ

CONTOH 1

Selesaikan relasi rekurensi di bawah ini lewat persamaan karakteristiknya

a_n = 3a_n-1 + 4a_n-2 untuk n ≥ 2 dengan kondisi awal a₀ = 1 dan a₁= 3.

Penyelesaian

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

Persamaan karakteristik yang sesuai adalah t² – 3t -4 = (t-4)(t+1) = 0 yang mempunyai akar-akar karakteristik α₁ = 4 dan α₂= -1

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

a_n = c₁ 4ⁿ + c₂ (-1)_ⁿ

Untuk menentukan c₁ dan c₂, digunakan kondisi awal :

a₀= 1 sehingga 1 = c₁ (4)⁰ + c₂ (-1)⁰

1 = c₁ + c₂

a₁ = 3 sehingga 3 = c₁ (4)¹ + c₂ (-1)¹

3 = 4c₁ – c₂

Didapat sistem persamaan linier :

c₁ + c₂ = 1

4c₁ – c₂ = 3

yang mempunyai penyelesaian c₁ = ⅘ dan c₂ = ⅕

Maka, penyelesaian relasi rekurensi a_n – 3a_n-1 – 4a_n-2 = 0 adalah a_n = ⅘ (4)ⁿ + ⅕ (-1)ⁿ

CONTOH 2

Selesaikan relasi rekurensi di bawah ini lewat persamaan karakteristiknya

a_{n – 3}a_n-1 + 3a_n-2 – a_n-3 = 0 untuk n ≥ 3 dengan kondisi awal a₀ = 1 a₁ = 2 dan a₂= 4

Penyelesaian

Persamaan karakteristik yang sesuai dengan relasi rekurensi a_n– 3a_n-1 + 3a_n-2 – a_n-3 = 0 adalah t³ – 3t²+ 3t-1 = (t-1)³= 0

Persamaan karakteristik mempunyai 3 akar kembar yaitu α₁ = α₂= α₃ = 1

sehingga penyelesaiannya adalah

a_n = (c₁ + c₂n + c₃n²).1ⁿ = c₁+ c₂n + c₃n²

Untuk menentukan koefisien-koefisien c₁, c₂, dan c₃, digunakan kondisi awalnya:

a₀= 1 sehingga 1 = c₁ + c₂ (0) + c₃(0)²

1 = c₁

a₁ = 2 sehingga 2 =c₁ + c₂ (1) + c₃(1)²

2 = c₁+ c₂ + c₃

a₂ = 4 sehingga 4 =c₁ + c₂ (2) + c₃(2)²

4 = c₁+ 2c₂ + 4c₃

Didapat sistem persamaan linier :

c₁ = 1

c₁ + c₂ + c₃ = 2

c₁+ 2c₂ + 4c₃ = 4

yang mempunyai penyelesaian c₁ = 1 c₂ = ½ c₃= ½

Maka, penyelesaian relasi rekurensi a_n– 3 a_n-1 + 3 a_n-2 – a_n-3 = 0 adalah a_n = 1 + ½n + ½n²

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,
a_n+ c₁a_n-1 + … + c_k a_n-k= f(n) → relasi rekurensi linier dengan koefisien konstan.

c(t) = t_k + c₁ t_k-1 + … + c_k→ 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 aⁿ	a bukan akar persamaan karakteristik c(t) (c(a) ≠ 0)	P aⁿ
D aⁿ	a adalah akar persamaan karakteristik c(t) kelipatan m	P n^m aⁿ
D n^s aⁿ	a bukan akar persamaan karakteristik c(t) (c(a) ≠ 0)	(P₀ + P₁n +…+ P_sn^s) aⁿ
D n^s aⁿ	a adalah akar persamaan karakteristik c(t) kelipatan m	(P₀ + P₁n +…+ P_sn^s) n^maⁿ
D n^s	1 bukan akar persamaan karakteristik c(t) (c(1)≠ 0)	P₀ + P₁n +…+ P_sn^s
D n^s	1 adalah akar persamaan karakteristik c(t) kelipatan m	(P₀ + P₁n +…+ P_sn^s) n^m

(P, P₀, P₁, …, P_s adalah koefisien yang harus dicari)

CONTOH 1

Carilah penyelesaian total relasi rekurensi dari

a_n– 7 a_n-1 + 10 a_n-2 = 4ⁿ untuk n ≥ 2 dengan kondisi awal a₀ = 8 dan a₁= 36

Penyelesaian

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

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

Akar-akar karakteristiknya adalah α₁ = 2, α₂ = 5

Penyelesaian homogen : a_n = c₁ 2ⁿ + c₂5ⁿ

Karena f(n) = 4ⁿ 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 4ⁿ -7(P 4^n-1) + 10 (P 4^n-2) = 4ⁿ

P 4^n-2 (4²-7.4 + 10) = 4n

-2 P 4n-2 = 4ⁿ

-2 P = 16

p = -8

Sehingga penyelesaian khususnya adalah

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

Penyelesaian Total = Penyelesaian homogen + Penyelesaian khusus

a_n = c₁.2ⁿ + c₂.5ⁿ – 8(4)ⁿ

Untuk mencari harga c₁ dan c₂, digunakan kondisi awal yang diberikan :

a_o = 8 sehingga 8 = c₁(2)⁰ + c₂(5)⁰ -8(4)⁰

8 = c₁+ c₂ -8

16 = c₁+ c₂

a1 = 36 sehingga 36 = c₁(2)¹ + c₂(5)¹-8(4)¹

36 = 2c₁ + 5c₂ – 32

68 = 2c₁+ 5c₂

didapat sistem persamaan linier :

c₁ + c₂ = 16

2c₁+ 5c₂ = 68

yang bila diselesaikan akan menghasilkan c₁=4 dan c₂ = 12

Jadi, penyelesaian relasi rekurensi mula-mula adalah

a_n= 4(2)ⁿ+12(5)ⁿ – 8(4)ⁿ

CONTOH 2:

Carilah penyelesaian total relasi rekurensi dari

a_n– 7 a_n-1 + 10 a_n-2 = 7.3ⁿ + 4ⁿ untuk n ≥ 2

Penyelesaian

Karena relasi rekurensi homogennya sama dengan soal pada contoh 1 maka penyelesaian homogennya juga sama yaitu a_n= c₁2ⁿ + c₂5ⁿ

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

a_n– 7 a_n-1 + 10 a_n-2 = 4ⁿ (dari soal contoh 1)

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

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.3ⁿ – 7 (P.3^n-1) + 10 (P.3^n-2) = 7.3ⁿ

P.3^n-2 (3² – 7.3 + 10) = 7.3ⁿ

\[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.3ⁿ + 4ⁿ 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

a_n– 4 a_n-1 + 4 a_n-2 = 2ⁿ untuk n ≥ 2

Penyelesaian

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

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

Akar-akar karakteristik : α₁ = α₂= 2

Penyelesaian homogennya adalah a_n = (c₁ + c₂n)2ⁿ

f(n) = 2ⁿ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 :

Pn²2ⁿ – 4 {P(n-1)² 2^n-1} + 4 {P(n-2)² 2^n-2} = 2ⁿ

P 2^n-2{n².2² – 4(n-1)²2 + 4 (n-2)²} = 2ⁿ

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

P(8) = 4

P = ½

Sehingga

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

Dan penyelesaian totalnya adalah a_n = (c₁ + c₂n) 2ⁿ + ½ n² 2ⁿ

Materi Lengkap

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

💡 Definisi Rekursi

✨ Penyelesaian dengan Iterasi

🧮 Penyelesaian dengan Persamaan Karakteristik

💻 Relasi Rekursi dalam Ilmu Komputer

Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Matematika Diskrit : Penyelesaian Relasi Rekurensi dengan Persamaan Karakteristik

Penyelesaian dengan Persamaan Karakteristik