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 dan Pembahasan – Relasi Rekursi Linear Homogen dengan Koefisien Konstan

Soal Nomor 1
Tentukan solusi khusus dari relasi rekursi a_n = 2a_{n - 1} dengan a_0 = 3

Penyelesaian

Ubah persamaannya menjadi
a_n -  2a_{n - 1} = 0
Persamaan karakteristik dari relasi rekursi tersebut adalah
r - 2 = 0
r = 2
Solusi umum relasi rekursi dengan akar tunggal adalah
\boxed{a_n = C_1r^n}
Berarti, solusi umum untuk kasus ini adalah a_n = C_1(2)^n
Untuk menentukan nilai C_1, gunakan nilai awal yang telah diberikan, yaitu a_0 = 3
a_0 = C_1(2)^0 = 3
Diperoleh C_1 = 3
Jadi, solusi khusus relasi rekursinya adalah \boxed{a_n = 3(2)^n}

[collapse]

Soal Nomor 2
Tentukan solusi khusus dari relasi rekursi a_n = a_{n - 1} + 2a_{n - 2} dengan a_0 = 2 dan a_1 = 7

Penyelesaian

Ubah persamaan yang diberikan menjadi
a_n - a_{n - 1} - 2a_{n - 2} = 0
Persamaan karakteristik dari relasi rekursi tersebut adalah
r^2 - r - 2 = 0
(r - 2)(r + 1) = 0
Diperoleh r = 2 atau r = -1
Solusi umum relasi rekursi dengan 2 akar berbeda adalah 
\boxed{a_n = C_1r_{1}^n + C_2r_{2}^n}
Berarti, solusi umum berdasarkan nilai r yang telah didapat adalah
a_n = C_1(2)^n + C_2(-1)^n
Untuk mendapatkan nilai C_1 dan C_2, masukkan a_0 = 2 dan a_1 = 7 ke persamaan itu.
a_0 = C_1(2)^0 + C_2(-1)^0 \Rightarrow C_1 + C_2 = 2
a_1 = C_1(2)^1 + C_2(-1)^1 \Rightarrow 2C_1 - C_2 = 7
Selesaikan SPLDV tersebut sehingga diperoleh C_1 = 3 dan C_2 = -1
Jadi, solusi khusus relasi rekursinya adalah \boxed{a_n = 3(2)^n - (-1)^n}

[collapse]

Soal Nomor 3
Tentukan solusi khusus dari relasi rekursi a_n = 6a_{n - 1} -  9a_{n - 2} dengan a_0 = 1 dan a_1 = 6

Penyelesaian

Ubah persamaan yang diberikan menjadi
a_n - 6_{n - 1} + 9a_{n - 2} = 0
Persamaan karakteristik dari relasi rekursi tersebut adalah
r^2 - 6r + 9 = 0
(r - 3)(r - 3) = 0
Diperoleh r = 3 
Solusi umum relasi rekursi dengan 2 akar kembar adalah 
\boxed{a_n = C_1r_{1}^n + C_2nr_{2}^n}
Berarti, solusi umum berdasarkan nilai r yang telah didapat adalah
a_n = C_1(3)^n + C_2n(3)^n
Untuk mendapatkan nilai C_1 dan C_2, masukkan a_0 = 1 dan a_1 = 6 ke persamaan itu.
a_0 = C_1(3)^0 + C_2(0)(3)^0 \Rightarrow C_1  = 1
a_1 = C_1(3)^1 + C_2(1)(3)^1 \Rightarrow 3C_1 + 3C_2= 6
Selesaikan SPLDV tersebut sehingga diperoleh C_1 = C_2 = 1
Jadi, solusi khusus relasi rekursinya adalah \boxed{a_n = 3^n + n(3)^n}

[collapse]

Soal Nomor 4
Tentukan solusi khusus dari relasi rekursi a_n = 5a_{n - 1} -  6a_{n - 2} dengan a_0 = 1 dan a_1 = 0

Penyelesaian

Ubah persamaan yang diberikan menjadi
a_n - 5a_{n - 1}  +  6a_{n - 2} = 0
Persamaan karakteristik dari relasi rekursi tersebut adalah
r^2 - 5r + 6 = 0
(r - 2)(r - 3) = 0
Diperoleh r = 2 atau r = 3
Solusi umum relasi rekursi dengan 2 akar kembar adalah 
\boxed{a_n = C_1r_{1}^n + C_2nr_{2}^n}
Berarti, solusi umum berdasarkan nilai r yang telah didapat adalah
a_n = C_1(2)^n + C_2(3)^n
Untuk mendapatkan nilai C_1 dan C_2, masukkan a_0 = 1 dan a_1 = 0 ke persamaan itu.
a_0 = C_1(2)^0 + C_2(3)^0 \Rightarrow C_1 + C_2 = 1
a_1 = C_1(2)^1 + C_2(3)^1 \Rightarrow 2C_1 + 3C_2= 0
Selesaikan SPLDV tersebut sehingga diperoleh C_1 = 3 dan C_2 = -2
Jadi, solusi khusus relasi rekursinya adalah \boxed{a_n = 3(3)^n - 2(3)^n = 3^{n+1} - 2(3)^n}

[collapse]

Soal Nomor 5
Tentukan solusi khusus dari relasi rekursi a_n = 6a_{n - 1} - 11a_{n - 2} + 6a_{n - 3}, dengan a_0 = 2, a_1 = 5, dan a_2 = 15

Penyelesaian

Ubah persamaannya menjadi
a_n - 6a_{n - 1} + 11a_{n - 2} - 6a_{n - 3} = 0

Persamaan karakteristik dari relasi rekursi tersebut adalah
r^3 - 6r^2 + 11r - 6 = 0
(r-1)(r-2)(r-3) = 0
Diperoleh r = 1, r = 2, atau r = 3
Solusi umum relasi rekursi dengan 3 akar berbeda adalah 
\boxed{a_n = C_1r_{1}^n + C_2r_{2}^n + C_3r_{3}^n}
Berarti, solusi umum berdasarkan nilai r yang telah didapat adalah
a_n =  C_1(1)^n + C_2(2)^n + C_3(3)^n
a_n = C_1 + C_2(2)^n + C_3(3)^n
Untuk mendapatkan nilai C_1 dan C_2, masukkan a_0 = 2, a_1 = 5, dan a_2 = 15 ke persamaan itu.

a_0 = C_1 + C_2(2)^0 + C_3(3)^0 \Rightarrow C_1 + C_2 + C_3 = 2
a_1 = C_1 + C_2(2)^1 + C_3(3)^1 \Rightarrow C_1 + 2C_2  + 3C_3 = 5
a_2 = C_1 + C_2(2)^2+ C_3(3)^2 \Rightarrow C_1 + 4C_2 + 9C_3 = 15

Selesaikan SPLDV tersebut sehingga diperoleh C_1 = 1, C_2 = -1, dan C_3 = 2
Jadi, solusi khusus relasi rekursinya adalah \boxed{a_n = 1 - 2^n + 2(3)^n }

[collapse]



Soal Nomor 6
Tentukan solusi umum dari relasi rekursi a_{n + 1} = 2na_n + n(n-1)a_{n-1}

Penyelesaian

Bagilah a_{n+1} = 2\,n\,a_n + n(n-1)\,a_{n-1} dengan n! untuk memperoleh
d\frac{a_{n+1}}{n!} = 2\,\dfrac{a_n}{(n-1)!} + \dfrac{a_{n-1}}{(n-2)!}
Misalkan b_n = \dfrac{a_n}{(n-1)!}, sehingga dapat ditulis
b_{n+1} = 2b_n + b_{n - 1}
Bentuk di atas ekuivalen dengan
b_n = 2b_{n - 1} + b_{n - 2}
b_n - 2b_{n - 1} - b_{n - 2} = 0
Persamaan karakteristiknya adalah
r^2 - 2r - 1 = 0
Carilah akar-akarnya dengan menggunakan rumus kuadrat. Selanjutnya, diperoleh r = 1 \pm \sqrt{2}
Dengan demikian, solusi umum untuk b_n adalah
b_n = C_1r_1^n + C_2r_2^n = C_1(1 + \sqrt{2})^n + C_2(1 - \sqrt{2})^n
Solusi umum untuk a_n, yaitu
b_n = \dfrac{a_n}{(n-1)!}
\boxed{a_n = (n-1)!b_n = (n - 1)!~\left(C_1(1 + \sqrt{2})^n + C_2(1 - \sqrt{2})^n\right)}

[collapse]

Soal Nomor 7 (Soal ON-MIPA PT Seleksi Untan Tahun 2017)
Solusi rekursif u_n = 2u_{n - 1}, n \geq 0 di mana u_0 = 3 adalah \cdots
a. 2^{n+2} - 1
b. 3. 2^n
c. 3^n + 2
d. 2. 3^n
e. 3(3^{n+1} - 2)

Penyelesaian

Ubah persamaan rekursifnya menjadi
u_n - 2u_{n-1} = 0
Persamaan karakteristiknya adalah
r - 2 = 0 yang berarti r = 2
Jadi, solusi umumnya adalah u_n = C_1(2)^n
Substitusikan u_0 = 3, sehingga diperoleh
3 = C_1(2)^0 \Leftrightarrow C_1 = 3
Berarti, solusi khusus yang dimaksud adalah \boxed{u_n = 3 . 2^n}
(Jawaban b)

[collapse]

Ayo Beri Rating Postingan Ini