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

Alamat email Anda tidak akan dipublikasikan.

*