Soal dan Pembahasan – Fungsi Pembangkit Dasar: Bagian 1

        Fungsi pembangkit (generating function) adalah salah satu materi kuliah Matematika Diskrit. 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

Soal Nomor 1
Tentukan Fungsi Pembangkit Biasa (FPB) dan Fungsi Pembangkit Eksponensial (FPE) dari barisan $(2, 2, 2, 2, \cdots)$.

Penyelesaian

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,
$$\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}$ 

[collapse]

Soal Nomor 2
Tentukan Fungsi Pembangkit Biasa (FPB) dari barisan $(0, 0, 0, 1, 1, 1, 1, \cdots)$.

Penyelesaian

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}}$.

[collapse]

Soal Nomor 3
Tentukan Fungsi Pembangkit Biasa (FPB) dari barisan $\left(0, 0, \dfrac{1}{2!}, \dfrac{1}{3!}, \dfrac{1}{4!}, \cdots \right)$.

Penyelesaian

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}$.

[collapse]

Soal Nomor 4
Tentukan Fungsi Pembangkit Biasa (FPB) dari barisan $\left(\dfrac{1}{3!}, \dfrac{1}{4!}, \dfrac{1}{5!}, \cdots \right)$

Penyelesaian

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}}$

[collapse]

Soal Nomor 5
Tentukan FPB dari $(a_n), a_n = n + 2$

Penyelesaian

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}}$.

[collapse]

Soal Nomor 6
Tentukan FPB dari $(a_n)$ jika diketahui
$(a_n) = \dfrac{n+1}{n!}$

Penyelesaian

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)}$

[collapse]

Soal Nomor 7
Carilah FPB dari barisan berikut.
$(a_n), a_n = \dfrac{1}{0!} + \dfrac{1}{1!} + \dfrac{1}{2!} + … + \dfrac{1}{n!}$

Penyelesaian

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)}$.

[collapse]

Soal Nomor 8
Tentukan $(a_n)$ jika FPE dari $(a_n)$ adalah $P(x) = 5 + 5x + 5x^2 + \cdots$

Penyelesaian

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)$.

[collapse]

Soal Nomor 9
Tentukan $(a_n)$ jika Fungsi Pembangkit Eksponensial (FPE) dari $(a_n)$ adalah $P(x) = e^x + e^{4x}$.

Penyelesaian

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)$.

[collapse]

Soal Nomor 10
Tentukan bentuk ekspansi dari $\displaystyle \sum_{n=0}^{\infty} nx^n$ dengan menggunakan teorema turunan pada fungsi pembangkit.

Penyelesaian

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
$G'(x) = -1(1-x)^{-2}(-1) = \dfrac{1}{(1-x)^2}$
Misalkan $a_n = 1$ (berarti $na_n = n$, sesuai dengan bentuk yang diminta pada soal), maka dengan menggunakan teorema tersebut, diperoleh bahwa
$$\displaystyle \sum_{n=0}^{\infty} nx^n = xG'(x) = x.\dfrac{1}{(1-x)^2} = \dfrac{x}{(1-x)^2}$$
Jadi, bentuk ekspansi dari $\displaystyle \sum_{n=0}^{\infty} nx^n$ adalah $\boxed{\dfrac{x}{(1-x)^2}}$.

[collapse]

Soal Nomor 11
Tentukan FPB dari barisan $(a_n), a_n = n^23^n$.

Penyelesaian

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)$ (menggunakan Aturan Hasil Kali) adalah
$\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}}$.

[collapse]

Soal Nomor 12
Tentukan $(c_n)$ jika FPB $(c_n)$ adalah $P(x) = x^5\left(\dfrac{1}{1+8x}\right)$

Penyelesaian

Misalkan $P(x) = x^5\left(\dfrac{1}{1+8x}\right)$.
$A(x) = x^5$ merupakan FPB dari $(a_n)$, sedangkan
$\begin{aligned} B(x) & = \dfrac{1}{1+8x} = \dfrac{1}{1-(-8x)} \\ & = 1 + (-8x) + (-8x)^2 + \cdots \end{aligned}$
merupakan FPB dari $(b_n)$.

Dari bentuk tersebut, diperoleh bahwa
$(a_n) = (0, 0, 0, 0, 0, 1, 0, 0, 0, \cdots)$
(Karena koefisien $x^5$ adalah $1$, suku lainnya memiliki koefisien $0$)
$(b_n) = (8^0, -8^1, 8^2, -8^3, \cdots), b_n = (-8)^n$
Sekarang, misalkan $P(x)$ adalah FPB dari $(c_n)$. Dengan menggunakan metode konvolusi, diperoleh
$c_n = \displaystyle \sum_{k=0}^{n}a_kb_{n-k} = \sum_{k=0}^{n}a_k(-8)^{n-k}$
Perhatikan bahwa $a_0 = 0, a_1 = 0, \cdots, a_5 = 1, a_6 = 0, \cdots$.
Untuk $0 \leq n \leq 4, c_n = 0$
Untuk $n = 5$,
$$c_5 = 0 + 0 + 0 + 0 + a_5(-8)^{5-5} = 1(-8)^0 = 1$$

Untuk $n \geq 6, c_n = 1$
Jadi,
$\boxed{(c_n) = (0, 0, 0, 0, 0, 1, 1, 1, 1, \cdots)}$

[collapse]

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$

Penyelesaian

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 preposisi
$$\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)(x+x^2+ \cdots +x^5) \\ & =x^9(x + \cdots + \cdots + \cdots + x^{9}) \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, hasil perkaliannya disingkat saja). Karena koefisien $x$ (dalam ekspresi kurung) adalah $1$, maka dapat disimpulkan bahwa koefisien $x^{10}$ dari ekspresi yang dimaksud pada soal adalah $1$.

[collapse]

Soal Nomor 14
Tentukan $(a_n)$ jika fungsi pembangkit eksponensialnya adalah $e^2(1+x)^8$.

Penyelesaian

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!}$.

[collapse]

Soal Nomor 15
Tentukan $(c_n)$ jika FPB-nya adalah $P(x) = \left(\dfrac{3}{1-x}\right)\left(\dfrac{5}{1-x}\right)$.

Penyelesaian

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).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
$(c_n) = \displaystyle \sum_{n=0}^{n} a_kb_{n-k} = \sum_{n=0}^{n} a_k(n-k+1)$
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{(c_n) = (15, 30, 45, 60, \cdots), c_n = 15(n+1), n \geq 0}$$
$\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$.

[collapse]

Lanjutan: $\bigstar\bigstar\bigstar$
Soal Latihan: Fungsi Pembangkit Dasar: Bagian 2