[latexpage]
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:
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]