Fungsi pembangkit (generating function) adalah salah satu materi mata kuliah Matematika Diskret. Materi yang disajikan juga tidak terlalu banyak, tetapi kebanyakan orang kesulitan dalam menyelesaikan persoalan terkait fungsi pembangkit. Untuk mengatasi kesulitan seperti itu, berikut ini disajikan sejumlah soal beserta penyelesaiannya mengenai fungsi pembangkit (bagian dasar) yang sangat cocok untuk Anda yang baru saja mempelajarinya.
Baca Juga: Soal dan Pembahasan – Fungsi Pembangkit untuk Kombinasi
Baca Juga: Soal dan Pembahasan – Fungsi Pembangkit untuk Permutasi
Quote by Helen Keller
Soal Nomor 1
Tentukan fungsi pembangkit biasa (FPB) dan fungsi pembangkit eksponensial (FPE) dari barisan $(2, 2, 2, 2, \cdots)$.
Misalkan $G(x)$ adalah FPB dari $(a_n) = (2, 2, 2, 2, \cdots)$ sehingga menurut definisi FPB,
$$\begin{aligned} G(x) & = a_0x^0 + a_1x + a_2x^2 + a_3x^3 + \cdots \\ & = 2 + 2x + 2x^2 + 2x^3 + \cdots \\ & = 2(1 + x + x^2 + x^3 + \cdots) \end{aligned}$$Perhatikan bahwa bentuk $(1 + x + x^2 + x^3 + \cdots)$ merupakan ekspansi Maclaurin dari $f(x) = \dfrac{1}{1 – x}$ sehingga $G(x)$ dapat ditulis menjadi
$G(x) = 2\left(\dfrac{1}{1-x}\right) = \dfrac{2}{1-x}.$
Jadi, FPB dari barisan tersebut adalah $\boxed{\dfrac{2}{1-x}}$
Misalkan $G(x)$ adalah FPE dari $(a_n) = (2, 2, 2, 2, \cdots)$ sehingga menurut definisi FPE, didapat
$$\begin{aligned} G(x) & = a_0\dfrac{x^0}{0!} + a_1\dfrac{x}{1!} + a_2\dfrac{x^2}{2!} + a_3\dfrac{x^3}{3!} + \cdots \\ & = 2\dfrac{1}{0!} + 2\dfrac{x}{1} + 2\dfrac{x^2}{2!} + 2\dfrac{x^3}{3!} + \cdots \\ & = 2\left(1 + x + \dfrac{1}{2!}x^2 + \cdots \right) \\ & = 2e^x. \end{aligned}$$Jadi, FPE dari barisan tersebut adalah $\boxed{2e^x}$
Soal Nomor 2
Tentukan FPB dari barisan $(0, 0, 0, 1, 1, 1, 1, \cdots).$
Barisan tersebut dikenal sebagai barisan yang tertunda (delayed sequence).
Misalkan $G(x)$ adalah FPB dari $(a_n) = (0, 0, 0, 1, 1, 1, 1, \cdots)$ sehingga menurut definisi FPB, diperoleh
$$\begin{aligned} G(x) & = \displaystyle \sum_{n=0}^{\infty} a_nx^n \\ & = 0 \cdot x^0 + 0 \cdot x + 0 \cdot x^2 + 1 \cdot x^3 + 1 \cdot x^4 + 1 \cdot x^5 + \cdots \\ & = x^3 + x^4 + x^5 + \cdots \\ & = (1 + x + x^2 + x^3 + x^4 + \cdots) -(1 + x + x^2) \\ & = \dfrac{1}{1-x} -\dfrac{(1+x+x^2)(1-x)}{1-x} \\ & = \dfrac{1 -(1 -x^3)}{1-x} = \dfrac{x^3}{1-x}. \end{aligned}$$Jadi, FPB dari barisan tersebut adalah $\boxed{\dfrac{x^3}{1-x}}$
Soal Nomor 3
Tentukan FPB dari barisan $\left(0, 0, \dfrac{1}{2!}, \dfrac{1}{3!}, \dfrac{1}{4!}, \cdots \right).$
Barisan tersebut dikenal sebagai Barisan yang Tertunda (Delayed Sequence).
Misalkan $G(x)$ adalah FPB dari $(a_n) =\left(0, 0, \dfrac{1}{2!}, \dfrac{1}{3!}, \dfrac{1}{4!}, \cdots \right)$ sehingga menurut definisi FPB, diperoleh
$$\begin{aligned} G(x) & = \displaystyle \sum_{n=0}^{\infty} a_nx^n \\ & = 0.x^0 + 0.x + \dfrac{1}{2!}x^2 + \dfrac{1}{3!}x^3 + \dfrac{1}{4!}x^4 + \cdots \\ & = \left(1 + x + \dfrac{1}{2!}x^2 + \dfrac{1}{3!}x^3 + \dfrac{1}{4!}x^4 + \cdots \right) -(1 + x) \\ & = e^x -x- 1. \end{aligned}$$Jadi, FPB dari barisan tersebut adalah $\boxed{e^x -x- 1}$
Soal Nomor 4
Tentukan FPB dari barisan $\left(\dfrac{1}{3!}, \dfrac{1}{4!}, \dfrac{1}{5!}, \cdots \right).$
Misalkan $G(x)$ adalah FPB dari $(a_n) = \left(\dfrac{1}{3!}, \dfrac{1}{4!}, \dfrac{1}{5!}, \cdots \right)$.
Dengan menggunakan definisi FPB, diperoleh
$$\begin{aligned} G(x) & = \displaystyle \sum_{n = 0}^{\infty}a_nx^n \\ & = \dfrac{1}{3!}x^0 + \dfrac{1}{4!}x + \dfrac{1}{5!}x^2 + \cdots \\ & = \dfrac{x^3}{x^3}\left(\dfrac{1}{3!}x^0 + \dfrac{1}{4!}x + \dfrac{1}{5!}x^2 + \cdots \right) \\ & = \dfrac{1}{x^3}\left(\dfrac{1}{3!}x^3 + \dfrac{1}{4!}x^4 + \dfrac{1}{5!}x^5 + \cdots \right) \\ & = \dfrac{1}{x^3}\left[\left(1+ x+ \dfrac{1}{2!}x^2+\dfrac{1}{3!}x^3 + \dfrac{1}{4!}x^4 + \dfrac{1}{5!}x^5 + \cdots \right) -\left(1 + x + \dfrac{1}{2!}x^2\right) \right] \\ & = \dfrac{1}{x^3}\left(e^x -\dfrac{1}{2}x^2 -x -1\right) \\ & = \dfrac{2e^x -x^2 -2x -2}{2x^3}. \end{aligned}$$Jadi, FPB dari barisan tersebut adalah $\boxed{\dfrac{2e^x -x^2 -2x -2}{2x^3}}$
Soal Nomor 5
Tentukan FPB dari $(a_n)$ dengan $a_n = n + 2$.
Misalkan $G(x)$ adalah FPB dari barisan tersebut. Dengan menggunakan definisi FPB, diperoleh
$\begin{aligned} G(x) & = \displaystyle \sum_{n = 0}^{\infty}a_nx^n \\ & = \displaystyle \sum_{n = 0}^{\infty}(n+2)x^n \\ & = \displaystyle \sum_{n = 0}^{\infty}nx^n + 2\sum_{n = 0}^{\infty}x^n \\ & = \dfrac{x}{(1-x)^2} + \dfrac{2}{1-x} \\ & = \dfrac{x + 2(1-x)}{(1-x)^2} \\ & = \dfrac{-x+2}{(1-x)^2}. \end{aligned}$
Jadi, FPB dari barisan tersebut adalah $\boxed{\dfrac{-x+2}{(1-x)^2}}$
Soal Nomor 6
Tentukan FPB dari $(a_n)$ jika diketahui $(a_n) = \dfrac{n+1}{n!}$.
Misalkan $G(x)$ adalah FPB dari $(a_n)$ sehingga berdasarkan definisi FPB, diperoleh
$\begin{aligned} G(x) & = \displaystyle \sum_{n = 0}^{\infty}a_nx^n \\ & = \displaystyle \sum_{n = 0}^{\infty}\left(\dfrac{n+1}{n!}\right)x^n \\ & = \displaystyle \sum_{n = 0}^{\infty}\left(\dfrac{n}{n!}\right)x^n + \sum_{n = 0}^{\infty}\left(\dfrac{1}{n!}\right)x^n. \end{aligned}$
Dengan menguraikan bentuk sigma pada suku pertama dan mengubah bentuk ekspansi suku kedua, diperoleh
$$ \left(0 + x + x^2 + \dfrac{1}{2!}x^3 + \dfrac{1}{3!}x^4 + \cdots \right) + e^x.$$Faktorkan $x$ pada suku pertama untuk mendapatkan
$$\begin{aligned} & x\left(1 + x + \dfrac{1}{2!}x^2 + \dfrac{1}{3!}x^3 + \cdots \right) + e^x \\ & = x.e^x + e^x \\ & = e^x(x + 1). \end{aligned}$$Jadi, FPB dari $(a_n)$ adalah $\boxed{e^x(x+1)}$
Soal Nomor 7
Carilah FPB dari barisan berikut.
$$(a_n), a_n = \dfrac{1}{0!} + \dfrac{1}{1!} + \dfrac{1}{2!} + \cdots + \dfrac{1}{n!}$$
Diketahui bahwa
$$a_n = \dfrac{1}{0!} + \dfrac{1}{1!} + \dfrac{1}{2!} + \cdots + \dfrac{1}{n!} = \displaystyle \sum_{k = 0}^{n} \dfrac{1}{k!}.$$Misalkan $G(x)$ adalah FPB dari $(a_n)$, maka
$\begin{aligned} G(x) & = \displaystyle \sum_{n = 0}^{\infty} a_nx^n \\ & = \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} \dfrac{1}{k!}\right)x^n \\ & = \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} \dfrac{1}{k!}\times 1\right)x^n. \end{aligned}$
Bentuk di atas merupakan hasil konvolusi sehingga
$\begin{aligned} G(x) & = \displaystyle \left(\sum_{n = 0}^{\infty} \dfrac{1}{n!}x^n\right)\left(\sum_{n = 0}^{\infty} 1 \cdot x^n\right) \\ & = e^x\left(\dfrac{1}{1-x}\right). \end{aligned}$
Jadi, FPB dari barisan tersebut adalah $\boxed{e^x\left(\dfrac{1}{1-x}\right)}$
Soal Nomor 8
Tentukan $(a_n)$ jika FPE dari $(a_n)$ adalah $P(x) = 5 + 5x + 5x^2 + \cdots$.
Ingat bahwa bentuk umum FPE sesuai definisinya adalah
$P(x)= \displaystyle \sum_{n = 0}^{\infty}\dfrac{a_n}{n!}x^n$ $(\bigstar)$
Berdasarkan informasi dari soal, dapat kita tuliskan
$\begin{aligned} P(x) & = 5 + 5x + 5x^2 + \cdots \\ & = 5(1 + x + x^2 + \cdots) \\ & = \displaystyle \sum_{n = 0}^{\infty}5x^n \\ & = \displaystyle \sum_{n = 0}^{\infty}\dfrac{5n!}{n!}x^n. \end{aligned}$
Dengan meninjau kembali $(\bigstar)$, bentuk di atas menunjukkan bahwa $\boxed{(a_n), a_n = 5n!}$ merupakan barisan dengan FPE $P(x)$.
Soal Nomor 9
Tentukan $(a_n)$ jika FPE dari $(a_n)$ adalah $P(x) = e^x + e^{4x}.$
Tinjau kembali bahwa jika diberikan $(a_n)$, maka fungsi pembangkit eksponensialnya adalah
$P(x) = \displaystyle \sum_{n=0}^{\infty}\dfrac{a_n}{n!}x^n$ $\bigstar$
Dalam kasus ini, $P(x) = e^x + e^{4x}$ dapat diubah menjadi bentuk sumasi, yaitu
$\begin{aligned} P(x) & = \displaystyle \sum_{n=0}^{\infty}\dfrac{1}{n!}x^n + \sum_{n=0}^{\infty}\dfrac{1}{n!}(4x)^n \\ & =\sum_{n=0}^{\infty}\dfrac{1}{n!}x^n +\sum_{n=0}^{\infty}\dfrac{4^n}{n!}(x)^n \\ &= \sum_{n=0}^{\infty}\dfrac{1+4^n}{n!}x^n. \end{aligned}$
Bandingkan bentuk terakhir yang didapat dengan $\bigstar$. Dapat kita simpulkan bahwa $\boxed{a_n = 1 + 4^n}$ merupakan barisan dengan FPE $P(x)$.
Soal Nomor 10
Tentukan bentuk ekspansi dari $\displaystyle \sum_{n=0}^{\infty} nx^n$ dengan menggunakan teorema turunan pada fungsi pembangkit.
Teorema turunan pada fungsi pembangkit berbunyi:
“$\mathbf{xG'(x)}$ adalah fungsi pembangkit dari $\mathbf{na_n}$, dengan $\mathbf{G'(x)}$ adalah turunan pertama $\mathbf{G(x)}$.”
Beranjak dari bentuk $\displaystyle \sum_{n=0}^{\infty} x^n = \dfrac{1}{1-x}.$
Misalkan $G(x) = \dfrac{1}{1-x} = (1-x)^{-1}.$
Turunan pertama dari $G(x)$ adalah
$\begin{aligned} G'(x) & = -1(1-x)^{-2}(-1) \\ & = \dfrac{1}{(1-x)^2}. \end{aligned}$
Misalkan $a_n = 1$ (berarti $na_n = n$, sesuai dengan bentuk yang diminta pada soal), maka dengan menggunakan teorema tersebut, diperoleh bahwa
$\begin{aligned} \displaystyle \sum_{n=0}^{\infty} nx^n & = xG'(x) \\ & = x \cdot \dfrac{1}{(1-x)^2} \\ & = \dfrac{x}{(1-x)^2}. \end{aligned}$
Jadi, bentuk ekspansi dari $\displaystyle \sum_{n=0}^{\infty} nx^n$ adalah $\boxed{\dfrac{x}{(1-x)^2}}$
Soal Nomor 11
Tentukan FPB dari barisan $(a_n), a_n = n^23^n$.
Langkah pertama adalah kita harus menentukan ekspansi dari $\displaystyle \sum_{n=0}^{\infty} n^2x^n$ dengan menggunakan teorema turunan pada fungsi pembangkit. Kasus ini sebenarnya adalah lanjutan dari soal nomor 10. Sekarang, kita misalkan $G(x) = \dfrac{x}{(1-x)^2} = x(1-x)^{-2}$. Turunan pertama dari $G(x)$ dapat dicari dengan menggunakan Aturan Hasil Kali.
$$\begin{aligned} G'(x) & = -2x(1-x)^{-3}(-1) + (1-x)^{-2} \\ & = \dfrac{2x}{(1-x)^3} + \dfrac{1-x}{(1-x)^3} \\ & = \dfrac{x+1}{(1-x)^3} \end{aligned}$$ $G(x)$ sendiri merupakan hasil ekspansi dari barisan $u_n = n$. Berarti, barisan $b_n = nu_n = n^2$ memiliki fungsi pembangkit
$\begin{aligned} \displaystyle \sum_{n=0}^{\infty} n^2x^n & = xG'(x) = x.\dfrac{x+1}{(1-x)^3} \\ & = \dfrac{x^2 + x}{(1-x)^3} \bigstar\end{aligned}$
Langkah selanjutnya adalah menyelesaikan kasus pada soal.
Misalkan $P(x)$ adalah FPB dari $(a_n)$. Dengan menggunakan definisi FPB, diperoleh
$\begin{aligned} P(x) & = \displaystyle \sum_{n=0}^{\infty}a_nx^n \\ & = \sum_{n=0}^{\infty}(n^23^n)x^n \\ & = \sum_{n=0}^{\infty}n^2(3x)^n. \end{aligned}$
Terapkan $(\bigstar)$ dan perluasan (mengganti $x$ menjadi $3x$) sehingga didapat
$P(x) =\dfrac{(3x)^2 + 3x}{(1-3x)^3} = \dfrac{9x^2+3x}{(1-3x)^3}.$
Jadi, FPB dari barisan tersebut adalah $\boxed{\dfrac{9x^2+3x}{(1-3x)^3}}$
Soal Nomor 12
Tentukan $(c_n)$ jika FPB $(c_n)$ adalah $P(x) = x^5\left(\dfrac{1}{1+8x}\right)$.
Misalkan $P(x) = x^5\left(\dfrac{1}{1+8x}\right)$ merupakan FPB dari $(c_n).$ Perhatikan bahwa
$$\begin{aligned} P(x) & = x^5 \displaystyle \sum_{n=0}^{\infty} (-8x)^n \\ & = \displaystyle \sum_{n=0}^{\infty} (-8)^n \cdot x^{n+5} \\ & = (-8)^0x^5 + (-8)^1x^6 + (-8)^2x^7 + (-8)^3x^8 + \cdots \\ & = x^5 -8x^6+64x^7-512x^8+\cdots. \end{aligned}$$Dari sini, dapat disimpulkan bahwa $$(c_n) = (0, 0, 0, 0, 0, 1, -8, 64, -512, \cdots).$$
Soal Nomor 13
Tentukan koefisien $x^{10}$ dalam ekspresi $(x^3 + x^4 + \cdots)^3(x+x^2+ \cdots +x^5)$ $(1-x^5)^3.$
Tinjau ekspresi $(x^3 + x^4 + \cdots)^3$. Ekspresi tersebut dapat diubah menjadi
$$\begin{aligned} & ((1+x+x^2+x^3+ \cdots) -(1+x+x^2))^3 \\ & =\left(\dfrac{1}{1-x}- \dfrac{(1+x+x^2)(1-x)}{1-x}\right)^3 \\ & =\left(\dfrac{1-(1-x^3)}{1-x}\right)^3 \\ & =x^9\left(\dfrac{1}{1-x}\right)^3 \\ & =x^9(1+x+x^2+ \cdots)^3. \end{aligned}$$Dengan demikian,
$$\begin{aligned}& (x^3 + x^4 + \cdots)^3(x+x^2+\cdots+x^5)(1-x^5)^3 \\ & =x^9(1 +x+x^2 + \cdots)^3(x+x^2+\cdots+x^5)(1-x^5)^3 \\ & =x^9((1+x+x^2+\cdots)(1-x^5))^3(x+x^2+\cdots+x^5). \end{aligned}$$Selanjutnya, gunakan proposisi
$$\begin{aligned} (1 + x + x^2 + \cdots + x^{m-1})^n = (1-x^m)^n(1+x+x^2+\cdots)^n. \end{aligned}$$untuk mendapatkan bentuk
$$\begin{aligned} & x^9(1+x+x^2+x^3+x^4)^3(x+x^2+ \cdots +x^5) \\ & =x^9(x + \cdots + \cdots + \cdots + x^{17}). \end{aligned}$$Perhatikan bahwa kita sedang menentukan koefisien $x^{10}$ sehingga jika dikaitkan dengan bentuk di atas, kita hanya perlu mencari koefisien $x$ dalam ekspresi kurungnya. Oleh karena itu, penulisan hasil perkaliannya disingkat saja dengan cara menuliskan suku pertama dan suku terakhir. Karena koefisien $x$ (dalam ekspresi kurung) adalah $1$, dapat disimpulkan bahwa koefisien $x^{10}$ dari ekspresi yang dimaksud pada soal adalah $1.$
Soal Nomor 14
Tentukan $(a_n)$ jika fungsi pembangkit eksponensialnya adalah $e^2(1+x)^8$.
Misalkan $G(x) = e^2(1+x)^8$. Perhatikan bahwa ekspresi $e^2$ merupakan suatu koefisien. Oleh karenanya, kita hanya perlu meninjau bentuk sumasi dari $(1+x)^8$. Menurut Teorema Binomial,
$\boxed{(1+x)^u = \displaystyle \sum_{n=0}^{\infty} \binom{u}{n}x^n}$
Oleh karena itu, didapat
$G(x) = e^2(1+x)^8 = e^2 \displaystyle \sum_{n=0}^{\infty} \binom{8}{n}x^n$
$ = \displaystyle \sum_{n=0}^{\infty} \dfrac{e^2 \binom{8}{n}n!}{n!}x^n.$
Bandingkan bentuk terakhir dengan definisi FPE, $P(x) = \displaystyle \sum_{n=0}^{\infty}\dfrac{a_n}{n!}x^n.$
Jadi, $\boxed{(a_n) = e^2 \binom{8}{n}n!}$
Soal Nomor 15
Tentukan $(c_n)$ jika FPB-nya adalah $P(x) = \left(\dfrac{3}{1-x}\right)\left(\dfrac{5}{1-x}\right).$
Misalkan
$\begin{aligned} P(x) & = \left(\dfrac{3}{1-x}\right)\left(\dfrac{5}{1-x}\right) \\ & = 15\left(\dfrac{1}{1-x}\right)^2 \\ & = A(x) \cdot B(x). \end{aligned}$
$A(x) = 15$ dengan $(a_n) = (15, 0, 0, 0, 0, \cdots) \bigstar$
$\begin{aligned} B(x) & = \left(\dfrac{1}{1-x}\right)^2 \\ & = 1 + 2x + 3x^2 + 4x^3 + \cdots \end{aligned}$
dengan $(b_n) = (1, 2, 3, 4, \cdots)$ atau $b_n = n+1, n \geq 0.$
Misalkan $P(x)$ FPB dari $(c_n)$. Dengan menggunakan konvolusi, diperoleh
$\begin{aligned} (c_n) & = \displaystyle \sum_{n=0}^{n} a_kb_{n-k} \\ & = \sum_{n=0}^{n} a_k(n-k+1). \end{aligned}$
Untuk $n = 0$, diperoleh
$c_0 = a_0(0-0+1) = 15(1) = 15.$
Untuk $n = 1$, diperoleh
$\begin{aligned} c_1 & = a_1(1-0+1) + a_2(1-1+1) \\ & = 15(2) + 0(1) = 30. \end{aligned}$
Untuk $n = 2$, diperoleh
$$\begin{aligned}c_2 & = a_1(2-0+1) + a_2(2-1+1) + a_3(2-2+1) \\ & = 15(3) + 0(2) + 0(1) = 45. \end{aligned}$$ $\vdots \vdots \vdots$
Jadi, $\boxed{\begin{aligned} (c_n) & = (15, 30, 45, 60, \cdots) \\ c_n & = 15(n+1), n \geq 0 \end{aligned}}$
$\bigstar$ Pertanyaan: Mengapa hanya suku pertama yang bernilai $15$? Jawaban: Dengan meninjau definisi FPB bahwa $P(x) = a_0x^0 + a_1x + a_2x^2 + \cdots$, kita perhatikan bahwa $15$ merupakan suku tanpa variabel, yang berarti koefisien dari $x^0$ sehingga menjadi suku pertama dari barisan yang terbentuk, sedangkan suku lainnya memiliki koefisien $0$.
Lanjutan: $\bigstar\bigstar\bigstar$
Baca: Soal dan Pembahasan – Fungsi Pembangkit Bagian Dasar (Bagian 2)