Pembahasan Soal 10 Fungsi Pembangkit

Soal

Suppose that a valid codeword is an $n$ -digit number in decimal notation containing an even number of 0s. Let $a_n$ denote the number of valid codewords of length $n$ . In Example 3 we showed that the sequence $\{ a_n \}$ satisfies the recurrence relation $a_n = 8a_{n - 1} + 10^{n - 1}$ and the initial condition $a_1 = 9$ . Use generating functions to find an explicit formula for $a_n$ .

Pembahasan

Untuk membuat pekerjaan dengan fungsi pembangkit lebih sederhana dan mudah, diperluas barisan ini dengan menetapkan $a_0 = 1$ ; ketika ditetapkan nilai ini ke $a_0$ dan menggunakan relasi rekurensi (perulangan), didapatkan $a_1 = 8a_0 + 10^0 = 8 + 1 = 9$ , yang konsisten dengan kondisi awal. (Hal ini juga masuk akal karena ada satu kata kode dengan panjang 0—string kosong.) Dengan mengalikan kedua sisi relasi rekurensi (pengulangan) dengan $x^n$ akan didapatkan $a_nx^n = 8a_{n - 1}x^n + 10^{n - 1}x^n$ .

Misalkan $G(x) = \sum_{n = 0}^{\infty} a_nx^n$ adalah fungsi pembangkit dari barisan $a_0, a_1, a_2, \dots$ . Dengan menjumlahkan kedua ruas sisi persamaan terakhir yang dimulai dengan $n = 1$ , didapatkan bahwa

$\begin{align*} G(x) - 1 & = \sum_{n = 1}^{\infty} a_nx^n = \sum_{n = 1}^{\infty} (8a_{n - 1}x^n + 10^{n - 1}x^n) \\ & = 8\sum_{n = 1}^{\infty} a_{n - 1}x^n + \sum_{n = 1}^{\infty} 10^{n - 1}x^n \\ & = 8x\sum_{n = 1}^{\infty} a_{n - 1}x^{n - 1} + x\sum_{n = 1}^{\infty} 10^{n - 1}x^{n - 1} \\ & = 8x\sum_{n = 0}^{\infty} a_nx^n + x\sum_{n = 0}^{\infty} 10^nx^n \\ & = 8xG(x) + \dfrac{x}{1 - 10x}, \end{align*}$

di mana telah digunakan contoh 4 (Fungsi $f(x) = \dfrac{1}{1 - ax}$ adalah fungsi pembangkit dari barisan $1, a, a^2, a^3, \dots$ , karena $\dfrac{1}{1 - ax} = 1 + ax + a^2x^2 + \dots$ ketika $\lvert ax \rvert < 1$ , atau ekuivalennya, untuk $\lvert x \rvert < \dfrac{1}{\lvert a \rvert}$ untuk $a \neq 0$ .) untuk mengevaluasi penjumlahan kedua. Oleh karena itu, didapatkan $G(x) - 1 = 8xG(x) + \dfrac{x}{1 - 10x}$ . Pemecahan untuk $G(x)$ menunjukkan bahwa

$\begin{align*} G(x) - 1 & = 8xG(x) + \dfrac{x}{1 - 10x} \\ G(x) - 8xG(x) & = \dfrac{x}{1 - 10x} + 1 \\ (1 - 8x)G(x) & = \dfrac{x}{1 - 10x} + \dfrac{1 - 10x}{1 - 10x} \\ G(x) & = \dfrac{1 - 9x}{(1 - 8x)(1 - 10x)}. \end{align*}$

Memperluas ruas kanan persamaan ini menjadi ke dalam bentuk pecahan parsial memberikan

$\begin{align*} \dfrac{1 - 9x}{(1 - 8x)(1 - 10x)} & = \dfrac{A}{1 - 8x} + \dfrac{B}{1 - 10x} \\ & = \dfrac{A(1 - 10x) + B(1 - 8x)}{(1 - 8x)(1 - 10x)}. \end{align*}$

Sehingga, $1 - 9x = A(1 - 10x) + B(1 - 8x)$ . Dengan memasukkan nilai $x = 1/10$ maka akan didapatkan

$\begin{align*} 1 - 9x & = A(1 - 10x) + B(1 - 8x) \\ 1 - 9\left(\frac{1}{10}\right) & = A\left(1 - 10 \left(\frac{1}{10}\right)\right) + B\left(1 - 8\left(\frac{1}{10}\right)\right) \\ 1 - \frac{9}{10} & = A(0) + B\left(1 - \frac{8}{10}\right) \\ \frac{1}{10} & = \frac{2}{10}B \Longleftrightarrow B = \frac{1}{10} \cdot \frac{10}{2} = \frac{1}{2}. \end{align*}$

Dengan cara yang sama, dengan memasukkan nilai $x = 1/8$ maka akan didapatkan

$\begin{align*} 1 - 9x & = A(1 - 10x) + B(1 - 8x) \\ 1 - 9\left(\frac{1}{8}\right) & = A\left(1 - 10 \left(\frac{1}{8}\right)\right) + B\left(1 - 8\left(\frac{1}{8}\right)\right) \\ 1 - \frac{9}{8} & = A\left(1 - \frac{10}{8}\right) + B(0) \\ -\frac{1}{10} & = -\frac{2}{10}A \Longleftrightarrow A = \left(-\frac{1}{10}\right) \cdot \left(-\frac{10}{2}\right) = \frac{1}{2}. \end{align*}$

Dengan demikian, $\dfrac{1 - 9x}{(1 - 8x)(1 - 10x)} = \dfrac{\dfrac{1}{2}}{1 - 8x} + \dfrac{\dfrac{1}{2}}{1 - 10x} = \dfrac{1}{2(1 - 8x)} + \dfrac{1}{2(1 - 10x)} = \dfrac{1}{2} \cdot \dfrac{1}{1 - 8x} + \dfrac{1}{2} \cdot \dfrac{1}{1 - 10x} = \dfrac{1}{2}\left(\dfrac{1}{1 - 8x} + \dfrac{1}{1 - 10x}\right)$ .

Sehingga didapatkan $G(x) = \dfrac{1 - 9x}{(1 - 8x)(1 - 10x)} = \dfrac{1}{2}\left(\dfrac{1}{1 - 8x} + \dfrac{1}{1 - 10x}\right)$ . Menggunakan contoh 4 dua kali (sekali dengan $a = 8$ dan sekali dengan $a = 10$ ) menghasilkan

$\begin{align*} G(x) & = \dfrac{1}{2}\left(\dfrac{1}{1 - 8x} + \dfrac{1}{1 - 10x}\right) \\ & = \dfrac{1}{2}\left(\sum_{n = 0}^{\infty} 8^nx^n + \sum_{n = 0}^{\infty} 10^nx^n\right) \\ & = \dfrac{1}{2}\left(\sum_{n = 0}^{\infty} 8^nx^n + 10^nx^n\right) \\ & = \sum_{n = 0}^{\infty} \dfrac{1}{2} (8^n + 10^n)x^n. \end{align*}$

Akibatnya, telah ditunjukkan bahwa $a_n = \dfrac{1}{2} (8^n + 10^n)$ .

Credit: Ramadhani Latief Firmansyah

Video Penjelasan:

Leave A Comment Batalkan balasan

Artikel Terbaru

Komentar