Relasi Rekursif

1. Rumus Eksplisit dan Rumus Rekursif Barisan

Rumus eksplisit barisan adalah rumus suku ke-n tanpa menyebut suku-suku sebelumnya, sedangkan rumus rekursif barisan adalah rumus suku ke-n dengan ada penyebutan suku-suku sebelumnya.

contoh:

Perhatikan barisan berikut ini

1, 3, 5, 7, ...

Cari rumus suku ke-n dari barisan tersebut!

Rumus suku ke-n dari barisan tersebut adalah Uₙ = 2n − 1 dengan n elemen himp bil asli. Rumus ini disebut sebagai rumus eksplisit.

Selain itu, dapat juga dinyatakan Uₙ = Uₙ₋₁ + 2, U₁ = 1, dimana n ≥ 2. Rumus ini disebut sebagai rumus rekursif.

2. Relasi dan Persamaan Rekursif

• Relasi rekursif (recurrence relation) adalah pendefinisian suatu suku dalam barisan dengan merujuk pada satu atau lebih suku-suku sebelumnya.

• Persamaan rekursif adalah sebuah formula dimana setiap bagian dari suatu barisan dapat ditentukan menggunakan satu atau lebih bagian sebelumnya.

• Jika aₖ adalah banyak cara untuk menjalankan prosedur dengan k objek, untuk k = 0, 1, 2, ..., maka Persamaan rekursif adalah sebuah persamaan yang menyatakan aₙ, sebagai sebuah fungsi dari aₖ untuk k < n.

3. Persamaan Rekursif Linier Berkoefisien Konstan

• Sebuah persamaan rekursif linier berkoefisien konstan dari sebuah fungsi numerik a, secara umum ditulis sebagai berikut :

aₙ + C₁·aₙ₋₁ + C₂·aₙ₋₂ + ... + Cₖ·aₙ₋ₖ = f(n)

dimana

Cᵢ, untuk i = 0, 1, 2, ..., k adalah konstan

f(n) adalah sebuah fungsi numerik dengan variabel n.

Jika f(n) = 0 persamaan rekursif tersebut disebut sebagai persamaan rekursif linier homogen

Jika f(n) ≠ 0 persamaan rekursif tersebut disebut sebagai persamaan rekursif linier non homogen

Persamaan rekursif tersebut dikatakan persamaan rekursif linier berderajat k jika Cₖ ≠ 0

• Pada sebuah Persamaan rekursi linier berkoefisien konstan derajat k , apabila harga k buah aⱼ yang berurutan diketahui, maka harga aⱼ yang lainnya dapat ditentukan secara unik. Dengan kata lain, k buah harga aⱼ yang diberikan merupakan himpunan syarat batas [kondisi awal] yang harus dipenuhi oleh Persamaaan rekursi tersebut untuk dapat memperoleh harga yang unik.

4. Metode Iterasi untuk Menyelesaikan Persamaan Rekursif

Metode iterasi merupakan metode paling dasar dalam menentukan rumus eksplisit dari barisan yang didefinisikan secara rekursif. Metode ini hanya dapat diterapkan pada relasi rekursif yang sederhana. Prinsip Perhitungan:

• Hitung suku-suku barisan secara berurutan terus menerus hingga diperoleh pola tertentu

• Berdasar pola tersebut dibuat rumus eksplisit

• Untuk mendapat pola tersebut, barisan dapat dihitung secara menaik (dihitung berturut-turut a₀, a₁, a₂, ...) atau secara menurun (dihitung berturut-turut aₙ, aₙ₋₁, aₙ₋₂, ...)

contoh:

aₙ = aₙ₋₁ + n; n > 0; a₀ = 1

solusi:

n = 1 → a₁ = a₀ + 1 = 1 + 1 = 2

n = 2 → a₂ = a₁ + 2 = 1 + 1 + 2 = 4

n = 3 → a₃ = a₂ + 3 = 1 + 1 + 2 + 3 = 7

...

n = n → aₙ = aₙ₋₁ + n = 1 + 1 + 2 + 3 + ... + n = 1 + (1 + 2 + 3 + ... + n) = 1 + n(n + 1)/2

Jadi, rumus eksplisitnya adalah aₙ = 1 + n(n + 1)/2

5. Metode Akar Persamaan Karakteristik untuk Menyelesaikan Persamaan Rekursif Linier Homogen dengan Koefisien Konstan

• Bentuk umum

aₙ + c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ = 0; cₖ ≠ 0

dengan k kondisi awal untuk 1 ≤ i ≤ k, cᵢ = konstanta

• Misalkan aₙ = xⁿ, x ≠ 0 maka bentuk umum menjadi

xⁿ + c₁xⁿ⁻¹ + c₂xⁿ⁻² + .... + cₖxⁿ⁻ᵏ = 0

• Bagi kedua ruas dengan xⁿ⁻ᵏ

xᵏ + c₁xᵏ⁻¹ + c₂xᵏ⁻² + .... + cₖ = 0

persamaan ini disebut persamaan karakteristik

• Jika semua akarnya berbeda, solusi dari persamaannya adalah

aₙ = α₁x₁ⁿ + α₂x₂ⁿ + ... + αₖxₖⁿ

• Jika ada akar yang kembar, dikalikan polinom dengan pangkat tertingginya adalah banyak kembaran dikurangi 1, contoh:

jika x₁ = x₂ maka aₙ = (α₁ + α₂n)x₁ⁿ + α₃x₃ⁿ + ... + αₖxₖⁿ

pada contoh ini x₁ kembar 2 sehingga dikalikan polinom berderajat 2 − 1 = 1, yaitu α₁ + α₂n.

6. Solusi Persamaan Rekursif Linier Non-Homogen

Dalam usaha mencari solusi dari sebuah persamaan rekursif linier non homogen perlu dicari dua macam solusi, yaitu :

• Solusi homogen yang diperoleh dari persamaan rekursif linier dengan mengambil harga f(n) = 0.

• Solusi khusus/partikuler yang memenuhi persamaan rekursif sebenarnya.

Solusi total atau jawab keseluruhan dari sebuah persamaan rekursif linier non homogen adalah jumlah dari solusi homogen dan solusi khusus.

aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾

aₙ: Solusi total

aₙ⁽ʰ⁾: Solusi homogen

aₙ⁽ᵖ⁾: Solusi partikuler

• Pada dasarnya tidak ada satu metode yang dapat menentukan solusi khusus dari sebuah persamaan rekursif linier yang non homogen.

• Untuk menentukan solusi khusus dari sebuah persamaan rekursif linier yang non homogen, akan diberikan beberapa model solusi yang disesuaikan dengan bentuk f(n). Model yang sering digunakan adalah model polinomial atau model eksponensial.

Secara umum:

• Jika f(n) berbentuk polinomial derajat t dalam n :

F₁nᵗ + F₂nᵗ⁻¹ + ... + Fₜn + F₊₁ ,

maka bentuk dari solusi khusus yang sesuai adalah :

aₙ⁽ᵖ⁾ = P₁nᵗ + P₂nᵗ⁻¹ + ... + Pₜn + P₊₁

• Jika f(n) berbentuk

(F₁nᵗ + F₂nᵗ⁻¹ + ... + Fₜn + F₊₁)βⁿ dan β bukan akar

karakteristik dari persamaan homogen, maka bentuk dari solusi khusus yang sesuai adalah :

aₙ⁽ᵖ⁾ = (P₁nᵗ + P₂nᵗ⁻¹ + ... + Pₜn + P₊₁)βⁿ

• Jika f(n) berbentuk

(F₁nᵗ + F₂nᵗ⁻¹ + ... + Fₜn + F₊₁)βⁿ dan β akar karakteristik yang berulang sebanyak m kali, maka bentuk dari solusi khusus yang sesuai adalah :

aₙ⁽ᵖ⁾ = nᵐ . (P₁nᵗ + P₂nᵗ⁻¹ + ... + Pₜn + P₊₁)βⁿ

Contoh Soal dan Pembahasan

1. Selesaikan persamaan rekursif

aₙ = aₙ₋₁ + 8aₙ₋₂ − 12aₙ₋₃ untuk n ≥ 3; dengan a₀ = 1; a₁ = 2; a₂ = 14

solusi:

aₙ − aₙ₋₁ − 8aₙ₋₂ + 12aₙ₋₃ = 0, persamaan karakteristik

x³ − x² − x + 12 = 0, faktorkan

(x − 2)²(x + 3) = 0

x = 2 (kembar 2) ∨ x = −3

bentuk umum solusinya adalah

aₙ = (A + Bn).2ⁿ + C.(−3)ⁿ

a₀ = 1 → (A + B.0).2⁰ + C.(−3)⁰ = A + C = 1 ...(i)

a₁ = 2 → (A + B.1).2¹ + C.(−3)¹ = 2A + 2B − 3C = 2 ...(ii)

a₂ = 14 → (A + B.2).2² + C.(−3)² = 4A + 8B + 9C = 14 ...(iii)

4(ii) − (iii) → 4A − 21C = −6 ...(iv)

4(i) − (iv) → 25C = 10 ↔ C = ⅖, masukkan ke (i)

A + ⅖ = 1 ↔ A = ⅗, masukkan ke (ii)

2.⅗ + 2B − 3.⅖ = 2 ↔ 2B = 2 ↔ B = 1

Jadi, solusi dari persamaan rekursif ini adalah aₙ = (⅗ + n).2ⁿ + ⅖.(−3)ⁿ

2. Selesaikan persamaan rekursif

aₙ = aₙ₋₁ + 14aₙ₋₂ − 24aₙ₋₃ untuk n ≥ 3; dengan a₀ = 10; a₁ = 10; a₂ = 32

solusi:

aₙ − aₙ₋₁ − 14aₙ₋₂ + 24aₙ₋₃ = 0, persamaan karakteristik

x³ − x² − 14x + 24 = 0, faktorkan

(x + 4)(x − 2)(x − 3) = 0

x = −4 ∨ x = 2 ∨ x = 3

bentuk umum solusinya adalah

aₙ = A.(−4)ⁿ + B.2ⁿ + C.3ⁿ

a₀ = 10 → A.(−4)⁰ + B.2⁰ + C.3⁰ = A + B + C = 10 ...(i)

a₁ = 10 → A.(−4)¹ + B.2¹ + C.3¹ = −4A + 2B + 3C = 10 ...(ii)

a₂ = 32 → A.(−4)² + B.2² + C.3² = 16A + 4B + 9C = 32 ...(iii)

selesaikan SPL dan diperoleh

A = 1, B = 13, C = −4

Jadi, solusi dari persamaan rekursif ini adalah aₙ = (−4)ⁿ + 13.2ⁿ − 4.3ⁿ

3. Tentukan rumus eksplisit untuk barisan Fibonacci!

Ingat kembali bahwa rumus rekursif untuk barisan Fibonacci adalah:

Fₙ = Fₙ₋₁ + Fₙ₋₂; untuk n ≥ 3; dengan F₀ = 0; F₁ = 1

Fₙ − Fₙ₋₁ − Fₙ₋₂ = 0, persamaan karakteristik

x² − x − 1 = 0, gunakan rumus abc

a = 1, b = −1, c = −1

Misalkan

bentuk umum solusinya adalah
Fₙ = A.φⁿ + B.ψⁿ

F₁ = 1, berlaku:

F₀ = 0, sehingga Aφ⁰ + Bψ⁰ = 0 ↔ A + B = 0 ↔ B = −A ...(i)

F₁ = 1, sehingga Aφ¹ + Bψ¹ = 1 ↔ Aφ + Bψ = 1 ...(ii)

Masukkan (i) ke (ii)

Aφ − Aψ = 1 ↔ A(φ − ψ) = 1 ↔ A√5 = 1 ↔ A = 1/(√5), masukkan ke (i)

B = −1/(√5), masukkan ke rumus Fₙ

Fₙ = (φⁿ − ψⁿ)/(√5)

Beberapa suku pertama barisan Fibonacci dimulai dari n = 0:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

4. Tentukan solusi total dari relasi rekursif aₙ = 3aₙ₋₁ + n.2ⁿ; n ≥ 1; a₀ = 0

solusi:

aₙ = 3aₙ₋₁ + n.2ⁿ; n ≥ 0; a₀ = 0

aₙ − 3aₙ₋₁ = n.2ⁿ; n ≥ 0; a₀ = 0

* Solusi homogen

aₙ − 3aₙ₋₁ = 0

Persamaan karakteristiknya adalah

x − 3 = 0

x = 3

aₙ⁽ʰ⁾ = A.3ⁿ

* Solusi partikuler

f(n) = n.2ⁿ

solusi partikulernya adalah

aₙ⁽ᵖ⁾ = (Bn + C).2ⁿ, masukkan ke persamaan awal

(Bn + C).2ⁿ − 3(B(n − 1) + C).2ⁿ⁻¹ = n.2ⁿ, bagi masing-masing ruas dengan 2ⁿ⁻¹

2(Bn + C) − 3(Bn − B + C) = 2n

2Bn + 2C − 3Bn + 3B − 3C = 2n

−Bn + (−C + 3B) = 2n, diperoleh

−B = 2 ↔ B = −2

−C + 3B = 0 ↔ C = 3B = 3.(−2) = −6

aₙ⁽ᵖ⁾ = (−2n − 6).2ⁿ

* Solusi total

aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾ = A.3ⁿ + (−2n − 6).2ⁿ

a₀ = 0 → A.3⁰ + (−2.0 − 6).2⁰ = 0 ↔ A − 6 = 0 ↔ A = 6

Jadi, solusi total persamaan rekursif ini adalah aₙ = 6.3ⁿ + (−2n − 6).2ⁿ

5. Tentukan solusi total dari relasi rekursif aₙ + 3aₙ₋₁ = 4n² − 2n; n ≥ 2; a₁ = −4

* Solusi homogen

aₙ + 3aₙ₋₁ = 0, persamaan karakteristik

x + 3 = 0

x = −3

aₙ⁽ʰ⁾ = A.(−3)ⁿ

* Solusi partikuler

f(n) = 4n² − 2n, polinom berderajat 2, solusi partikulernya adalah

aₙ⁽ᵖ⁾ = Bn² + Cn + D, masukkan ke persamaan awal

Bn² + Cn + D + 3[B(n − 1)² + C(n − 1) + D] = 4n² − 2n

Bn² + Cn + D + 3[Bn² − 2Bn + B + Cn − C + D] = 4n² − 2n

(4B)n² + (4C − 6B)n + (3B − 3C + D) = 4n² − 2n, diperoleh

4B = 4 ↔ B = 1

4C − 6B = −2 ↔ 4C = −2 + 6B = −2 + 6 = 4 ↔ C = 1

3B − 3C + D = 0 ↔ D = 0 − 3B + 3C = 0 − 3.1 + 3.1 = 0

aₙ⁽ᵖ⁾ = n² + n

* Solusi total

aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾ = A.(−3)ⁿ + n² + n

a₁ = −4 → A.(−3)¹ + 1² + 1 = −4 ↔ −3A = −4 − 2 = −6 ↔ A = 2

Jadi, solusi total persamaan rekursif ini adalah aₙ = 2.(−3)ⁿ + n² + n

6. Tentukan solusi total dari relasi rekursif aₙ − 4aₙ₋₁ + 4aₙ₋₂ = 2ⁿ + 4; a₀ = 0; a₁ = 1; n ≥ 2

* Solusi homogen

aₙ − 4aₙ₋₁ + 4aₙ₋₂ = 0, persamaan karakteristiknya adalah

x² − 4x + 4 = 0

(x − 2)² = 0

x = 2, kembar 2

aₙ⁽ʰ⁾ = (A + Bn).2ⁿ

* Solusi partikuler

f(n) = 2ⁿ + 4

untuk 2ⁿ karena 2 merupakan akar karakteristik kembar 2, solusi partikulernya adalah Cn²2ⁿ

4 merupakan konstanta, solusi partikulernya adalah D

aₙ⁽ᵖ⁾ = Cn²2ⁿ + D, masukkan ke persamaan awal

Cn²2ⁿ + D − 4[C(n − 1)²2ⁿ⁻¹ + D] + 4[C(n − 2)²2ⁿ⁻² + D] = 2ⁿ + 4

Cn²2ⁿ + D − 2[C(n − 1)²2ⁿ + 2D] + [C(n − 2)²2ⁿ + 4D] = 2ⁿ + 4

Cn²2ⁿ + D − 2[C(n² − 2n + 1)2ⁿ + 2D] + [C(n² − 4n + 4)2ⁿ + 4D] = 2ⁿ + 4

2C2ⁿ + D = 2ⁿ + 4, diperoleh

2C = 1 ↔ C = ½

D = 4

aₙ⁽ᵖ⁾ = ½n²2ⁿ + 4

* Solusi total

aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾ = (A + Bn).2ⁿ + ½n²2ⁿ + 4 = (A + Bn + ½n²).2ⁿ + 4

a₀ = 0 → (A + B.0 + ½0²).2⁰ + 4 = 0 ↔ A + 4 = 0 ↔ A = −4

a₁ = 1 → (A + B.1 + ½1²).2¹ + 4 = 1 ↔ 2A + 2B + 5 = 1 ↔ 2A + 2B = −4

masukkan A = −4 ke 2A + 2B = −4

2(−4) + 2B = −4 ↔ 2B = −4 + 8 = 4 ↔ B = 2

Jadi, solusi total persamaan rekursif ini adalah aₙ = (−4 + 2n + ½n²).2ⁿ + 4

7. Tentukan solusi total dari relasi rekursif

aₙ − 7aₙ₋₁ + 16aₙ₋₂ − 12aₙ₋₃ = −2n + 9 untuk n ≥ 3; dengan a₀ = 1; a₁ = 1; a₂ = 2

* Solusi homogen

aₙ − 7aₙ₋₁ + 16aₙ₋₂ − 12aₙ₋₃ = 0, persamaan karakteristiknya adalah

x³ − 7x² + 16x − 12 = 0, faktorkan

(x − 2)²(x − 3) = 0

x = 2 (kembar 2) ∨ x = 3

aₙ⁽ʰ⁾ = (A + Bn).2ⁿ + C.3ⁿ

* Solusi partikuler

f(n) = −2n + 9, merupakan fungsi linier, sehingga solusi partikulernya juga fungsi linier

aₙ⁽ᵖ⁾ = D + En, masukkan ke persamaan awal

D + En − 7[D + E(n − 1)] + 16[D + E(n − 2)] − 12[D + E(n − 3)] = −2n + 9

(−2E)n + (−2D + 11E) = −2n + 9, diperoleh

−2E = −2 ↔ E = 1

−2D + 11E = 9 ↔ −2D + 11 = 9 ↔ −2D = −2 ↔ D = 1

aₙ⁽ᵖ⁾ = n + 1

* Solusi total

aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾ = (A + Bn).2ⁿ + C.3ⁿ + n + 1

a₀ = 1 → (A + B.0).2⁰ + C.3⁰ + 0 + 1 = 1 ↔ A + C = 0 ...(i)

a₁ = 1 → (A + B.1).2¹ + C.3¹ + 1 + 1 = 1 ↔ 2A + 2B + 3C = −1 ...(ii)

a₂ = 2 → (A + B.2).2² + C.3² + 2 + 1 = 2 ↔ 4A + 8B + 9C = −2 ...(iii)

Selesaikan SPL yang terbentuk, akan diperoleh

A = −2; B = −3/2; C = 2

Jadi, solusi total persamaan rekursif ini adalah (−2 − 3n/2).2ⁿ + 2.3ⁿ + n + 1