Soal dan Pembahasan – Relasi Rekurensi dengan Fungsi Pembangkit

Anda diharuskan sudah menguasai teknik dekomposisi pecahan parsial karena pada postingan ini, langkah menguraikan bentuk pecahan yang akan didekomposisi akan dilewatkan (skip). Gunakan informasi berikut untuk menjawab soal-soal di bawah.
\boxed{\begin{aligned} & \displaystyle \binom{k} {n} = \binom{k} {k-n} \\ & \sum_{n=1}^{\infty} nx^n = \dfrac{x} {(1-x)^2} \\ & \sum_{n=1}^{\infty} n^2x^n = \dfrac{x^2+x} {(1-x)^3} \end{aligned}}

Soal Nomor 1
Selesaikan relasi rekurensi berikut dengan menggunakan fungsi pembangkit,
a_n - a_{n-1} = 7
dengan a_0 = 1

Penyelesaian

Misalkan a(x) adalah fungsi pembangkit biasa (FPB) untuk menyelesaikan relasi rekurensi ini, maka haruslah
\displaystyle \sum_{n = 1}^{\infty} (a_n - a_{n-1})x^n = 7
Tinjau sukunya satu per satu.
\displaystyle \sum_{n=1}^{\infty} a_nx^n = a(x) - a_0 = a(x) - 1
\displaystyle \sum_{n=1}^{\infty} a_{n-1}x^n = x\sum_{n=1}^{\infty} a_{n-1}x^{n-1} = xa(x)
Jadi, persamaan di atas dapat ditulis,
\begin{aligned}& a(x) - 1 - xa(x) = 7 \\ & (1 - x)a(x) = 8 \\ & a(x) = \dfrac{8}{1-x} = \displaystyle \sum_{n=0}^{\infty} 8x^n \end{aligned}
Jadi, solusi relasi rekurensinya adalah \boxed{a_n = 8} (barisan konstan yang setiap suku-sukunya 8).

[collapse]

Soal Nomor 2
Selesaikan relasi rekurensi
a_n - 2a_{n-1} = 0 dengan a_0 = 3

Penyelesaian

Relasi rekurensi tersebut merupakan relasi rekurensi homogen dengan koefisien konstan yang dapat diselesaikan dengan mudah. Tetapi, kita akan mencoba menggunakan metode fungsi pembangkit.
Misalkan G(x) fungsi pembangkit biasa (FPB) untuk relasi ini, maka haruslah
\begin{aligned} & \displaystyle \sum_{n=1}^{\infty} (a_n - 2a_{n-1})x^n = 0 \\ & \sum_{n=1}^{\infty} a_nx^n - 2x \sum_{n=1}^{\infty} a_{n-1}x^{n-1} = 0 \\ & (G(x) - a_0) - 2xG(x) = 0 \\ & (1 -2x)G(x) = 3 \\ & G(x) = \dfrac{3}{1-2x} = \sum_{n=0}^{\infty} 3(2^n)x^n \end{aligned}
Jadi, solusi relasi rekurensinya adalah \boxed{a_n = 3(2^n)}

[collapse]

Soal Nomor 3
Selesaikan a_n - 3a_{n-1} = n^2, n \geq 1, a_0 = 1

Penyelesaian

Misalkan
\displaystyle G(x) = \sum_{n=0}^{\infty} a_nx^n
sehingga bentuk operator sumasi dari barisan rekursif tersebut dapat ditulis menjadi
\begin{aligned} \displaystyle & \sum_{n=1}^{\infty} (a_n - 3a_{n-1})x^n = \sum_{n=1}^{\infty} n^2x^n \\ & (G(x) -1) - 3xG(x) = \dfrac{x^2+x} {(1-x)^3} \\ & (1-3x)G(x) = \dfrac{x^2+x} {(1-x) ^3} + 1 \\ & G(x) = \dfrac{x^2+x + (1-x)^3}{(1-x)^3(1-3x)} \\ & G(x) = \dfrac{-x^3+4x^2-2x+1}{(1-x)^3(1-3x)} \end{aligned}
Dengan menerapkan teknik dekomposisi pecahan parsial (prosedurnya memang cukup panjang dalam kasus ini), diperoleh
\begin{aligned}G(x) & = \dfrac{-\dfrac{13}{8}} {1-x} + \dfrac{\dfrac{9}{4}} {(1-x)^2} + \dfrac{-\dfrac{5}{2}} {(1-x)^3} + \dfrac{\dfrac{23}{8}} {1-3x} \\ & = -\dfrac{13}{8} \displaystyle \sum_{n=0}^{\infty} x^n + \dfrac{9}{4} \sum_{n=0}^{\infty} \binom{n+1}{n} x^n \\ & - \dfrac{5}{2} \sum_{n=0}^{\infty} \binom{n+2}{n}x^n + \dfrac{23}{8} \sum_{n=0}^{\infty} (3x)^n \\ & = \sum_{n=0}^{\infty} \left(-\dfrac{13}{8} + \dfrac{9}{4} \binom{n+1}{1} - \dfrac{5}{2} \binom{n+2}{2} + \dfrac{23}{8}. 3^n\right)x^n \end{aligned}
Jadi, didapat
\boxed{a_n = -\dfrac{13}{8} + \dfrac{9}{4} \binom{n+1}{1} - \dfrac{5}{2} \binom{n+2}{2} + \dfrac{23}{8}. 3^n}

[collapse]

Soal Nomor 4
Selesaikan a_n = a_{n-1} + n, a_0 = 1.

Penyelesaian

Misalkan
\displaystyle G(x) = \sum_{n=0}^{\infty} a_nx^n
sehingga bentuk operator sumasi dari barisan rekursif tersebut dapat ditulis menjadi
\begin{aligned} \displaystyle & \sum_{n=1}^{\infty} a_nx^n = \sum_{n=1}^{\infty} (a_{n-1} + n)x^n \\ & G(x) -1 = xG(x) + \dfrac{x} {(1-x)^2} \\ & G(x)(1-x) = \dfrac{x} {(1-x)^2} + \dfrac{(1-x)^2}{(1-x)^2} \\ & G(x) = \dfrac{x+(1-x)^2}{(1-x)^2(1-x)} = \dfrac{1-x+x^2}{(1-x)^3} \end{aligned}
Dengan menggunakan teknik dekomposisi pecahan parsial, diperoleh
\begin{aligned} G(x) & = \dfrac{1}{1-x} - \dfrac{1}{(1-x)^2} + \dfrac{1}{(1-x)^3} \\ & =\displaystyle \sum_{n=0}^{\infty} x^n - \sum_{n=0}^{\infty} \binom{n+1}{n} x^n + \sum_{n=0}^{\infty} \binom{n+2}{2}x^n \\ & = \sum_{n=0}^{\infty} \left(1-(n+1)+\binom{n+2}{2}\right)x^n \\ & = \sum_{n=0}^{\infty} \left(-n +\binom{n+2}{2}\right)x^n \end{aligned}
Jadi, barisan eksplisitnya adalah
\boxed{a_n = -n +\binom{n+2}{2}}

[collapse]

Soal Nomor 5 (Soal OSN Pertamina Tahun 2010)
Jika a_n - 3a_{n-1} = 2-2n^2,a_0 = 3, maka a_{99} = \cdots

Penyelesaian

Misalkan
G(x) = \displaystyle \sum_{n=0}^{\infty} a_nx^n dan perhatikan bahwa
\sum_{n=0}^{\infty} x^n = \dfrac{1}{1-x} ekuivalen dengan \sum_{n=1}^{\infty} x^n =\dfrac{1}{1-x} - 1, berarti dapat kita tuliskan bentuk barisan rekursif di atas menjadi
\displaystyle \begin{aligned} & \sum_{n=1}^{\infty} (a_n - 3a_{n-1})x^n = \sum_{n=1}^{\infty} (2-2n^2)x^n \\ & [G(x) - 3] - 3xG(x) = \dfrac{2}{1-x} - 2 - \dfrac{2(x^2+x)} {(1-x)^3} \\ & G(x) = \dfrac{-x^3+3x^2-9x+3}{(1-x)^3(1-3x)} \end{aligned}
Uraikan dengan dekomposisi pecahan parsial untuk mendapatkan
\begin{aligned} \displaystyle G(x) & = \dfrac{2}{(1-x)^3} + \dfrac{1}{1-3x} \\ & = 2 \sum_{n=0}^{\infty} \binom{2+n} {n} x^n + \sum_{n=0}^{\infty} (3x)^n \\ & = \sum_{n=0}^{\infty} \left(2 \binom{2+n} {n} + 3^n\right)x^n \end{aligned}
Jadi, rumus barisan eksplisitnya adalah
\displaystyle a_n = 2 \binom{2+n} {n} + 3^n = 2 \binom{2+n} {2} + 3^n
sehingga
\boxed{a_{99} = 2 \binom{2+99}{99} + 3^{99} = 3^{99} + 99^2 + 299}

[collapse]

Ayo Beri Rating Postingan Ini

Soal Latihan dan Pembahasan – Fungsi Pembangkit (Dasar) Bagian I


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

Soal Nomor 1
Tentukan Fungsi Pembangkit Biasa (FPB) dan Fungsi Pembangkit Eksponensial (FPE) dari barisan (2, 2, 2, 2, …). Lanjutkan membaca “Soal Latihan dan Pembahasan – Fungsi Pembangkit (Dasar) Bagian I”

Ayo Beri Rating Postingan Ini