Relasi Rekursif

BAB I

PENDAHULUAN

A.    Latar Belakang

Suatu barisan dapat kita nyatakan dengan beberapa cara. Cara pertama dengan menuliskan beberapa suku-sukunya. Misalnya barisan bilangan ganjil yang lebih besar dari 2 dapat dinyatakan, yaitu 3, 5, 7, 9, 11, . . . . . Cara kedua nyatakan barisan itu dalam rumus, misalnya barisan bilangan ganjil yang besar dari 2 dengan rumus dinyatakan :  . cara ketiga dengan, rekursif. Suatu barisan didefinisikan secara rekursif maka kondisi awal barisan diketahui, dan suku-suku barisan selanjutnya dinyatakan dalam hubungannya dengan jumlah suku-suku yang sudah dinyatakan sebelumnya. Persamaan yang menyatakan hubungan antara beberapa suku tersebut dinamakan Relasi Rekursi.

Misalnya barisan pangkat dari 2, yaitu 2, 4, 8, 16, . . . dapat dinyatakan sebagai berikut.

disebut kondisi awal, sedang  disebut relasi rekurensi.

Definisi rekursif merupakan suatu jawaban ketika untuk menentukan ru mus eksplisit suatu barisan sangat rumit atau bahkan mustahil. Hal ini terjadi tidak hanya pada barisan bilangan, tetapi juga paling sering terjadi pada beberapa konsep matematika yang lain, seperti: operasi himpunan, proposisi dalam logika, relasi, fungsi, bahasa mesin, dll.

B.     Rumusan Masalah

Berdasarkan latar belakang masalah di atas maka dapat di buat rumusan masalah sebagai berikut:

1.      Apa definisi dari rekursif?

2.      Bagaimana fungsi, barisan, dan himpunan yang didefinisikan secara rekursif?

3.      Apakah relasi rekursif ?

4.      Bagaimana penyelesaian relasi rekursif?

C.    Tujuan

1.      Dapat mendefinisikan rekursif.

2.      Dapat membuktikan fungsi, barisan, dan himpunan yang didefinisikan secara rekursif.

3.      Dapat mengetahui relasi rekursif

4.      Dapat menentukan penyelesaian relasi rekursif.

BAB II PEMBAHASAN

RELASI REKURSIF

Untuk memahami definisi rekursif, terlebih dahulu perhatikan barisan intejer genap tak-negatif:  Barisan itu bisa kita tuliskan dengan:  Suku ke berapapun dari barisan itu bisa kita peroleh secara langsung, misalnya: suku ke-125 adalah : Barisan yang demikian kita sebut dengan barisan dengan rumus eksplisit.

Definisi rekursif merupakan suatu jawaban ketika untuk menentukan ru mus eksplisit suatu barisan sangat rumit atau bahkan mustahil. Hal ini terjadi tidak hanya pada barisan bilangan, tetapi juga paling sering terjadi pada beberapa konsep matematika yang lain, seperti: operasi himpunan, proposisi dalam logika, relasi, fungsi, bahasa mesin, dll.[1]

Rekursif adalah suatu proses dari fungsi yang memanggil dirinya sendiri. Fungsi yang seperti ini disebut fungsi rekursif (recursive function) . dalam sebuah fungsi rekursif pemanggilan dapat terjadi berulang kali. Karena ada proses yang berulang-ulang maka harus ada suatu kondisi yang mengakhiri.

Pemecahan masalah dengan pendekatan rekursif dapat dilakukan jika masalah tersebut dapat didefinisikan secara rekursif, yaitu masalah dapat diuraikan menjadi masalah sejenis yang lebih sederhana.

•      Sebuah objek dikatakan rekursif  (recursive) jika ia didefinisikan dalam terminologi dirinya sendiri.

•      Proses mendefinisikan objek dalam terminologi dirinya sendiri disebut rekursi (recursion).[2]

A.    Fungsi yang Didefinisikan secara Rekursif

Tinjau kembali fungsi untuk menghitung faktorial dari bilangan bulat tak-negatif n yang didefenisikan sebagai berikut :

bentuk faktorial tersebut dapat dinyatakan sebagai berikut

 , untuk

secara rekursif bentuk faktorial dapat dinyatakan

Jika f(n) = n! maka bentuk di atas dapat dinyatakan sebagai berikut:

Kita dapat melihat bahwa dalam proses perhitungan faktorial bilangan tak-negatif n terdapat definisi faktorial itu sendiri. Cara pendefenisian seperti itu, yang mendefenisikan sebuah objek dalam terminologi dirinya sendiri dinamakan definisi rekursif.

Definisi 1: Fungsi f dikatakan fungsi rekursif apabila definisi fungsinya mengacu pada dirinya sendiri[3]

Nama lain dari fungsi rekursif adalah relasi rekursif (recurrence relation). Ingatlah bahwa fungsi adalah bentuk khusus dari relasi.

Definisi 2 : Fungsi f dikatakan fungsi rekursif (recurrence relation)

Penyusunan fungsi rekursif memperhatikan aturan :

a). Basis: bagian yang berisi nilai awal yang tidak mengacu pada di sendiri. Bagian ini juga sekaligus menghentikan defenisi rekursif ( dan memberikan sebuah nilai yang terdefenisi pada fungsi rekursif).

b). Rekurens: bagian ini mendefinisikan argumen fungsi dalam terminologi dirinya sendiri. Setiap kali fungsi mengacu pada dirinya sendiri, argumen dari fungsi harus lebih dekat ke nilai awal (basis).[4]

Contoh 1:

Akan ditentukan nilai 4 ! secara rekursif.

Jawab :

(a). basis ,  untuk

(b). rekurens: Untuk  

maka untuk menentukan nilai 4 ! digunakan langkah berikut :

(1)  

(2)                 

(3)                               

(4)                                              

(5)                                                            

Pada baris (5) kita memperoleh nilai yang terdefenisi secara langsung dan bukan faktorial dari bilangan lainnya. Dengan melakukan runut-balik (backtrack) dari baris (5) ke baris (1), kita mendapatkan nilai pada setiap baris untuk menghitung hasil pada baris sebelumnya :

(5)  

(4)  

(3)  

(2)  

(1)  

maka nilai  adalah .

Contoh 2.

Diberikan fungsi rekursif f , yang didefinisikan sebagai berikut:

 bilangan bulat positip, tentukan nilai

Jawab :

 merupakan fungsi floor maka hasil pembagian dibulatkan kebawah

(nilai dibulatkan ke 0)

Contoh lain dari fungsi rekursif yaitu:

Fungsi Chebysev :

Fungsi fibonacci :

Contoh 3:

sehingga:

Latihan :

1. Definisikan aⁿ secara rekursif , yang dalam hal ini a adalah bilangan riil tidak-nol dan n adalah bilangan bulat tidak-negatif.

2. Nyatakan a ´ b secara rekursif, yang dalam hal ini a dan b adalah bilangan bulat positif.

B.     Barisan Yang Didefinisikan Secara Rekursif

Perhatikan barisan bilangan berikut ini: 1, 2, 4, 8, 16, 64, …

Setiap elemen ke-n untuk n = 0, 1, 2, … merupakan hasil perpangkatan  2 dengan n, atau a_n = 2ⁿ. Secara rekursif, setiap elemen ke-n merupakan hasil kali elemen sebelumnya dengan 2, atau a_n = 2a_{n – 1}.

            Basis: a₀ = 1

            Rekurens: a_n = 2a_{n – 1}.[5]

Contoh 4: 

Koloni bakteri dimulai dari lima buah bakteri.  Setiap bakteri membelah diri menjadi dua bakteri baru setiap satu jam. Berapa jumlah bakteri baru sesudah 4 jam?

Jawab:

Misalkan a_n = jumlah bakteri setelah n jam, yang dapat dinyatakan dalam relasi rekursif sebagai berikut:

n = 1  à jumlah bakteri = a₁ = 2a₀ = 2 × 5 = 10

n = 2  à jumlah bakteri = a₂ = 2a₁ = 2 × 10 = 20

n = 3  à jumlah bakteri = a₃ = 2a₂ = 2 × 20 = 40

n = 4  à jumlah bakteri = a₄ = 2a₃ = 2 × 40 = 80

Jadi, setelah 4 jam terdapat 80 buah bakteri

C.    Himpunan Yang Didefinisikan Secara Rekursif

Langkah-langkah dalam mendefinisikan suatu himpunan secara rekursif:

1.      Langkah basis: Spesifikasi koleksi awal dari anggota

2.      Langkah rekursif: Mendefinisikan aturan konstruksi anggota baru dari anggota yang telah diketahui [6]

Contoh 5:

Misalkan S didefinisikan secara rekursif oleh: 3 Î S, (x+y) Î S jika x Î S dan y Î S

Maka S adalah himpunan bilangan bulat positif yang habis dibagi 3.

Bukti:

Misalkan A himpunan yang beranggotakan semua bilangan bulat positif yang habis dibagi 3.

Untuk membuktikan bahwa A = S, harus ditunjukkan

A Í S dan S Í A.

Bagian I:

Akan dibuktikan A Í S, yaitu menunjukkan bahwa setiap bilangan bulat positif yang habis dibagi 3 ada di S (dengan menggunakan induksi matematika).

Misalkan P(n): proposisi “3n anggota S”.

1.      Langkah basis: P(1) benar, karena 3 Î S.

2.      Langkah induktif:

 Asumsikan P(k) benar, yaitu 3k Î S.

Akan ditunjukkan P(k+1) juga benar, yaitu 3(k+1) Î S

Karena 3k Î S dan 3 Î S, berdasarkan definisi rekursif dari S, 3k+3 = 3(k+1) juga ada di S.

3.      Konklusi:

Jadi, setiap bilangan bulat positif yang habis dibagi 3 ada di S.

Kesimpulan dari bagian I adalah A Í S.

Bagian II:

Akan ditunjukkan S Í A dengan menggunakan definisi rekursif dari S.

Langkah basis:

Akan ditunjukkan setiap anggota awal S ada di A.

Karena 3 habis dibagi 3 maka 3 Î A.

Langkah rekursif:

Akan ditunjukkan bahwa setiap bilangan bulat yang dibangun dengan mengunakan langkah rekursif juga merupakan anggota A, yaitu

(x+y) Î A jika x,y Î S (yang diasumsikan Î A).

Jika x dan y keduanya di A, maka 3 | x dan 3 | y. Akibatnya, 3 | (x + y).

Kesimpulan dari bagian II adalah S Í A.

Jadi, secara keseluruhan, berlaku A = S.

D.    Relasi Rekurens

Relasi rekursif adalah suatu topik penting dan menarik dalam kombinatorik. Banyak permasalahan dalam matematika, khususnya kombinatorik dapat dimodelkan ke dalam bentuk relasi rekursif. Suatu barisan didefinisikan secara rekursif jika kondisi awal barisan ditentukan, dan suku-suku barisan selanjutnya dinyatakan dalam hubungannya dengan sejumlah suku-suku yang sudah dinyatakan sebelumnya.

Barisan (sequence) a₀, a₁, a₂, …, a_n dilambangkan dengan {a_n} Elemen barisan ke-n, yaitu a_n,  dapat ditentukan dari suatu persamaan.

Bila persamaan yang mengekspresikan a_n dinyatakan secara rekursif dalam satu atau lebih term elemen sebelumnya, yaitu a₀, a₁, a₂, …, a_n–1, maka persamaan tersebut dinamakan relasi rekurens.[7]

Contoh 6:

a_n = 2a_n–1   + 1

a_n = a_n–1 + 2a_n–2

a_n = 2a_n–1  – a_n–2

Kondisi awal (initial conditions) suatu barisan adalah satu  atau lebih nilai yang diperlukan untuk memulai menghitung elemen-elemen selanjutnya.

Contoh 7: 

a_n = 2a_n–1   + 1; a₀ = 1

a_n = a_n–1 + 2a_n–2 ; a₀ = 1 dan a₁ = 2 

Karena relasi rekurens menyatakan definisi  barisan secara rekursif, maka kondisi awal merupakan langkah basis pada definisi rekursif tersebut.

Contoh 8:

Barisan Fibonacci  0, 1, 1, 2, 3, 5, 8, 13, … dapat dinyatakan dengan relasi rekurens

                        f_n = f_n–1  + f_n–2  ;   f₀ = 0 dan f₁ = 1

Kondisi awal secara unik menentukan elemen-elemen barisan. Kondisi awal yang berbeda akan menghasilkan elemen-elemen  barisan yang berbeda pula.

Solusi dari sebuah relasi rekurens adalah sebuah formula yang tidak melibatkan lagi term  rekursif.   Formula tersebut memenuhi relasi rekurens yang dimaksud.

Contoh 9:

Misalkan {a_n} adalah barisan yang memenuhi relasi rekurens berikut:  

                        a_n = 2a_n–1  – a_n–2  ;  a₀ = 1 dan a₁ = 2

Periksa apakah a_n = 3n merupakan solusi relasi rekurens tersebut.

Penyelesaian:

2a_n–1  – a_n–2 = 2[3(n – 1)] – 3(n – 2)

                   = 6n – 6 – 3n + 6

                   = 3n = a_n

Jadi, a_n = 3n merupakan solusi dari relasi rekurens tersebut.

Apakah a_n = 2ⁿ merupakan solusi relasi rekurens  a_n = 2a_n–1  – a_n–2  ;  a₀ = 1 dan a₁ = 2?

Penyelesaian:

2a_n–1  – a_n–2 = 2×2^n–1 –  2^n–2

                   = 2^{n–1 + 1}  –  2^n–2

                   = 2ⁿ  –  2^n–2 ¹ 2ⁿ

Jadi, a_n = 2ⁿ  bukan merupakan solusi relasi rekurens tsb.

Cara lain: Karena a₀ = 1 dan a₁ = 2, maka dapat dihitung

                 a₂ = 2a₁ – a₀ = 2×2 – 1 = 3

                 Dari rumus a_n = 2ⁿ dapat dihitung a₀ = 2⁰ = 1,

                 a₁ = 2¹ = 2, dan  a₂ = 2² = 4           

                 Karena 3 ¹ 4, maka a_n = 2ⁿ  bukan merupakan solusi dari relasi rekurens tsb.

a.      Pemodelan Dengan Relasi Rekurens

1.      Bunga majemuk.

Contoh 10.

Misalkan uang sebanyak Rp10.000 disimpan di bank dengan sistem bunga berbunga dengan besar bunga 11% per tahun.  Berapa banyak uang setelah 30 tahun? 

Jawan:

Misalkan P_n menyatakan nilai uang setalah n tahun.  Nilai uang setelah n tahun sama dengan nilai uang tahun sebelumnya ditambah dengan bunga uang:

             P_n = P_n–1  + 0,11 P_n–1 ; P₀ = 10.000

Solusi relasi rekurens P_n = P_n–1  + 0,11 P_n–1 ; P₀ = 10.000 dapat dipecahkan sebagai berikut:

            P_n        = P_n–1  + 0,11 P_n–1  = (1,11) P_n–1

                        = (1,11) [(1,11)P_n–2] = (1,11)²P_n–2

                        = (1,11)² [(1,11) P_n–3] = (1,11)³P_n–3

                        = …

                        = (1,11)ⁿP₀

Jadi, P_n = (1,11)ⁿ P₀ = 10.000 (1,11)ⁿ

Setelah 30 tahun, banyaknya uang adalah

 P₃₀ = 10.000 (1,11)³⁰ = Rp228.922,97

2.  Menara Hanoi (The Tower of Hanoi)

Contoh 11:

Menara Hanoi adalah sebuah puzzle yang terkenal pada akhir abad 19. Puzzle ini ditemukan oleh matematikawan Perancis, Edouard Lucas.

Dikisahkan bahwa di kota Hanoi, Vietnam, terdapat tiga buah tiang tegak setinggi 5 meter dan 64  buah piringan (disk) dari berbagai ukuran. Tiap piringan mempunyai lubang di tengahnya yang memungkinkannya untuk dimasukkan ke dalam tiang. Pada mulanya piringan tersebut tersusun pada sebuah tiang sedemikian rupa sehingga piringan yang di bawah mempunyai ukuran lebih besar daripada ukuran piringan di atasnya. Pendeta Budha memberi pertanyaan kepada murid-muridnyanya: bagaimana memindahkan seluruh piringan tersebut ke sebuah tiang yang lain; setiap kali hanya satu piringan yang boleh dipindahkan, tetapi tidak boleh ada piringan besar di atas piringan kecil. Tiang yang satu lagi dapat dipakai sebagai tempat peralihan dengan tetap memegang aturan yang telah disebutkan. Menurut legenda pendeta Budha, bila pemindahan seluruh piringan itu berhasil dilakukan, maka dunia akan kiamat!

Secara umum, untuk n piringan, penyelesaian dengan cara berpikir rekursif adalah sebagai berikut:

Kita harus memindahkan piringan paling bawah terlebih dahulu ke tiang B sebagai alas bagi piringan yang lain. Untuk mencapai maksud demikian, berpikirlah secara rekursif: pindahkan n – 1 piringan teratas dari A ke C, lalu pindahkan piringan paling bawah dari A ke B, lalu pindahkan n – 1 piringan dari C ke B.

                        pindahkan n – 1 piringan dari A ke C

                        pindahkan 1 piringan terbawah dari A ke B

                        pindahkan n – 1 piringan dari C ke B

Selanjutnya dengan tetap berpikir rekursif-pekerjaan memindahkan n – 1 piringan dari sebuah tiang ke tiang lain dapat dibayangkan sebagai memindahkan n – 2 piringan antara kedua tiang tersebut, lalu memindahkan piringan terbawah dari sebuah tiang ke tiang lain, begitu seterusnya.

Misalkan H_n menyatakan jumlah perpindahan piringan yang dibutuhkan untuk memecahkan teka-teki Menara Hanoi.

                        pindahkan n – 1 piringan dari A ke C             à H_n-1 kali

                        pindahkan 1 piringan terbawah dari A ke B   à 1 kali

                        pindahkan n – 1 piringan dari C ke B                         à H_n-1 kali

Maka jumlah perpindahan yang terjadi adalah:

                        H_n = 2H_n-1  + 1

dengan kondisi awal H₁ = 1

Penyelesaian relasi rekurens:

                         H_n  = 2H_n-1 + 1

                               = 2(2H_n-2 + 1) + 1 = 2² H_n-2  + 2 + 1

                               = 2² (2H_n-3 + 1) + 2 + 1  = 2³ H_n-3  + 2² + 2 + 1

                                    ¼       

                               = 2^n-1 H₁  + 2^n-2 + 2^n-3 + … + 2 + 1

                               = 2^n-1  + 2^n-2 + 2^n-3 + … + 2 + 1   à deret geometri

                               = 2ⁿ – 1

Untuk n = 64 piringan, jumlah perpindahan piringan yang terjadi adalah

                        H₆₄ = 2⁶⁴ – 1 = 18.446.744.073.709.551.615

Jika satu kali pemindahan piringan membutuhkan waktu 1 detik, maka waktu yang diperlukan adalah       18.446.744.073.709.551.615 detik atau setara dengan 584.942.417.355 tahun atau sekitar 584 milyar tahun!

Karena itu, legenda yang menyatakan bahwa dunia akan kiamat bila orang berhasil memindahkan 64 piringan di menara Hanoi ada juga benarnya, karena 584 milyar tahun tahun adalah waktu yang sangat lama, dunia semakin tua, dan akhirnya hancur. Wallahualam

b.      Penyelesaian Relasi Rekurens

Relasi rekurens dapat diselesaikan secara iteratif atau dengan metode yang sistematis. Secara iteratif misalnya pada contoh bunga majemuk (Contoh 10) dan Menara Hanoi (Contoh 11). Secara sistematis adalah untuk relasi rekurens yang berbentuk homogen lanjar (linear homogeneous).

Relasi rekurens dikatakan homogen lanjar jika berbentuk

                        a_n = c₁a_n–1  + c₂a_n–2 + … + c_ka_n–k

yang dalam hal ini c₁, c₂, …, c_k adalah bilangan riil dan c_k ¹ 0.[8]

Contoh 12:

P_n = (1,11) P_n–1  à homogen lanjar

                                    f_n = f_n–1  +  f_n–2  à homogen lanjar

                                     a_n = 2a_n–1  – a²_n–2 à tidak homogen lanjar

                                     H_n = 2H_n–1  – 1  à tidak homogen lanjar

                                     a_n = na_n–1   à tidak homogen lanjar

Penjelasan:

            H_n = 2H_n–1  – 1  tidak homogen lanjar karena term -1 tidak dikali dengan nilai H_j  untuk sembarang j

             a_n = na_n–1   tidak homogen lanjar karena koefisiennya bukan konstanta.

Solusi relasi rekurens yang berbentuk homogen lanjar adalah mencari bentuk

                                    a_n = rⁿ

yang dalam hal ini r adalah konstanta.

Sulihkan a_n = rⁿ ke dalam relasi rekuren homugen lanjar:

                        a_n = c₁a_n–1  + c₂a_n–2 + … + c_ka_n–k

menjadi

                         rⁿ = c₁r^n–1  + c₂r^n–2 + … + c_kr^n–k

Bagi kedua ruas dengan r^n–k  , menghasilkan

                        r^k – c₁r^k–1 – c₂r^k–2 – … – c_{k – 1} r  – c_k = 0

Persamaan di atas dinamakan persamaan karakteristik dari relasi rekurens.  Solusi persamaan karakteristik disebut akar-akar karakteristik, dan merupakan komponen solusi relasi rekurens yang kita cari (a_n = rⁿ).

Untuk relasi rekurens homogen lanjar derajat k = 2,

                        a_n = c₁a_n–1  + c₂a_n–2

persamaan karakteristiknya berbentuk:

                        r² – c₁r – c₂ = 0

Akar persamaan karakteristik adalah r₁ dan r₂.

Teorema 1:

Barisan {a_n} adalah solusi relasi rekurens a_n = c₁a_n–1  + c₂a_n–2 jika dan hanya jika a_n = a₁rⁿ₁  + a₂rⁿ₂  untuk n = 0, 1, 2, … dengan a₁ dan a₂ adalah konstan.

Contoh 13:  

Tentukan solusi relasi rekurens berikut:

             a_n = a_n–1  +  2a_n–2  ;  a₀ = 2 dan a₁ = 7?

Penyelesaian: 

Persamaan karakteristik: r² – r – 2 = 0.  

Akar-akarnya:  (r – 2) (r + 1) = 0  à r₁ = 2 dan r₂ = -1

                        a_n = a₁rⁿ₁  + a₂rⁿ₂ à a_n = a₁2ⁿ  + a₂(-1)ⁿ

                         a₀ = 2 à a₀ = 2 = a₁2⁰  + a₂(-1)⁰   = a₁  + a₂

                        a₁ = 7 à a₁ = 7 = a₁2¹  + a₂(-1)¹   = a₁  – a₂

Diperoleh dua persamaan: a₁  + a₂ = 2 dan a₁  – a₂ = 7,

solusinya adalah a₁  = 3 dan a₂ = –1

Jadi, solusi relasi rekurens adalah:  a_n = 3×2ⁿ   – (-1)ⁿ

Jika persamaan karakteristik memiliki dua akar yang sama (akar kembar, r₁ = r₂),  maka Teorema 1 tidak dapat dipakai.  Terapkan Teorema 2 berikut ini.

Teorema 2:

Misalkan r² – c₁r – c₂ = 0  mempunyai akar kembar r₀. Barisan {a_n} adalah solusi relasi rekurens a_n = c₁a_n–1  + c₂a_n–2 jika dan hanya jika a_n = a₁rⁿ₀  + a₂nrⁿ₀ untuk n = 0, 1, 2, … dengan a₁ dan a₂ adalah konstan.

Contoh 14: 

Tentukan solusi relasi rekurens berikut:

             a_n = 6a_n–1  – 9a_n–2  ;  a₀ = 1 dan a₁ = 6?

Penyelesaian: 

Persamaan karakteristik: r² – 6r + 9 = 0.  

Akar-akarnya:  (r – 3)(r – 3 ) = 0  à r₁ = r₂ = 3 à r₀

                        a_n = a₁rⁿ₀  + a₂nrⁿ₀ à a_n = a₁3ⁿ  + a₂n3ⁿ

                        a₀ = 1 à a₀ = 1 = a₁3⁰  + a₂× 0×3⁰   = a₁   

                        a₁ = 6 à a₁ = 6 = a₁3¹  + a₂×1×3¹   = 3a₁  + 3a₂

Diperoleh dua persamaan: a₁ = 1 dan 3a₁  + 3a₂ = 6,

solusinya adalah a₁  = 1 dan a₂ = 1

Jadi, solusi relasi rekurens adalah:

                          a_n = 3ⁿ   + n3ⁿ

c.       Penyelesaian Relasi Rekurensi dengan Iterasi

Prinsipnya: dihitung suku-suku barisan secara berurutan terus menerus sehingga diperoleh suatu pola tertentu.

Contoh 15:

Misalkan K_n adalah graf dengan n buah titik dan setiap pasang titik dihubungkan dengan sebuah garis (Graf Lengkap).

Jika S_n menyatakan jumlah garis dalam K_n, maka:

a. Buktikan bahwa S_n memenuhi relasi rekurensi S_n = S_n-1 + (n-1) 

    dan kondisi awal S₁ = 0

b. Selesaikan relasi rekurensi S_n tersebut.

Penyelesaian:

a.      

K_n untuk n = 1, 2, 3, 4, dan 5

Banyaknya garis dalam K₄ adalah banyaknya garis K₃ ditambah dengan banyaknya garis baru yang harus dibuat akibat penambahan satu buah titik.

Banyaknya garis baru yang ditambahkan pada K₄ sama dengan banyaknya titik pada K₃. Jadi S₄ = S₃ + 3.

Secara umum: S_n = S_n-1 + (n-1)

Kondisi awal S₁ = 0 jelas benar karena tidak mungkin membuat garis dari satu buah titik.

b.      S_n         = S_n-1 + (n-1)

            = (S_n-2 + (n-2)) + (n-1) = S_n-2 + (n-2) + (n-1)

            = (S_n-3 + (n-3)) + (n-2) + (n-1) = S_n-3 + (n-3) + (n-2) + (n-1)

            = …

            = S_n-(n-1) + (n-(n-1)) + …+ (n-3) + (n-2) + (n-1)

            = S₁ + 1 + 2 + … + (n-2) + (n-1)

Karena S₁ = 0 maka

S_n = 1 + 2 + … + (n-2) + (n-1) = ½ n (n-1)

E.     Relasi Rekursif Linear dengan Koefisien Konstanta

Sebuah relasi rekurensi linier berkoefisien konstan dari sebuah fungsi numerik  a, secara umum ditulis sebagai berikut

C₀ a_n + C₁ a_n-1 + C₂ a_n-2 + … + C_k a_n-k = f(n)

dimana  C_i , untuk i = 0,1,2,…,k  adalah konstan  dan f(n) adalah sebuah fungsi numerik dengan variabel  n.

            Relasi rekurensi tersebut dikatakan relasi rekurensi linier berderajat  k , jika C₀  dan C_k  keduanya tidak bernilai 0 (nol).[9]

Contoh 16:

2 a_n + 2 a_n-1 = 3ⁿ          adalah sebuah relasi rekurensi linier berderajat  1

t_n = 7 t_n-1                     adalah sebuah relasi rekurensi linier berderajat  1

a_n – a_n-1 – a_n-2 = 0        adalah sebuah relasi rekurensi linier berderajat  2

b_n-3 – 3b_n = n+3           adalah sebuah relasi rekurensi linier berderajat  3                        ð

            Untuk sebuah relasi rekurensi dengan koefisien konstan derajat  k, jika diberikan  k  buah harga  a_j   yang berurutan   a_m-k , a_m-k+1 , … , a_m-1   untuk suatu nilai   m  tertentu, maka setiap nilai  a_m  yang lain dapat dicari dengan rumus

a_m =   ( C₁ a_m-1 + C₂ a_m-2 + … + C_k a_m-k -  f(m) )

dan selanjutnya, harga  a_m+1  juga dapat dicari dengan cara

a_m+1 =   ( C₁ a_m + C₂ a_m-1 + … + C_k a_m-k+1 -  f(m+1) )

demikian pula untuk nilai  a_m+2 , a_m+3  dan seterusnya. Di lain pihak, harga  a_m-k-1  dapat pula dihitung dengan

a_m-k-1 =   ( C₁ a_m-1 + C₂ a_m-2 + … + C_k-1 a_m-k -  f(m-1) )

dan  a_m-k-2   dapat dicari dengan

a_m-k-2 =   ( C₁ a_m-2 + C₂ a_m-3 + … + C_k-1 a_m-k-1 -  f(m-2) ).

Harga a_m-k-3 dan seterusnya dapat dicari dengan cara yang sama. Jadi, untuk sebuah relasi rekurensi linier berkoefisien konstan derajat  k  , bila harga k  buah  a_j yang berurutan diketahui, maka harga  a_j yang lainnya dapat ditentukan secara unik. Dengan kata lain, k  buah  harga a_j yang diberikan merupakan himpunan syarat batas (kondisi batas) yang harus dipenuhi oleh relasi rekurensi tersebut untuk dapat memperoleh harga yang unik.

1)      Solusi dari relasi rekurensi

            Seperti telah disebutkan pada bagian sebelumnya, sebuah relasi rekurensi linier berkoefisien konstan dapat dinyatakan dalam bentuk  C₀ a_n + C₁ a_n-1 + … + C_k a_n-k = f(n). Bila nilai  f(n) = 0, maka diperoleh relasi rekurensi yang memenuhi

C₀ a_n + C₁ a_n-1 + C₂ a_n-2 + … + C_k a_n-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 :[10]

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 total atau jawab keseluruhan dari sebuah relasi rekurensi adalah jumlah dari solusi homogen dan solusi partikuler.  Misalkan  a_n^(h) = (a₀^(h), a₁^(h), … )  adalah solusi homogen yang diperoleh dan   misalkan  a_n^(p) = (a₀^(p), a₁^(p), … ) adalah solusi partikuler yang diperoleh, maka solusi total dari relasi rekurensi yang dimaksud adalah   

a_n = a^(h) + a^(p)

2)      Solusi homogen dari relasi rekurensi

            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  Aaⁿ , dimana  a  adalah akar karakteristik  dan  A  adalah konstanta yang harganya akan ditentukan kemudian untuk memenuhi syarat batas yang diberikan. Dengan substitusi bentuk Aaⁿ  kepada  a_n   pada persamaan homogen    C₀ a_n + C₁ a_n-1 + C₂ a_n-2 + … + C_k a_n-k = 0 , maka diperoleh

C₀ Aaⁿ   + C₁ Aa^n-1 + C₂ Aa^n-2 + … + C_k Aa^n-k = 0.

Dengan penyederhanaan pada persamaan tersebut, maka diperoleh

C₀ aⁿ   + C₁ a^n-1 + C₂ a^n-2 + … + C_k a^n-k = 0

Persamaan ini merupakan persamaan karakteristik dari persamaan diferensial yang diberikan.  Jika,  bila   adalah akar karakteristik dari persamaan karakteristik ini, maka Aaⁿ akan memenuhi persamaan homogen. Jadi, solusi homogen yang dicari akan berbentuk Aaⁿ.

            Bila persamaan karakteristik memiliki sebanyak  k   akar karakteristik berbeda   (a₁ ¹ a₂ ¹ … ¹ a_k) , maka solusi homogen dari relasi rekurensi yang dimaksud dinyatakan dalam bentuk

a_n^(h) = A₁ a₁ⁿ + A₂ a₂ⁿ + … + A_k a_kⁿ

dimana  a_i  adalah akar karakteristik dari persamaan karakeristik yang diperoleh, sedangkan  A_i  adalah konstanta yang akan dicari untuk memenuhi kondisi batas yang ditentukan.[11]

Contoh 17:

Tentukan solusi homogen dari relasi rekurensi     b_n + b_n-1 – 6 b_n-2 = 0  dengan kondisi batas b₀ = 0 , b₁ = 1 .

Penyelesaian :

Relasi rekurensi tersebut adalah relasi rekurensi homogen, karena f(n)=0.

Persamaan karakteristik dari relasi rekurensi b_n + b_n-1 – 6 b_n-2 = 0 adalah         a²  +  a  - 6 = 0  atau   (a + 3) ( a - 2) = 0 hingga diperoleh akar-akar karakteristik   a₁ = -3   dan   a₂ = 2.

Oleh karena akar-akar karakteristiknya berbeda, maka solusi homogennya berbentuk                                    b_n^(h)  = A₁ a₁ⁿ  +  A₂ a₂ⁿ      Þ        b_n^(h)  = A₁ (-3)ⁿ  +  A_{2 .} 2ⁿ.

Dengan kondisi batas   b₀ = 0   dan    b₁ = 1 ,    maka

                        b₀^(h)  = A₁ (-3)⁰  +  A_{2 .} 2⁰         Þ        0  = A₁ +  A₂ .

                        b₁^(h)  = A₁ (-3)¹  +  A_{2 .} 2¹         Þ        1  =  -3 A₁ +  2 A₂ .

bila diselesaikan maka akan diperoleh harga  A₁ = (-1/5)  dan  A₂ = 1/5 , sehingga jawab homogen dari relasi rekurensi    b_n + b_n-1 – 6 b_n-2 = 0  adalah

                                        b_n^(h)  = (-3)ⁿ  +   .  2ⁿ                                                       ð

Jika akar karakteristik  a₁  dari persamaan karakteristik merupakan akar ganda yang berulang sebanyak  m  kali, maka bentuk solusi homogen yang sesuai untuk akar ganda tersebut adalah

(A₁ . n^m-1 + A₂ . n^m-2 + … + A_m-2 n² + A_m-1 . m + A_m ) a₁ⁿ

dimana   A_i  adalah konstanta yang nantinya akan ditentukan untuk memenuhi kondisi batas yang ditentukan.

Contoh 18:

Tentukan solusi dari relasi rekurensi     a_n + 4 a_n-1 + 4 a_n-2 = 2ⁿ .

Penyelesaian :

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

Persamaan karakteristiknya adalah     a²  +  4 a  + 4 = 0

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

hingga diperoleh akar-akar karakteristik   a₁ =  a₂ = -2 ,  m = 2,

Oleh karena akar-akar karakteristiknya ganda,  maka solusi homogennya berbentuk                                                            a_n^(h)  = (A₁ n^m-1 + A₂ n^m-2) a₁ⁿ  ,

                                                  a_n^(h)  = (A₁ n + A₂ ) (-2)ⁿ                                                  ð

Contoh 19:

Tentukan solusi homogen dari relasi rekurensi

4 a_n - 20 a_n-1 + 17 a_n-2 – 4 a_n-3 = 0.

Penyelesaian :

Persamaan karakteristiknya :   4 a³  - 20 a² + 17 a  - 4 = 0

akar-akar karakteristiknya                   ½ , ½  dan   4

solusi homogennya berbentuk             a_n^(h)  = (A₁ n + A₂ ) (½)ⁿ + A₃ . 4ⁿ

3)      Solusi khusus dari relasi rekurensi

                        Pada dasarnya tidak ada satu metode yang dapat menentukan solusi khusus dari sebuah relasi rekurensi linier yang tidak homogen. Untuk menentukan solusi khusus dari sebuah relasi rekurensi linier dengan  f(n) ¹ 0, akan diberikan beberapa model solusi yang disesuaikan dengan bentuk  f(n). Model yang sering digunakan adalah model polinomial atau model eksponensial.[12]

1.      Secara umum, jika  f(n)  berbentuk polinomial derajat  t  dalam  n  :

F₁ n^t + F₂ n^t-1  + … +  F_t n  + F_t+1   ,

maka bentuk dari solusi khusus yang sesuai adalah :

 P₁ n^t + P₂ n^t-1  + … +  P_t n  + P_t+1   

2.      Jika  f(n)  berbentuk  bⁿ  dan  b  bukan akar karakteristik dari persamaan homogen, maka jawab khusus berbentuk

P bⁿ

3. Jika  f(n) berbentuk  (F₁.n^t + F₂.n^t-1 +…+ F_t.n + F_t+1 ).bⁿ  dan b bukan akar karakteristik dari persamaan homogen, maka bentuk dari solusi khusus yang sesuai adalah :

 (P₁ n^t + P₂ n^t-1  + … +  P_t n  + P_t+1  ) bⁿ

4. Jika  f(n)  berbentuk  (F₁.n^t + F₂.n^t-1 +…+ F_t.n + F_t+1 ).bⁿ  dan b  akar karakteristik yang berulang sebanyak  (m-1)  kali, maka bentuk dari solusi khusus yang sesuai adalah :

n^m-1. (P₁ n^t + P₂ n^t-1  + … +  P_t n  + P_t+1  ) bⁿ

Contoh 20:

            Diketahui  a_r – 7 a_r-1 + 10 a_r-2 = 3^r . Tentukan solusi khusus dari a_r.

Penyelesaian :

Diketahui  f(r) = 3^r .

Oleh karena bentuk dari f(r) tersebut adalah b^r dan b = 3 bukan akar karakteristik, maka solusi khusus dari relasi rekurensi tersebut berbentuk  P3^r.

a_r = P 3^r.

BAB III

PENUTUP

Kesimpulan

Rekursif adalah suatu proses dari fungsi yang memanggil dirinya sendiri. Fungsi yang seperti ini disebut fungsi rekursif (recursive function) . dalam sebuah fungsi rekursif pemanggilan dapat terjadi berulang kali. Karena ada proses yang berulang-ulang maka harus ada suatu kondisi yang mengakhiri.

Pemecahan masalah dengan pendekatan rekursif dapat dilakukan jika masalah tersebut dapat didefinisikan secara rekursif, yaitu masalah dapat diuraikan menjadi masalah sejenis yang lebih sederhana.

•      Sebuah objek dikatakan rekursif  (recursive) jika ia didefinisikan dalam terminologi dirinya sendiri.

•      Proses mendefinisikan objek dalam terminologi dirinya sendiri disebut rekursi (recursion)

Penyusunan fungsi rekursif memperhatikan aturan :

a). Basis: bagian yang berisi nilai awal yang tidak mengacu pada di sendiri. Bagian ini juga sekaligus menghentikan defenisi rekursif ( dan memberikan sebuah nilai yang terdefenisi pada fungsi rekursif).

b). Rekurens: bagian ini mendefinisikan argumen fungsi dalam terminologi dirinya sendiri. Setiap kali fungsi mengacu pada dirinya sendiri, argumen dari fungsi harus lebih dekat ke nilai awal (basis).

.

DAFTAR PUSTAKA

Munir, Rinaldi. 2012. Matematika Diskrit Revisi Lima. Bandung: Informatika.

Reky, Umar. 2007. Diktat Kuliah Metode Diskrit. Kendari: Universitas Haluoleo.

Sutarno, Heri, dkk. 2003.  Common Textbook Matematika Diskrit. Bandung: Universitas Pendidikan Indonesia.

http://abrari.files.wordpress.com/2009/12/matdis-updated.pdf

http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2013-2014/Rekursi%20dan%20Relasi %20Rekurens.pptx

http://lecturer.d3ti.mipa.uns.ac.id/hartatik/files/2013/10/bab-3-relasidan-fungsi.pdf

http://www.math.itb.ac.id/~diskrit/Kuliah5baru.ppt

---

[1] http://abrari.files.wordpress.com/2009/12/matdis-updated.pdf

[2] http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2013-2014/Rekursi%20dan%20Relasi%20 Rekurens.pptx

[3] Rinaldi Munir, Matematika Diskrit Revisi Lima, (Bandung: Informatika, 2012), hlm: 139

[4] http://lecturer.d3ti.mipa.uns.ac.id/hartatik/files/2013/10/bab-3-relasidan-fungsi.pdf

[5]http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2013-2014/Rekursi%20dan%20Relasi%20 Rekurens.pptx

[6] http://www.math.itb.ac.id/~diskrit/Kuliah5baru.ppt

[7]http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2013-2014/Rekursi%20dan%20Relasi%20 Rekurens.pptx

[8]http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2013-2014/Rekursi%20dan%20Relasi%20 Rekurens.pptx

[9] Umar Reky, Diktat Kuliah Metode Diskrit, (Kendari: Universitas Haluoleo, 2006), hlm: 28

[10] Umar Reky, Diktat Kuliah Metode Diskrit, (Kendari: Universitas Haluoleo, 2006), hlm: 29

[11] Umar Reky, Diktat Kuliah Metode Diskrit, (Kendari: Universitas Haluoleo, 2006), hlm: 31

[12] Umar Reky, Diktat Kuliah Metode Diskrit, (Kendari: Universitas Haluoleo, 2006), hlm: 34