Soal dan Pembahasan – Relasi Rekurensi dengan Fungsi Pembangkit

Misalkan $G(x)$ adalah fungsi pembangkit biasa (FPB) untuk menyelesaikan relasi rekurensi ini, maka haruslah
$\displaystyle \sum_{n = 1}^{\infty} (a_n- a_{n-1})x^n = 7$
Tinjau sukunya satu per satu.
$\displaystyle \sum_{n=1}^{\infty} a_nx^n = G(x)- a_0 = G(x)- 1$
$\displaystyle \sum_{n=1}^{\infty} a_{n-1}x^n = x\sum_{n=1}^{\infty} a_{n-1}x^{n-1} = xG(x)$
Jadi, persamaan di atas dapat ditulis menjadi
$\begin{aligned} G(x)- 1- xG(x) & = 7 \\ (1- x)G(x) & = 8 \\ G(x) & = \dfrac{8}{1-x} = \displaystyle \sum_{n=0}^{\infty} 8x^n \end{aligned}$
Jadi, solusi relasi rekurensinya adalah $\boxed{a_n = 8}$ (barisan konstan yang setiap suku-sukunya $8$).

Relasi rekurensi tersebut merupakan relasi rekurensi homogen dengan koefisien konstan yang dapat diselesaikan dengan mudah. Tetapi, kita akan mencoba menggunakan metode fungsi pembangkit.
Misalkan $G(x)$ fungsi pembangkit biasa (FPB) untuk relasi ini, maka haruslah
$\begin{aligned} \displaystyle \sum_{n=1}^{\infty} (a_n- 2a_{n-1})x^n & = 0 \\ \sum_{n=1}^{\infty} a_nx^n- 2x \sum_{n=1}^{\infty} a_{n-1}x^{n-1} & = 0 \\ (G(x)- a_0)- 2xG(x) & = 0 \\ (1-2x)G(x) & = 3 \\ G(x) & = \dfrac{3}{1-2x} \\ G(x) & = \sum_{n=0}^{\infty} 3(2^n)x^n \end{aligned}$
Jadi, solusi relasi rekurensinya adalah $\boxed{a_n = 3(2^n)} $

Misalkan $\displaystyle G(x) = \sum_{n=0}^{\infty} a_nx^n$, sehingga bentuk operator sumasi dari barisan rekursif tersebut dapat ditulis menjadi
$$\begin{aligned} \displaystyle \sum_{n=1}^{\infty} (a_n- 3a_{n-1})x^n & = \sum_{n=1}^{\infty} n^2x^n \\ (G(x)-1)- 3xG(x) & = \dfrac{x^2+x} {(1-x)^3} \\ (1-3x)G(x) & = \dfrac{x^2+x} {(1-x) ^3} + 1 \\ G(x) & = \dfrac{x^2+x + (1-x)^3}{(1-x)^3(1-3x)} \\ G(x) & = \dfrac{-x^3+4x^2-2x+1}{(1-x)^3(1-3x)} \end{aligned}$$Dengan menerapkan teknik dekomposisi pecahan parsial (prosedurnya memang cukup panjang dalam kasus ini), diperoleh
$$\begin{aligned}G(x) & = \dfrac{-\dfrac{13}{8}} {1-x} + \dfrac{\dfrac{9}{4}} {(1-x)^2} + \dfrac{-\dfrac{5}{2}} {(1-x)^3} + \dfrac{\dfrac{23}{8}} {1-3x} \\ & =-\dfrac{13}{8} \displaystyle \sum_{n=0}^{\infty} x^n + \dfrac{9}{4} \sum_{n=0}^{\infty} \binom{n+1}{n} x^n \\ &- \dfrac{5}{2} \sum_{n=0}^{\infty} \binom{n+2}{n}x^n + \dfrac{23}{8} \sum_{n=0}^{\infty} (3x)^n \\ & = \sum_{n=0}^{\infty} \left(-\dfrac{13}{8} + \dfrac{9}{4} \binom{n+1}{1}- \dfrac{5}{2} \binom{n+2}{2} + \dfrac{23}{8} \cdot 3^n\right)x^n \end{aligned}$$Jadi, didapat
$$\boxed{a_n =-\dfrac{13}{8} + \dfrac{9}{4} \binom{n+1}{1}- \dfrac{5}{2} \binom{n+2}{2} + \dfrac{23}{8} \cdot 3^n}$$

Misalkan $\displaystyle G(x) = \sum_{n=0}^{\infty} a_nx^n$, sehingga bentuk operator sumasi dari barisan rekursif tersebut dapat ditulis menjadi
$\begin{aligned} \displaystyle \sum_{n=1}^{\infty} a_nx^n & = \sum_{n=1}^{\infty} (a_{n-1} + n)x^n \\ G(x)-1 & = xG(x) + \dfrac{x} {(1-x)^2} \\  G(x)(1-x) & = \dfrac{x} {(1-x)^2} + \dfrac{(1-x)^2}{(1-x)^2} \\ G(x) &= \dfrac{x+(1-x)^2}{(1-x)^2(1-x)} \\ G(x) & = \dfrac{1-x+x^2}{(1-x)^3} \end{aligned}$
Dengan menggunakan teknik dekomposisi pecahan parsial, diperoleh
$$\begin{aligned} G(x) & = \dfrac{1}{1-x}- \dfrac{1}{(1-x)^2} + \dfrac{1}{(1-x)^3} \\ & =\displaystyle \sum_{n=0}^{\infty} x^n- \sum_{n=0}^{\infty} \binom{n+1}{n} x^n + \sum_{n=0}^{\infty} \binom{n+2}{2}x^n \\ & = \sum_{n=0}^{\infty} \left(1-(n+1)+\binom{n+2}{2}\right)x^n \\ & = \sum_{n=0}^{\infty} \left(-n +\binom{n+2}{2}\right)x^n \end{aligned}$$Jadi, barisan eksplisitnya adalah
$\boxed{a_n =-n +\binom{n+2}{2}} $

Misalkan $G(x) = \displaystyle \sum_{n=0}^{\infty} a_nx^n$ dan perhatikan bahwa
$\displaystyle \sum_{n=0}^{\infty} x^n = \dfrac{1}{1-x}$ ekuivalen dengan $\displaystyle \sum_{n=1}^{\infty} x^n =\dfrac{1}{1-x}- 1$, berarti dapat kita tuliskan bentuk barisan rekursif di atas menjadi
$$\displaystyle \begin{aligned} \sum_{n=1}^{\infty} (a_n- 3a_{n-1})x^n & = \sum_{n=1}^{\infty} (2-2n^2)x^n \\ [G(x)- 3]- 3xG(x) & = \dfrac{2}{1-x}- 2- \dfrac{2(x^2+x)} {(1-x)^3} \\ G(x) & = \dfrac{-x^3+3x^2-9x+3}{(1-x)^3(1-3x)} \end{aligned}$$Uraikan dengan dekomposisi pecahan parsial untuk mendapatkan
$\begin{aligned} \displaystyle G(x) & = \dfrac{2}{(1-x)^3} + \dfrac{1}{1-3x} \\ & = 2 \sum_{n=0}^{\infty} \binom{2+n} {n} x^n + \sum_{n=0}^{\infty} (3x)^n \\ & = \sum_{n=0}^{\infty} \left(2 \binom{2+n} {n} + 3^n\right)x^n \end{aligned}$
Jadi, rumus barisan eksplisitnya adalah
$\displaystyle a_n = 2 \binom{2+n} {n} + 3^n = 2 \binom{2+n} {2} + 3^n$
sehingga
$\boxed{\begin{aligned} a_{99} & = 2 \binom{2+99}{99} + 3^{99} \\ & = 3^{99} + 99^2 + 299 \end{aligned}}$