Relasi Rekursif

Relasi, dalam MATEMATIKA adalah hubungan antara dua buah elemen

himpunan. Hubungan ini bersifat abstrak, dan tidak perlu memiliki arti
apapun baik secara konkrit maupun secara matematis. Relasi biner R
antara A dan B adalah himpunan bagian dari A x B. Himpunan A disebut
daerah asal (domain) dari R dan himpunan B disebut daerah hasil (range)
dari R. Relasi pada himpunan A adalah relasi dari A x A.

Relasi rekursif sering juga disebut relasi berulang . relasi ini

mendefinisikan sebuah barisan dengan memberikan nilai ke-n yang
dikaitkan dengan suku suku sebelumnya . untuk mendefinisikan sebuah
barisan, relasi berulang memerlukan nilai awal yang sudah ditentukan.
Secara formal relasi berulang ini didefinisikan sebagai berikut:
Definisi sebuah relasi berulang untuk barisan a0, a1, a2, . . . merupakan
sebuah persamaan yng mengkaitkan an dengan 0, a1, a2, . . . , an-1.
Syarat awal untuk barisan a0, a1, a2, . . . adalah nilai nilai yang diberikan
secara eksplisit pada beberapa suku dari barisan tersebut.

Contohnya:

Barisan 3, 7 , 11, 15, . . . didefinisikan dengan relasi berulang an = an-1 +

4 untuk n 1 dengan syarat awal a0 = 3.
Contoh 2
Carilah relasi berulang dengan syarat awal dari barisan 1, 1, 2, 4, 16, 128,
4096, . . .
Penyelesaian
Bentuk rumusan setiap suku dengan menggunakan suku sebelumnya
1=1
1=1X1
2=2X1X1
4=2X2X1
16 = 2 X 4 X 2
128 = 2 X 16 X 4
4096 = 2 X 128 X 16 X 4
Dengan demikian relasi yang berulang yang diperoleh adalah an = 2 X an-
1 X 2 X an-2 untuk n2
Dengan syarat awal a0 = 1 dan a1 = 1
Relasi rekursif sering juga disebut relasi berulang . relasi ini
mendefinisikan sebuah barisan dengan memberikan nilai
ke-n yang dikaitkan dengan suku suku sebelumnya . untuk
mendefinisikan sebuah barisan, relasi berulang memerlukan nilai awal
yang sudah ditentukan.
Secara formal relasi berulang ini didefinisikan sebagai berikut:
Definisi sebuah relasi berulang untuk barisan a0, a1, a2, . . . merupakan
sebuah persamaan yng mengkaitkan an dengan 0, a1, a2, . . . , an-1.
Syarat awal untuk barisan a0, a1, a2, . . .
adalah nilai nilai yang diberikan secara eksplisit pada beberapa suku dari
barisan tersebut.

@: Sebuah relasi rekurensi linier berkoefisien konstan dapat dinyatakan

dalam bentuk C0 an + C1 an-1 + + Ck an-k = f(n). Bila nilai f(n) = 0, maka
diperoleh relasi rekurensi yang memenuhi
C0 an + C1 an-1 + C2 an-2 + + Ck an-k = 0.
Relasi rekurensi demikian disebut dengan relasi rekurensi homogen dan
solusi dari relasi rekurensi homogen ini dinamakan solusi homogen atau
jawab homogen.
Dalam usaha mencari solusi dari sebuah relasi rekurensi perlu dicari dua
macam solusi, yaitu :
1. Solusi homogen (jawab homogen) yang diperoleh dari relasi rekurensi
linier dengan mengambil harga f(n) = 0.
2. Solusi khusus/partikuler (jawab khusus) yang memenuhi relasi
rekurensi sebenarnya.

Solusi homogen dari sebuah relasi rekurensi linier dapat dicari dengan mengambil
harga f(n) = 0. Solusi homogen dari sebuah persamaan diferensial linier dengan
koefisien konstan dinyatakan dalam bentuk Aan , dimana a adalah akar
karakteristik dan A adalah konstanta yang harganya akan ditentukan kemudian
untuk memenuhi syarat batas yang diberikan. Dengan substitusi bentuk
Aan kepada an pada persamaan homogen
C0 an + C1 an-1 + C2 an-2 + + Ck an-k = 0 , maka diperoleh
C0 Aan + C1 Aan-1 + C2 Aan-2 + + Ck Aan-k = 0.
Dengan penyederhanaan pada persamaan tersebut, maka diperoleh
C0 an + C1 an-1 + C2 an-2 + + Ck an-k = 0
Persamaan ini merupakan persamaan karakteristik dari persamaan diferensial yang
diberikan. Apabila akar karakteristik dari persamaan karakteristik ini, maka Aan akan
memenuhi persamaan homogen. Jadi, solusi homogen yang dicari akan berbentuk
[Link] persamaan karakteristik memiliki sebanyak k akar karakteristik
berbeda (a1 a2 ak) , maka solusi homogen dari relasi rekurensi yang dimaksud
dinyatakan dalam bentuk
an(h) = A1 a1n + A2 a2n + + Ak akn
dimana ai adalah akar karakteristik dari persamaan karakeristik yang
diperoleh, sedangkan Ai adalah konstanta yang akan dicari untuk
memenuhi kondisi batas yang ditentukan.
[Link]
[Link]?m=1

CONTOH MAKALAH, TIDAK BISA DI BUKA

([Link]
[Link]?m=1)

Contoh soal Relasi Rekursi beserta pembahasan

KELOMPOK 1

1. Solusi homogen dari relasi rekurensi bn + bn-1 2 bn-2 = 0 dengan kondisi batas b0 =
2 , b1 = 3 adalah

a. bn(h) = 1/6(-2)n + 1/3. (1)n

b. (a + 3) (a - 2)
c. bn(h) = 1/5 (-3)n +1/5 . 2n

d. b0(h) = A1 (-3)0 + A2 . 20

Pembahasan :

bn + bn-1 2 bn-2 = 0

= a2 + a- 2 = 0

= (a+ 2) (a- 1) = 0

a1 = -2 a2 = 1.

Solusi homogen = bn(h)= A1 a1n+ A2 a2n =>bn(h)= A1 (-2)n+ A2 . (1)n

Dengan kondisi batas b0= 2 dan b1= 3 ,maka:

b0(h) = A1 (-2)(2) + A2 . 1(2) => 0 = -4 A1 + 2 A2

b1(h) = A1 (-2)(3) + A2 . 1(3) => 1 = -6 A1 + 3A2

-4 A1 + 2 A2 = 0 x 3 -12A1 + 6 A2 = 0

-6 A1 + 3A2 = 1 x2 -12A1 + 6 A2 = 2 +

6A2 = 2

A2 = 1/3

-4A1 + 2A2 = 0

-4A1 + 2(1/3) = 0

A1 = 1/6

Maka akan diperoleh harga A1 = 1/6 dan A2 =1/3

Jawab homogen dari relasi rekurensi bn + bn-1 2bn-2 = 0 adalah

bn(h) = 1/6(-2)n + 1/3. (1)n

2. Mana diantara berikut yang merupakan solusi dari relasi rekurensi dari :
an + 4 an-1 + 4 an-2 = 0 .

a. an(h) = (A1 nm-1 + A2 nm-2) a1n , an(h) = (A1 n + A2 ) (-2)n .

b. an(h) = (A1 n + A2 ) (-2)n .

c. an(h) = (A1 nm-1 + A2 nm-2) a1n ,

d. an(h) = (A1 nm-1) an(h) = (A1 n + A2 ) (-2)n .

Pembahasan :

Relasi rekurensi homogen : an + 4 an-1 + 4 an-2 =0.

Persamaan karakteristiknya adalah a2 + 4 a + 4 = 0

(a+ 2) (a + 2) = 0

Hingga diperoleh akar-akar karakteristik a1 = a2 = -2 , m = 2,

Oleh arena akar-akar karakteristiknya ganda,Maka solusi homogennya berbentuk

an(h) = (A1 nm-1 + A2 nm-2) a1n ,an(h) = (A1 n + A2 ) (-2)n .

3. a - an-1 = 2n2,n 1, dan 0 = 9 Solusi Umumnya adalah

a. 5 + (n) (n+1)(4n+2)

b. 9 + (n) (n+1)(2n+1)

c. 2 + (n+2)(n)(n+2n)

d. 9 + (n)(n+1)(2n+1)

Pembahasan :

f (n) = 2n2, sehingga solusi umumnya :

 = A0+ (n(n+1)(2n+1)/6)

= 9 + (n) (n+1)(2n+1)

5. Berapa banyak kah bilangan Fibonacci antara 10 sampai dengan 100?

(A) 90

(B) 9

(C) 5

(D) 10

Jawab :

Dari tabel di atas, terlihat bahwa bilangan Fibonacci yang terletak antara 10 hingga 100
adalah sebanyak 5 (lima) buah, yaitu suku ke-6 (13), suku ke-7 (21), suku ke-8 (34), suku ke-
9 (55), dan suku ke-10 (89). Dengan demikian, jawabannya adalah (C) 5.

6. Diketahui : Suatu barisan c0, c1, c2, didefinisikan secara rekursif sebagai berikut :

Untuk semua bilangan bulat k 2,

Ck = (ck-1 + k) (ck-2 + 1)

Dengan kondisi awal c0 = 1 dan c1 = 2.

Ditanya : Hitunglah c5 !

Penyelesaian :

Oleh karena barisan didefinisikan secara rekursif, maka c5 tidak bisa dihitung secara
langsung, tetapi harus terlebih dahulu menghitung c2, c3 dan c4.

c2 = c1 + 2 c0 + 1 =

2 + 2.1 + 1 =5

c3= c2 + 3 c1 + 1 =

5 + 3.2 + 1 = 12

c4= c3 + 4 c2 + 1 =

12 + 4.5 + 1 = 33

c5= c4 + 5 c3 + 1 =

33 + 5.12 + 1 = 94

Jadi, c5 = 94

A. C5 = 90

B. C5 = 92

C. C5 = 84

D. C5 = 94

7. Diketahui relasi rekurensi Sn = 2Sn-1 dengan syarat awal S0 = 1. Selesaikan untuk suku
ke-n!

a. 2n
b. 4n
c. n
d. 2

Jawab:

Sn = 2Sn-1
= 2 (2Sn-2) = 22 Sn-2
= 23 Sn-3
=
= 2nS0
= 2n

8. Selesaikan relasi rekurensi an = 7an -1 , n > 1, a2= 98

a. an= 7n (2) , n > 1

b. an= 7n (1) , n > 0

c. an= 7n , n > 2

d. an= 7n(2) , n > 0

Penyelesaian

Untuk n = 1 maka a1 = 7 a0 a2 = 7 a1 = 7 (7 a0) = 72a0 dari a2 = 98 maka 98 = 49 a0

sehingga diperoleh a0 = 2. Jika relasi rekurensi tersebut dideretkan terus akan diperoleh :

a3 = 7 a2 = 7 (7pangkat2 a0) = 7pangkat3 a0 ..........dan seterusnya

sehingga penyelesaian umum dari relasi rekurensi di atas adalah

an= 7n (2) , n > 0

9. Tentukan solusi umum dari relasi rekurensi dan 0=9

a. 5 + (n) (n+1) (4n+2)

b. 9 + (n) (n+2) (2n+1)

c. 2 + (n+2) (n) (n+2n)

d. 9 + (n) (n+1) (2n+1)

Penyelesaian
f(n) = sehingga solusi umumnya :

n = 0 + (i)

=0+2

=0+2

= 9 + (n) (n+1) (2n+1)

10. Dengan mengambil satu harga n kemudian anda menjumlahkan bilangan-bilangan tsb
mulai dari f1 s.d. fn maka berapakah n terkecil agar jumlah itu > 150?

(A) 9

(B) 10

(C) 11

(D) 15

Jawab :

Dari tabel di atas juga, dapat kita ketahui bahwa nilai n terkecil agar jumlah seluruh bilangan
Fibonacci dari f1 hingga fn > 150 adalah sebesar 10 (n=10), yang akan menghasilkan jumlah
sebesar 231 (diperoleh dari = 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89, yang merupakan
bilangan fibonacci dari suku ke-1 hingga suku ke-10). Sehingga, jawaban yang benar adalah
(B) 10

[Link]
[Link]?=1