Soal dan Pembahasan – Relasi Rekurensi dengan Fungsi Pembangkit

Berikut ini penulis sajikan soal & pembahasan mengenai relasi rekurensi dengan melibatkan 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}}$

Today Quote

Orang tidak selalu membutuhkan nasihat. Terkadang yang mereka butuhkan hanyalah tangan untuk dipegang, telinga untuk mendengarkan, dan hati untuk memahami mereka.

Soal Nomor 1
Selesaikan relasi rekurensi  $a_n- a_{n-1} = 7$ dengan menggunakan fungsi pembangkit jika didefinisikan $a_0 = 1$. 

Pembahasan

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

Pembahasan

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} \\ G(x) & = \sum_{n=0}^{\infty} 3(2^n)x^n \end{aligned}$
Jadi, solusi relasi rekurensinya adalah $\boxed{a_n = 3(2^n)} $

[collapse]

Read: Soal dan Pembahasan – Relasi Rekursif Linear Homogen dengan Koefisien Konstan

Soal Nomor 3
Selesaikan $a_n- 3a_{n-1} = n^2$ untuk $n \geq 1$ dan $a_0 = 1$.

Pembahasan

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} \cdot 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} \cdot 3^n}$$

[collapse]

Soal Nomor 4
Selesaikan $a_n = a_{n-1} + n$ jika didefinisikan $a_0 = 1$.

Pembahasan

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)} \\ G(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 \cdot$

Pembahasan

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{\begin{aligned} a_{99} & = 2 \binom{2+99}{99} + 3^{99} \\ & = 3^{99} + 99^2 + 299 \end{aligned}}$

[collapse]

KategoriKombinatorikaTag, , , , ,

Tinggalkan Balasan

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini bila ada kesalahan pengetikan sekecil apapun (typo atau bahasa latex yang error) atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *