[latexpage]
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
\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:
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]