Matematika Diskrit-Relasi Rekurensi

Posted on

Dalam artikel ini, akan dibahas bagaimana teknik rekursif dapat menghasilkan barisan dan digunakan untuk menyelesaikan masalah penghitungan. Prosedur untuk menemukan suku-suku barisan secara rekursif disebut relasi rekursif.

Relasi rekursif adalah persamaan yang secara rekursif menentukan barisan di mana suku berikutnya merupakan fungsi dari suku-suku sebelumnya.

Contoh: Barisan Fibonacci – F_{ n }=F_{ n-1 }+F_{ n-2 }, Tower Hanoi – F_{ n }=2F_{ n-1 }+1

Relasi Rekursif Linear

Persamaan rekursif linier derajat k atau orde k adalah persamaan rekursif yang dapat dituliskan dalam bentuk:

    \[ x_n= A_1 x_{n-1}+ A_2 x_{n-1}+ A_3 x_{n-1}+ \dots A_k x_{n-k} \]
A_{ n } konstanta dan A_{ k }\ne 0.

Beberapa contoh persamaan rekursif linear:

Relasi RekurensiNilai AwalSolusi
Fn = Fn-1 + Fn-2a1 = a2 = 1Barisan Fibonacci
Fn = Fn-1 + Fn-2a1 = 1, a2 = 3Barisan Lucas
Fn = Fn-2 + Fn-3a1 = a2 = a3 = 1Barisan Padovan
Fn = 2Fn-1 + Fn-2a1 = 0, a2 = 1Barisan Pell

Menyelesaikan Persamaan rekursif linear

Misalkan, relasi rekursif linier derajat dua adalah – F_{ n } = AF_{ n-1 } + BF_{ n - 2 } di mana A dan B adalah bilangan real. Persamaan karakteristik yang sesuai dengan relasi di atas adalah

    \[ x^{ 2 }-Ax-B=0 \]

Terdapat 3 kemungkinan yang terjadi saat mencari akar persamaannya:
Kasus 1 – Jika faktor persamaannya \left( x-x_{ 1 } \right)\left( x-x_{ 2 } \right)=0 dan menghasilkan dua akar real yang berbeda x_{ 1 } \text{ dan } x_{ 2 }, maka F_{ n }=ax_{ 1 }^{ n }+bx_{ 2 }^{ n } merupakan solusi.
Kasus 2 – Jika faktor persamaannya \left( x-x_{ 1 } \right)^{ 2 }=0 dan menghasilkan akar real tunggal x_{ 1 }, maka F_{ n }=anx_{ 1 }^{ n }+bnx_{ 1 }^{ n } merupakan solusi.
Kasus 3 – Jika persamaannya menghasilkan dua akar kompleks atau tidak real, x_{ 1 } \text{ dan } x_{ 2 } dalam bentuk polar x_{ 1 }=r\angle{\theta} dan x_{ 2 }=r\angle{-\theta}, maka F_{ n }=r^{ n }\left( a\cos(n\theta)+b\sin(n\theta) \right) merupakan solusi.



Contoh soal dan pembahasan

Soal 1

Selesaikan relasi rekurensi  F_n = 5F_{n-1} - 6F_{n-2} dengan F_{0  }=1 \text{ dan }F_{1  }=4.

Solusi:

Persamaan karakteristik yang memenuhi

    \[ x^2-5x+6=0  \]
Jadi (x-3)(x-2)=0 dan akar-akarnya adalah x_1 = 3 dan x_2 = 2.

Karena diperoleh akar real berbeda, maka solusinya berbentuk:

    \[ F_n = a3^n + b2^n \]
dengan F_{0 }=1 \text{ dan }F_{1 }=4 diperoleh:

    \begin{align*}1&=F_{ 0 }=a3^0 + b2^0 = a+b\\4 &= F_1 = a3^1 + b2^1 = 3a+2b\end{align*}

Menyelesaikan sistem persamaan tersebut akan diperoleh a=2 dan b=-1, sehingga solusi akhirnya adalah:

    \[ F_n = 2.3^n + (-1) . 2^n = 2.3^n - 2^n \]

Soal 2

Selesaikan relasi rekurensi   F_n = 10F_{n-1} - 25F_{n-2} dengan F_{0  }=3 \text{ dan }F_{1  }=17.

Solusi:

Persamaan karakteristik yang memenuhi

    \[ x^2 - 10x -25 = 0 \]
Jadi (x-5^{ 2 }=0 dan akarnya tunggal x_{ 1 }=5.

Karena diperoleh akar tunggal maka solusinya berbentuk:

    \[ F_n = a5^n + bn5^n \]
dengan F_{0 }=3 \text{ dan }F_{1 }=17 diperoleh:

    \begin{align*}3& = F_0 = a.5^0 + (b)(0.5)^0 = a\\17 &= F_1 = a.5^1 + b.1.5^1 = 5a+5b\end{align*}

Menyelesaikan sistem persamaan tersebut akan diperoleh a=3 dan b=\frac{ 2 }{ 5 }, sehingga solusi akhirnya adalah:

    \[ F_n = 3.5^n +( 2/5) .n.2^n \]

Soal 3

Selesaikan relasi rekurensi  F_n = 2F_{n-1} - 2F_{n-2} dengan F_{0  }=1 \text{ dan }F_{1  }=3.

Solusi:

Persamaan karakteristik yang memenuhi

    \[ x^2 - 2x -2 = 0 \]
Jadi akar-akarnya adalah x_1 = 1+i dan x_2 = 1-i.
Dalam bentuk polar,
x_1 = r \angle \theta dan x_2 = r \angle(- \theta), di mana r = \sqrt 2 dan \theta = \frac{\pi}{4}.

Akar-akarnya adalah imajiner, sehingga bentuk kasus 3 yang akan digunakan. Solusinya:

    \[ F_n = (\sqrt 2 )^n (a \cos(n .\pi/4) + b \sin(n .\pi/4)) \]
dengan F_{0 }=1 \text{ dan }F_{1 }=3 diperoleh:

    \begin{align*}1 &= F_0 = (\sqrt 2 )^0 (a \cos(0 .\pi /4) + b \sin(0 .\pi/4) ) = a\\3 &= F_1 = (\sqrt 2 )^1 (a \cos(1 .\pi/4) + b\ sin(1 . \pi/4) ) = \sqrt 2 ( a/ \sqrt 2 + b/ \sqrt 2)\end{align*}

Menyelesaikan sistem persamaan tersebut akan diperoleh a=1 dan b=2, sehingga solusi akhirnya adalah:

    \[ F_n = (\sqrt 2 )^n (\cos(n .\pi /4 ) + 2 \sin(n .\pi /4 )) \]

Leave a Reply

Your email address will not be published.