Soal dan Pembahasan – Relasi Rekurensi dengan Fungsi Pembangkit

Misalkan $a(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 = a(x) – a_0 = a(x) – 1$
$\displaystyle \sum_{n=1}^{\infty} a_{n-1}x^n = x\sum_{n=1}^{\infty} a_{n-1}x^{n-1} = xa(x)$
Jadi, persamaan di atas dapat ditulis,
$\begin{aligned}& a(x) – 1 – xa(x) = 7 \\ & (1 – x)a(x) = 8 \\ & a(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} = \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)} = \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
$\sum_{n=0}^{\infty} x^n = \dfrac{1}{1-x}$ ekuivalen dengan $\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{a_{99} = 2 \binom{2+99}{99} + 3^{99} = 3^{99} + 99^2 + 299}$