Soal dan Pembahasan – Fungsi Pembangkit Dasar: Bagian 1

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

When one door of happiness closes, another opens, but often we look so long at the closed door that we do not see the one that has been opened for us.

Soal Nomor 1

Tentukan fungsi pembangkit biasa (FPB) dan fungsi pembangkit eksponensial (FPE) dari barisan $(2, 2, 2, 2, \cdots)$.

Pembahasan

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

[collapse]

Soal Nomor 2

Tentukan FPB dari barisan $(0, 0, 0, 1, 1, 1, 1, \cdots).$

Pembahasan

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 FPB dari barisan $\left(0, 0, \dfrac{1}{2!}, \dfrac{1}{3!}, \dfrac{1}{4!}, \cdots \right).$

Pembahasan

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 FPB dari barisan $\left(\dfrac{1}{3!}, \dfrac{1}{4!}, \dfrac{1}{5!}, \cdots \right).$

Pembahasan

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)$ dengan $a_n = n + 2$.

Pembahasan

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

Pembahasan

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!} + \cdots + \dfrac{1}{n!}$$

Pembahasan

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

Pembahasan

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 FPE dari $(a_n)$ adalah $P(x) = e^x + e^{4x}.$

Pembahasan

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.

Pembahasan

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

[collapse]

Soal Nomor 11

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

Pembahasan

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

[collapse]

Soal Nomor 12

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

Pembahasan

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

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

Pembahasan

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

[collapse]

Soal Nomor 14

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

Pembahasan

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

Pembahasan

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

[collapse]

Lanjutan: $\bigstar\bigstar\bigstar$

Baca: Soal dan Pembahasan – Fungsi Pembangkit Bagian Dasar (Bagian 2)  

One Reply to “Soal dan Pembahasan – Fungsi Pembangkit Dasar: Bagian 1”

Leave a Reply

Your email address will not be published. Required fields are marked *