1. Aplikasi Relasi Rekursif

Relasi Rekursif untuk barisan {an} adalah sebuah persamaan yang

menyatakan an ke dalam satu atau lebih suku-suku sebelumnnya dari

barisan tersebut, yaitu a0, a1, …, an-1, untuk semua bilangan bulat n

dengan n ≥ n0, n0 adalah bilangan bulat tak negatif.

Sebuah barisan dikatakan solusi dari relasi rekursif jika suku-sukunya

memenuhi relasi rekusifnya.

Banyaknya benih penyakit pada sebuah perkampungan bertambah dua

kali setiap jam. Jika sebuah perkampungan awalnya ditemukan lima

benih penyakit, berapa banyak benih penyakit dalam n jam pada

perkampungan tersebut?

Misalkan an adalah banyaknya penyakit pada n jam.

Karena banyaknya benih penyakit bertambah dua kali dalam setiap jam,

maka an= 2an-1 dengan n adalah bilangan bulat positif.

Karena pada perkampungan tersebut awalnya ditemukan lima benih

penyakit, maka a0=5.

Dengan menggunakan pendekatan iterasi, kita dapat menemukan rumus

untuk an ;

an = 2an-1

a1 = 2a0 = 2. 5

a2 = 2a1 = 2. 2.5 = 22. 5

a3 = 2a2 = 2. 2.2.5 = 23. 5

a4 = 2a3 = 2. 2.2.2.5 = 24. 5

.

.

.

an = 2n. 5

Banyak benih penyakit dalam n jam yaitu an= 2n. 5 untuk semua bilangan

bulat tak negatif n.

Membuat Model Relasi Rekursif

Rabbits and the Fibonacci Numbers

Sepasang kelinci muda (jantan dan betina) ditempatkan di suatu pulau.

Sepasang kelinci itu tidak melahirkan sampai mereka berumur dua bulan.

Setelah mereka berumur dua bulan, setiap pasang kelinci melahirkan satu

pasangan lain setiap bulan, seperti yang ditunjukkan pada gambar.

Tentukan relasi rekursif untuk banyaknya pasangan kelinci di pulau

setelah n bulan, dengan mengasumsikan bahwa tidak ada kelinci yang

mati!

Kita misalkan fn adalah banyaknya pasangan kelinci setelah n bulan.

f1 = 1,

f2 = 1.

Untuk menentukan banyaknya pasangan di pulau setelah n bulan,

tambahkan banyaknya pasangan di pulau pada bulan sebelumnya, fn-1,

dengan pasangan yang baru lahir. fn-2, sehingga diperoleh

fn = fn-1 + fn-2.

Dengan demikian, barisan {fn} memenuhi relasi rekursif

fn= fn-1 + fn-2, untuk n ≥ 3,

dengan kondisi awal f1 = 1 dan f2 = 2.

Sehingga banyaknya pasangan kelinci setelah n bulan, dinyatakan oleh

suku ke-n dari barisan Fibonacci.

The Tower of Hanoi

Kita harus memindahkan semua piringan dari tiang (1) ke tiang (3).

Tiang (2) hanya berfungsi sebagai bantuan saja. Piringan hanya boleh

dipindahkan satu per satu. Piringan yang lebih besar harus selalu berada

di bawah piringan yang lebih kecil.

Berapa banyak langkah yang paling sedikit yang dibutuhkan untuk

memindahkan semua piringan ke tiang 3?

1 2 31 2 3

Misalkan mn adalah langkah yang paling sedikit yang dibutuhkan dalam

kasus yang berjumlah n piringan.

Jelas m1= 1.

Misalkan dibutuhkan m4 langah untuk 4 piringan.

m5 = 2m4+ 1.

Dengan menggunakan pendekatan iterasi, kita peroleh solusi relasi

rekursif mn = 2mn-1+ 1 dengan kondisi awal m1=1 dan n > 1.

Perhatikan bahwa mn= 2m(n-1) + 1 dengan m1=1.

Dengan menggunakan teorema 1 pada subbab 2.4, kita peroleh bentuk

mn = 2n – 1.

Oleh karena itu, banyaknya langkah praktis yang dibutuhkan untuk

memindahkan n piringan pada Tower of Hanoi adalah (2n – 1) langkah.

Sebuah relasi rekursif linear homogen berderajat k dengan koefisien

konstan adalah relasi rekursif yang berbentuk

an = c1an-1 + c2an-2 + … + ckan-k,

dengan c1, c2, …, ck adalah bilangan real, dan ck ≠ 0.

2. Menyelesaikan Relasi Rekusif Linear

Pn = {1.11} Pn-1 adalah relasi rekursif linear homogen berderajat

satu.

fn = fn-1 + fn-2 adalah relasi rekursif linear homogen berderajat dua.

an = an-5 adalah relasi rekursif linear homogen berderajat lima.

an = an-1 + a2n-2 tidak linear.

Hn = 2Hn-1 + 1 tidak homogen.

Bn = nBn-1 tidak memiliki koefisien konstan.

Misalkan c1 dan c2 adalah bilangan real dan misalkan r2-c1r-c2 = 0

memiliki dua akar-akar yang berbeda yaitu r1 dan r2. Maka barisan {an}

adalah solusi dari relasi rekursif an=c1an-1 + c2an-2 jika dan hanya jika

an = β1r1n + β2r2

n untuk n = 0,1,2,3,… dengan β1 dan β2 adalah konstan.

Menyelesaikan Relasi Rekursif Linear Homogen dengan Koefisien Konstan

Tentukan solusi dari relasi rekursif an=an-1 + 2an-2

dengan a0= 2 dan a1= 7 !

Persamaan khusus dari relasi rekursif an=an-1 + 2an-2 adalah

r2 – r – 2 = 0. Akar-akarnya adalah r = 2 dan r = -1.

Karenanya, Barisan {an} adalah solusi dari relasi rekursif jika dan hanya

jika an = p2n + q(-1)n, untuk konstan p dan q.

a0= 2 = p + q, ___(1)

a1= 7 = p.2 + q.(-1) ___(2)

Dengan menyelesaiakan persamaan (1) dan (2), kita peroleh p = 3 dan

q = -1.

Jadi, solusinya adalah barisan {an} dengan an = 3.2n - (-1)n.

Tentukan rumus eksplisit untuk Fibonacci numbers !

Ingat kembali bahwa barisan Fibonacci memenuhi relasi rekursif

fn = fn-1 + fn-2 dengan kondisi adalah f0 = 0 dan f1 = 1. Akar-akar dari

persamaan khusus r2 – r – 1 = 0 adalah

r1 = (1+ ) / 2 dan r2 = (1 - ) / 2. Berdasarkan teorema 1, rumus

eksplisit untuk Fibonacci numbers yaitu:

untuk konstan α dan β.

5 5

nn

nf

2

51

2

51

Kondisi awal f0 = 0 dan f1 = 1 digunakan untuk mencari nilai dari

konstan α dan β sehingga diperoleh

f0 = α + β = 0

Dari persamaan di atas kita dapatkan nilai dari

Dengan demikian, rumus eksplisit untuk Fibonacci numbers adalah

12

51

2

511

f

5

1,

5

1

nn

nf

2

51

5

1

2

51

5

1

Misalkan c1 dan c2 adalah bilangan real dengan c2 ≠ 0 dan misalkan

bahwa r2-c1r-c2 = 0 hanya memiliki satu akar yaitu r0. Barisan {an}

adalah solusi dari relasi rekursif an=c1an-1 + c2an-2 jika dan hanya jika

an = β1r0n + β2nr0

n untuk n = 0,1,2,3,… dengan β1 dan β2 adalah

konstan.

Tentukan solusi dari relasi rekursif an= 6an-1 + 9an-2

dengan a0= 1 dan a1= 6 !

Persamaan khusus dari relasi rekursif an= 6an-1 + 9an-2 adalah

r2 – 6r – 9 = 0 dengan r = 3. Berdasarkan teorema 2, solusi dari relasi

rekursif ini adalah

an = p3n + qn3n, untuk konstan p dan q.

Dengan menggunakan a0= 1 dan a1= 6, diperoleh

a0= 1 = p, a1= 6 = p.3 + q.3

Dengan menyelesaiakan persamaan di atas, diperoleh p = 1 dan q = 1.

Jadi, solusinya adalah an = 3n + n3n.

Misalkan c1 ,c2 , …, ck adalah bilangan real. Misalkan persamaan khusus

rk - c1rk-1 - … - ck = 0

memiliki k akar-akar berbeda yaitu r1, r2, … , rk. Maka barisan {an}

adalah solusi dari relasi rekursif

an=c1an-1 + c2an-2 + … + ckan-k

jika dan hanya jika

an = β1r1n + β2r2

n + … + βkrkn

untuk n = 0,1,2,3,… dengan β1, β2, …, βk adalah konstan.

Sebuah relasi rekursif linear nonhomogen dengan koefisien konstan

adalah relasi rekursif yang berbentuk

an = c1an-1 + c2an-2 + … + ckan-k + F(n),

dengan c1, c2, …, ck adalah bilangan real, dan F(n) adalah fungsi yang

tidak identik nol yang tergantung hanya pada n. Relasi rekursif

an = c1an-1 + c2an-2 + … + ckan-k

disebut relasi rekursif homogen penghubung.

Relasi Rekursif Linear Nonhomogen dengan Koefisien Konstan

an = an-1 + 2n, adalah relasi rekursif linear nonhomogen dengan

koefisien konstan dan relasi linear homogen penghubungnya adalah

an = an-1.

an = an-1 + an-2 + n2 + n + 1 adalah relasi rekursif linear nonhomogen

dengan koefisien konstan dan relasi linear homogen penghubungnya

adalah an = an-1 + an-2.

an = 3an-1 + n3n adalah relasi rekursif linear nonhomogen dengan

koefisien konstan dan relasi linear homogen penghubungnya adalah

an = 3an-1 .

Jika an(p) adalah solusi bagian dari relasi rekursif linear nonhomogen

dengan koefisien konstan

an = c1an-1 + c2an-2 + … + ckan-k + F(n),

maka solusinya berbentuk {an(p) + an

(h) }, dengan {an(h) } adalah solusi

dari relasi rekursif homogen penghubung

an = c1an-1 + c2an-2 + … + ckan-k .

Tentukan solusi dari relasi rekursif an= 3an-1 + 2n, dengan a1 = 3.

Relasi rekursif homogen penghubung adalah an= 3an-1, dan solusinya

adalah an(h) = β3n, dengan β adalah konstan.

Solusi bagiannya adalah an(p) = -n – 3/2.

Berdasarkan teorema 4, solusinya adalah

dengan β adalah konstan.

Karena a1 = 3, maka solusinya adalah an = -n – 3/2 + (11/6)3n.

,3.2

3)()( nh

n

p

nn naaa