[latexpage]
Soal
Solve the recurrence relation $a_k = 3a_{k – 1}$ for $k = 1, 2, 3, \dots$ and initial condition $a_0 = 2$.
Pembahasan
Misalkan $G(x)$ adalah fungsi pembangkit untuk barisan $\{ a_k \}$, yaitu, $G(x) = \sum_{k = 0}^{\infty} a_kx^k$. Pertama-tama perhatikan bahwa
\begin{align*}
xG(x) & = \sum_{k = 0}^{\infty} a_kx^{k + 1} \\
& = \sum_{k = 1}^{\infty} a_{k – 1}x^k.
\end{align*}
Dengan menggunakan relasi rekurensi (perulangan), didapatkan
\begin{align*}
G(x) – 3xG(x) & = \sum_{k = 0}^{\infty} a_kx^k – 3\sum_{k = 1}^{\infty} a_{k – 1}x^k \\
& = a_0 + \sum_{k = 1}^{\infty} (a_k – 3a_{k-1})x^k \\
& = 2,
\end{align*}
karena $a_0 = 2$ dan $a_k = 3a_{k – 1}$. Dengan demikian, $G(x) – 3xG(x) = (1 – 3x)G(x) = 2$. Pemecahan untuk $G(x)$ menunjukkan bahwa $G(x) = \dfrac{2}{1 – 3x}$. Menggunakan identitas $\dfrac{1}{1 – ax} = \sum_{k = 0}^{\infty} a^kx^k$, didapatkan $G(x) = 2\sum_{k = 0}^{\infty} 3^kx^k = \sum_{k = 0}^{\infty} 2 \cdot 3^kx^k$. Akibatnya, $a_k = 2 \cdot 3^k$.
Credit: Ramadhani Latief Firmansyah
Video Penjelasan:
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]