Pembahasan Soal 11 Fungsi Pembangkit

Soal

Tentukan bentuk umum dari barisan Fibonacci.

Pembahasan

Barisan Fibonacci mempunyai bentuk yang dibentuk dari fungsi rekursif berikut, $a_n = a_{n - 1} + a_{n - 2}$ , dengan $n \geq 2, a_0 = 0, a_1 = 1$ . Konstruksi fungsi pembangkit untuk barisan Fibonacci sebagai berikut

(1) $\begin{align*} G(x) & = a_0 & + & a_1x^1 & + & a_2x^2 & + & a_3x^3 & + & a_4x^4 & + & \dots \\ xG(x) & = & & a_0x^1 & + & a_1x^2 & + & a_2x^3 & + & a_3x^4 & + & \dots \\ x^2G(x) & = & & & & a_0x^2 & + & a_1x^3 & + & a_2x^4 & + & \dots \end{align*}$

Dari persamaan (1) dikurangi persamaan (2) dan (3), diperoleh

$\begin{align*} G(x) - xG(x) - x^2G(x) & = a_0 + (a_1 - a_0)x^1 + (a_2 - a_1 - a_0)x^2 + \\ &\quad (a_3 - a_2 - a_1)x^3 + (a_4 - a_3 - a_2)x^4 + \dots \\ (1 - x - x^2)G(x) & = 0 + 1x + 0x^2 + 0x^3 + 0x^4 + \dots \\ G(x) & = \dfrac{x}{1 - x - x^2} \end{align*}$

Dengan menggunakan metode pecahan parsial, $G(x)$ dapat dituliskan sebagai

$\begin{align*} \dfrac{x}{1 - x - x^2} & = \dfrac{x}{\dfrac{5}{4} - \left(x + \dfrac{1}{2}\right)^2} \\ & = \dfrac{x}{\left(\sqrt{\dfrac{5}{4}} + \left(x + \dfrac{1}{2}\right)\right)\left(\sqrt{\dfrac{5}{4}} - \left(x + \dfrac{1}{2}\right)\right)} \\ & = \dfrac{x}{\left(\dfrac{\sqrt{5}}{2} + x + \dfrac{1}{2}\right)\left(\dfrac{\sqrt{5}}{2} - x - \dfrac{1}{2}\right)} \\ & = \dfrac{x}{\left(\dfrac{\sqrt{5} + 1}{2} + x\right)\left(\dfrac{\sqrt{5} - 1}{2} - x\right)} \end{align*}$

$\begin{align*} \dfrac{x}{\left(\dfrac{\sqrt{5} + 1}{2} + x\right)\left(\dfrac{\sqrt{5} - 1}{2} - x\right)} & = \dfrac{A}{\dfrac{\sqrt{5} + 1}{2} + x} + \dfrac{B}{\dfrac{\sqrt{5} - 1}{2} - x} \\ & = \dfrac{A\left(\dfrac{\sqrt{5} - 1}{2} - x\right) + B\left(\dfrac{\sqrt{5} + 1}{2} + x\right)}{\left(\dfrac{\sqrt{5} + 1}{2} + x\right)\left(\dfrac{\sqrt{5} - 1}{2} - x\right)} \end{align*}$

Sehingga, $x = A\left(\dfrac{\sqrt{5} - 1}{2} - x\right) + B\left(\dfrac{\sqrt{5} + 1}{2} + x\right)$ . Dengan memasukkan nilai $x = -\dfrac{\sqrt{5} + 1}{2}$ maka akan didapatkan

$\begin{align*} x & = A\left(\dfrac{\sqrt{5} - 1}{2} - x\right) + B\left(\dfrac{\sqrt{5} + 1}{2} + x\right) \\ -\dfrac{\sqrt{5} + 1}{2} & = A\left(\dfrac{\sqrt{5} - 1}{2} + \dfrac{\sqrt{5} + 1}{2}\right) + B\left(\dfrac{\sqrt{5} + 1}{2} - \dfrac{\sqrt{5} + 1}{2}\right) \\ -\dfrac{\sqrt{5} + 1}{2} & = A\left(\dfrac{\sqrt{5} - 1 + \sqrt{5} + 1}{2}\right) + B(0) \\ -\dfrac{\sqrt{5} + 1}{2} & = A\left(\dfrac{2\sqrt{5}}{2}\right) \\ -\dfrac{\sqrt{5} + 1}{2} & = A(\sqrt{5}) \Longleftrightarrow A = -\dfrac{\sqrt{5} + 1}{2\sqrt{5}} \end{align*}$

Dengan cara yang sama, dengan memasukkan nilai $x = \dfrac{\sqrt{5} - 1}{2}$ maka akan didapatkan

$\begin{align*} x & = A\left(\dfrac{\sqrt{5} - 1}{2} - x\right) + B\left(\dfrac{\sqrt{5} + 1}{2} + x\right) \\ \dfrac{\sqrt{5} - 1}{2} & = A\left(\dfrac{\sqrt{5} - 1}{2} - \dfrac{\sqrt{5} - 1}{2}\right) + B\left(\dfrac{\sqrt{5} + 1}{2} + \dfrac{\sqrt{5} - 1}{2}\right) \\ \dfrac{\sqrt{5} - 1}{2} & = A(0) + B\left(\dfrac{\sqrt{5} + 1 + \sqrt{5} - 1}{2}\right) \\ \dfrac{\sqrt{5} - 1}{2} & = B\left(\dfrac{2\sqrt{5}}{2}\right) \\ \dfrac{\sqrt{5} - 1}{2} & = B(\sqrt{5}) \Longleftrightarrow B = \dfrac{\sqrt{5} - 1}{2\sqrt{5}} \end{align*}$

Dengan demikian,

$\begin{align*} \dfrac{x}{1 - x - x^2} & = \dfrac{-\dfrac{\sqrt{5} + 1}{2\sqrt{5}}}{\dfrac{\sqrt{5} + 1}{2} + x} + \dfrac{\dfrac{\sqrt{5} - 1}{2\sqrt{5}}}{\dfrac{\sqrt{5} - 1}{2} - x} \\ & = -\dfrac{\sqrt{5} + 1}{\sqrt{5}(\sqrt{5} + 1) + 2\sqrt{5}x} + \dfrac{\sqrt{5} - 1}{\sqrt{5}(\sqrt{5} - 1) - 2\sqrt{5}x} \\ & = \dfrac{1}{\sqrt{5}}\left[-\dfrac{\sqrt{5} + 1}{\sqrt{5} + 1 + 2x} + \dfrac{\sqrt{5} - 1}{\sqrt{5} - 1 - 2x}\right] \\ & = \dfrac{1}{\sqrt{5}}\left[-\dfrac{\dfrac{\sqrt{5} + 1}{\sqrt{5} + 1}}{\dfrac{\sqrt{5} + 1 + 2x}{\sqrt{5} + 1}} + \dfrac{\dfrac{\sqrt{5} - 1}{\sqrt{5} - 1}}{\dfrac{\sqrt{5} - 1 - 2x}{\sqrt{5} - 1}}\right] \\ \end{align*}$

$\begin{align*} \dfrac{x}{1 - x - x^2} & = \dfrac{1}{\sqrt{5}}\left[-\dfrac{1}{1 + \dfrac{2}{\sqrt{5} + 1}x} + \dfrac{1}{1 - \dfrac{2}{\sqrt{5} - 1}x}\right] \\ & = \dfrac{1}{\sqrt{5}}\left[-\dfrac{1}{1 + \dfrac{\sqrt{5} - 1}{2}x} + \dfrac{1}{1 - \dfrac{\sqrt{5} + 1}{2}x}\right] \\ & = \dfrac{1}{\sqrt{5}}\left[\dfrac{1}{1 - \dfrac{\sqrt{5} + 1}{2}x} - \dfrac{1}{1 - \dfrac{-\sqrt{5} + 1}{2}x}\right] \end{align*}$

Sehingga didapatkan

$\begin{align*} G(x) & = \dfrac{x}{1 - x - x^2} \\ & = \dfrac{1}{\sqrt{5}}\left[\dfrac{1}{1 - \dfrac{\sqrt{5} + 1}{2}x} - \dfrac{1}{1 - \dfrac{-\sqrt{5} + 1}{2}x}\right]. \end{align*}$

Dengan memisalkan

$\begin{align*} p & = \dfrac{\sqrt{5} + 1}{2} \\ q & = \dfrac{-\sqrt{5} + 1}{2} \end{align*}$

Diperoleh, \\
\begin{center}
$G(x) = \dfrac{1}{\sqrt{5}}\left[\dfrac{1}{1 - px} - \dfrac{1}{1 - qx}\right]$
\end{center}

Karena

$\begin{align*} \dfrac{1}{1 - px} & = 1 + px + p^2x^2 + p^3x^3 + \dots \\ \dfrac{1}{1 - qx} & = 1 + qx + q^2x^2 + q^3x^3 + \dots \end{align*}$

Diperoleh,

$\begin{align*} G(x) & = \dfrac{1}{\sqrt{5}}\left[\dfrac{1}{1 - px} - \dfrac{1}{1 - qx}\right] \\ \sqrt{5}G(x) & = 1 + px + p^2x^2 + p^3x^3 + \dots - (1 + qx + q^2x^2 + q^3x^3 + \dots) \\ \sqrt{5}G(X) & = (1 - 1) + (p - q)x + (p^2 - q^2)x^2 + (p^3 - q^3)x^3 + \dots \\ G(x) & = \dfrac{(1 - 1) + (p - q)x + (p^2 - q^2)x^2 + (p^3 - q^3)x^3 + \dots}{\sqrt{5}} \end{align*}$

Jelas bahwa

$\begin{align*} a_n & = \dfrac{p^n - q^n}{\sqrt{5}} \\ & = \dfrac{{{\left(\dfrac{\sqrt{5} + 1}{2}\right)}}^n - {{\left(\dfrac{-\sqrt{5} + 1}{2}\right)}}^n}{\sqrt{5}} \end{align*}$

Sehingga bentuk umum dari barisan Fibonacci adalah

$a_n = \dfrac{{{\left(\dfrac{\sqrt{5} + 1}{2}\right)}}^n - {{\left(\dfrac{-\sqrt{5} + 1}{2}\right)}}^n}{\sqrt{5}}$

Credit: Ramadhani Latief Firmansyah

Video Penjelasan:

S	S	R	K	J	S	M
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Leave A Comment Batalkan balasan

Kalender

Artikel Terbaru

Arsip

Komentar