Relasi Rekursi

1.       Relasi Rekursif Homogen Linear Berderajat Dua dengan Koefisien Konstanta

Nyatakan apakah masing-masing relasi rekursif berikut merupakan relasi rekursif homogen linear berderajat dua dengan koefisien konstanta atau bukan:

      1.       ak = (–4)ak – 1 + (k + 1)ak – 2

      2.       bk = bk – 1 + bk – 2

      3.       ck = (ck – 1)2 + ck – 1 ∙ ck – 2

      4.       dk = dk – 1 + dk – 2 + dk – 3

      5.       ek = 2ek – 2

      6.       fk = 2fk – 1 + 3fk – 2 – 5

Pembahasan : Kita dapat mengidentifikasi relasi-relasi rekursif tersebut dengan menggunakan definisi di atas.

      1.       Bukan; koefisiennya bukan konstanta.

      2.       Iya; A = 1 = B.

      3.       Bukan; tidak linear.

      4.       Bukan; tidak berderajat dua.

      5.       Iya; A = 0 dan B = 2.

      6.       Bukan; tidak homogen.

2.       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

3.       Diketahui : Misalkan a1, a2, … ; b1, b2, … dan c1, c2, … adalah 3 barisan yang semua sukunya memenuhi relasi rekurensi. Nilai suatu suku sama dengan 3 kali nilai suku sebelumnya.

Jadi, ak = 3ak-1; bk=3bk-1; ck=3 ck-1.

Tetapi kondisi awal ketiga barisan tersebut berbeda :

a1= 0 ; b1 = 1 ; c1= 2

Ditanya : Nyatakan barisan-barisan terebut dengan cara menuliskan beberapa suku awal barisannya !

Apakah ketiga nya merupakan barisan yang sama ?

Penyelesaian :

Pada barisan a1, a2….

a2 = 3a1 =3.0 = 0

a3 = 3a2 = 3.0 = 0

a4 = 3a3 = 3.0 = 0

pada barisan b1, b2….

b2 = 3b1 = 3.1 = 3

b3 = 3b2 =3.3 = 9

b4 = 3b3 = 3.9 = 27

pada barisan c1, c2….

c2 = 3c1 = 3.2 = 6

c3 = 3c2 = 3.6 =18

c4 = 3c3 = 3.18 = 54

dengan demikian , barisan a1 adalah :0,0,0 …

barisan b1 adalah: 3,9,27…

barisan c1 adalah: 6,18,54…

tampak bahwa ketiga barisan tersebut berbeda. Baik relasi rekurensi maupun kondisi awal barisan yang sangat mempengaruhi nilai-nilai suku barisan yang berbentuk.

4.       Diketahui : Misalkan a0 , a1 , a2 , … , adalah barisan yang didefinisikan secara rekursif sebagai berikut :

Untuk semua bilangan bulat k ≥ 1

ak = ak-1 + 2 ( relasi rekurensi )

a0 = 1 ( kondisi awal )

Ditanya : Carilah rumus eksplisit barisan tersebut dengan metode iterasi.

Penyelesaian :

Metode iterasi akan diselesaikan secara menurun dan secara menaik.

ak = ak-1 + 2

= ( ak-2 + 2 ) + 2 = ak-2 + 2.2

= ( ak-3 + 2 ) + 2.2 = ak-3 + 3.2

= ( ak-4 + 2 ) + 3.2 = ak-4 + 4.2

= ( ak-5 + 2 ) + 4.2 = ak-5 + 5.2

Berdasarkan pola yang ada, terlihat bahwa :

ak = ak-k + k.2 = a0 + 2.k

oleh karena a0 = 1 maka penyelesaian persamaan rekursif adalah ak = 1 + 2k

jika diselesaikan dengan cara menaik :

a1 = a0 + 2

a2 = a1 + 2 = ( a0 + 2 ) + 2 = a0 + 2 + 2 = a0 + 2.2

a3 = a2 + 2 = ( a0 + 2 + 2 ) + 2 = a0 + 2 + 2 + 2 = a0 + 3.2

a4 = a3 + 2 = ( a0 + 2 + 2 + 2 ) + 2 = a0 + 2 + 2 + 2 + 2 = a0 + 4.2

………

ak = a0 + k.2 = 1 + 2 k

5.       Diketahui : mk = 2mk-1 + 1 untuk bilangan bulat k ≥ 2

m1 = 1

Ditanya : Carilah rumus eksplisit barisan m1 , m2 ,…yang menyatakan masalah menara Hanoi.

penyelesaian :

mk = 2mk-1 + 1

= 2 ( 2mk-2 + 1 ) + 1 = 22 mk-2 + 2.1 + 1

= 22 ( 2mk-3 + 1 ) + 2.1 + 1 = 23 mk-3 + 22.1 + 2.1 + 1

= 23 ( 2mk-4 + 1 ) + 22.1 + 2.1 + 1 = 24 mk-4 + 23.1 + 22.1 + 2.1 + 1

= 24 ( 2mk-5 + 1 ) + 23.1 + 22.1 + 2.1 + 1 = 25 mk-5 + 24.1 + 23.1 + 22.1 + 2.1 + 1

= ……….

= 2k-1mk-(k-1) + 2k-2.1 + … + 23.1 + 22.1 + 21 + 1

= 2k-1m1 + 2k-2 + … + 23 + 22 + 21 + 1

Oleh karena m1 = 1, maka :

mk = 2k-1 + 2k-2 + 2k-3 + … + 23 + 22 + 21 + 1

mk merupakan deret geometri dengan r = 2 yang besarnya = (2^((k-1)+1)-1)/(2-1) = 2k – 1

jadi, mk = 2k – 1 untuk bilangan bulat k ≥ 1

6.       Diketahui : Misalkan Kn adalah graf sederhana ( tanpa loop maupun garis paralel ) dengan n buah titik dan setiap pasang titik dihubungkan dengan sebuah garis ( sering disebut Graf Lengkap = Complete Graph ).

Ditanya : Jika Sn menyatakan jumlah garis dalam kn, maka :

Buktikan bahwa Sn memenuhi relasi rekurensi Sn = Sn-1 + (n-1) dam kondisi awal s1 = 0.

Selesaikan relasi rekurensi Sn tersebut.

Penyelesaian :

Kn untuk n = 1,2,3,4 dan 5 tampak pada gambar ini .

K1 K2 K3 K4 K5

Gambar 2

Perhatikan cara penambahan garis ketika menggambar K4 dari K3. Banyaknya garis dalam K4 adalah banyaknya garis K3 ditambah dengan banyaknya garis baru yang harus dibuat akibatpenambahan satu buah titik ( ditunjukkan dengan garis terputus-putus ).

Banyaknya garis baru yang ditambahkan pada K4 sama dengan banyaknya titik pada K3 . jadi, S4 = S3 + 3.

Coba untuk mendapatkan k5 dari K4.

Titik baru yang

Ditambahkan.

K3 K4

Gambar 3

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

Kondisi awal S1 = 0 jelas benar karena tidak mungkin membuat suatu garis dari satu buah titik. ( lihat gambar 2 )

Sn = Sn-1 + (n-1)

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

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

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

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

= ( Sn-4 + (n-4) ) + (n-3) + (n-2) + (n-1)

= Sn-4 + (n-4) + (n-3) + (n-2) + (n-1)

…

= Sn-(n-1) + (n – (n-1)) + … + (n-3) + (n-2) + (n-1)

= S1 + 1 + 2 + … + (n-2) + (n-1)

Oleh karena S1 = 0, maka

Sn = 1 + 2 + … + (n-2) + (n-1) = (n ( n+1 ))/n- n = (n ( n-1))/2

Rumus eksplisit yang didapat dari proses iterasi tersebut sebetulnya hanyalah perkiraan kita saja yang dibuat berdasarkan pola-pola yang ada dalam beberapa suku. Rumus yang kita buat mungkin salah. Untuk memastikan bahwa rumus tersebut benar, kita bisa menggunakan induksi matematika untuk membuktikannya.

7.       Sebutkan dan jelaskan aplikasi dari Pigeon Hole?

Prinsip pigeon hole bisa diterapkan dalam permainan kartu dengan 2 trik yaitu trik permainan kartu kombinatorial. Contoh cara kerjanya adalah Pesulap akan menanyakan kepada salah satu pengunjung untuk memilih secara acak lima kartu dari satu dek kartu permainan. Pengunjung tidak menunjukkan kelima kartu ini pada pesulap , tapi menunjukkannya pada khalayak ramai lainnya. Pengunjung-pengunjung yang lain akan memilih empat kartu dan menunjukkannya pada sang pesulap. Maka pesulap itu akan dengan cepat bisa menentukan kartu kelima kartu pertama yang ditunjukkan ke pesulap adalah satu dai dua kartu yang sama ini. Kartu-kartu yang lain dengan lambang yang sama yaitu kartu misteri tersebut yang harus ditebak oleh sang pesulap. Lalu pengunjung-pengunjung lainnya menunjukkan bahwa kartu yang disembunyikan tersebut mempunyai lambang yang sama dengan kartu pertama yang ditunjukkan. Sedangkan nilai dari kartu misteri tersebut akan bisa didapatkan dengan sedikit trik yaitu dengan ‘perhitungan lingkaran’ kecil.

 8.    Adakah hubungan metode antara kombinasi dan permutasi dalam pigeon hole? Jika ada apa tolong    jelaskan hubungannya!

                        Hubungan metode antara kombinasi dan permutasi dalam pigeon hole ada, yaitu karena metode ini dapat menunjukkan banyaknya suatu susunan yang dapat dibentuk dari suatu kumpulan objek yang berbeda dalam suatu tempat, baik yang dipilih seluruhnya atau sebagian. Selain itu dapat menunjukkan susunan objek yang identik. Dengan demikian, metode ini dapat mencari objek dalam suatu tempat dan dapat menentukan banyaknya objek tersebut. Metode perhitungan ini berguna dalam menyelesaikan masalah yang berhubungan dengan Prinsip Pigeonhole.

Cc :   http://mutiaratyax27.wordpress.com/

        http://intan-ftriani.blogspot.com/

        http://yos3prens.wordpress.com/

Satrio Nugroho kelompok 10