Subbab 9.6 Menggunakan fungsi pembangkit untuk menyelesaikan rekurensi

Pendekatan yang telah kita pelajari sejauh ini dalam bab ini bukanlah satu-satunya cara untuk menyelesaikan persamaan rekurensi. Selain itu, pendekatan tersebut pada dasarnya hanya berlaku untuk persamaan rekurensi linear berkoefisien konstan. Pada bagian selanjutnya dalam bab ini, kita akan melihat beberapa contoh penggunaan fungsi pembangkit sebagai alat lain untuk menyelesaikan persamaan rekurensi. Dalam bagian ini, kita akan berfokus pada persamaan rekurensi linear. Dalam Subbab 9.7, kita akan melihat bagaimana fungsi pembangkit dapat menyelesaikan rekurensi nonlinear.

Contoh pertama kita adalah rekurensi homogen yang bersesuaian dengan persamaan operator pemajuan dalam Contoh 9.9.

Contoh 9.24.

Perhatikan persamaan rekurensi \(r_{n}+r_{n-1}-6r_{n-2} = 0\) untuk barisan \(\{r_n\colon n\geq 0\}\) dengan \(r_0=1\) dan \(r_1=3\text{.}\) Barisan ini memiliki fungsi pembangkit

\begin{equation*} f(x) = \sum_{n=0}^\infty r_n x^n = r_0+r_1 x+r_2x^2+r_3x^3+\cdots. \end{equation*}

Sekarang, perhatikan sejenak bentuk fungsi \(xf(x)\text{.}\) Fungsi tersebut memiliki \(r_{n-1}\) sebagai koefisien \(x^n\text{.}\) Demikian pula, dalam fungsi \(-6x^2 f(x)\text{,}\) koefisien \(x^n\) adalah \(-6r_{n-2}\text{.}\)

Apa tujuan semua ini? Jika ketiga fungsi tersebut dijumlahkan, perhatikan apa yang terjadi. Koefisien \(x^n\) menjadi \(r_n+r_{n-1}-6r_{n-2}\text{,}\) yang bernilai \(0\) karena persamaan rekurensinya! Sekarang mari kita lihat bagaimana semua sukunya sejajar:

\begin{align*} f(x) \amp = r_0 + r_1 x + r_2x^2 + r_3 x^3 + \cdots + r_nx^n + \cdots\\ xf(x) \amp = 0 + r_0 x + r_1x^2 + r_2 x^3 + \cdots + r_{n-1}x^n + \cdots\\ -6x^2f(x) \amp = 0 + 0 -6r_0x^2 - 6r_1 x^3 + \cdots - 6r_{n-2}x^n + \cdots \end{align*}

Ketika ruas kiri dijumlahkan, kita memperoleh \(f(x)(1+x-6x^2)\text{.}\) Pada ruas kanan, koefisien \(x^n\) untuk \(n\geq 2\) adalah \(0\) karena persamaan rekurensinya. Namun, dengan menggunakan syarat awal, masih tersisa \(r_0 + (r_0+r_1)x = 1 + 4x\text{.}\) Jadi, kita memperoleh persamaan

\begin{equation*} f(x)(1+x-6x^2)= 1+4x, \end{equation*}

atau \(f(x) = (1+4x)/(1+x-6x^2)\text{.}\) Fungsi pembangkit ini dapat kita uraikan menggunakan pecahan parsial dalam SageMath:

Hasil ini menunjukkan bahwa

\begin{equation*} f(x) = \frac{6}{5}\frac{1}{1-2x}-\frac{1}{5}\frac{1}{1+3 x} = \frac{6}{5}\sum_{n=0}^\infty 2^n x^n -\frac{1}{5} \sum_{n=0}^\infty (-3)^n x^n \text{.} \end{equation*}

Dari sini, kita langsung membaca \(r_n\) sebagai koefisien \(x^n\) dan memperoleh \(r_n = (6/5) 2^n -(1/5)(-3)^n\text{.}\)

Meskipun memerlukan sedikit lebih banyak pekerjaan, metode ini juga dapat digunakan untuk menyelesaikan persamaan rekurensi nonhomogen, sebagaimana diperlihatkan oleh contoh berikut.

Contoh 9.25.

Persamaan rekurensi \(r_n - r_{n-1}-2r_{n-2} = 2^n\) bersifat nonhomogen. Misalkan \(r_0=2\) dan \(r_1=1\text{.}\) Kali ini, untuk menyelesaikan rekurensi tersebut, kita mulai dengan mengalikan kedua ruas dengan \(x^n\text{.}\) Langkah ini menghasilkan persamaan

\begin{equation*} r_nx^n - r_{n-1}x^n-2r_{n-2}x^n = 2^nx^n. \end{equation*}

Jika persamaan ini kita jumlahkan untuk semua nilai \(n\geq 2\text{,}\) kita memperoleh

\begin{equation*} \sum_{n=2}^\infty r_nx^n - \sum_{n=2}^\infty r_{n-1}x^n-2 \sum_{n=2}^\infty r_{n-2}x^n = \sum_{n=2}^\infty 2^nx^n. \end{equation*}

Anda seharusnya segera mengenali bahwa ruas kanan hampir sama dengan \(1/(1-2x)\text{.}\) Namun, suku \(1\) dan \(2x\) tidak ada, sehingga keduanya harus dikurangkan dari bentuk fungsi rasional dari deret tersebut. Sementara itu, pada ruas kiri kita perlu melakukan sedikit lebih banyak pekerjaan.

Jumlah pertama hanya kehilangan dua suku pertama deret, sehingga kita dapat menggantinya dengan \(R(x) - (2+x)\text{,}\) dengan \(R(x)=\sum_{n=0}^\infty r_n x^n\text{.}\) Jumlah kedua hampir sama dengan \(xR(x)\text{,}\) kecuali bahwa suku pertamanya tidak ada. Jadi, jumlah itu sama dengan \(xR(x) - 2x\text{.}\) Jumlah pada suku terakhir hanyalah \(x^2 R(x)\text{.}\) Dengan demikian, persamaannya dapat dituliskan kembali sebagai

\begin{equation*} R(x) - (2+x) -(xR(x)-2x)-2x^2R(x) = \frac{1}{1-2x} - 1- 2x. \end{equation*}

Sedikit manipulasi aljabar kemudian menghasilkan fungsi pembangkit

\begin{equation*} R(x) = \frac{6x^2-5x+2}{(1-2x)(1-x-2x^2)}. \end{equation*}

Fungsi pembangkit ini dapat diuraikan menggunakan pecahan parsial dalam SageMath:

Oleh karena itu, dengan menggunakan Contoh 8.7 untuk fungsi rasional kedua, kita memperoleh

\begin{align*} R(x) \amp = -\frac{1}{9(1-2x)} + \frac{2}{3(1-2x)^2} + \frac{13}{9(1+x)}\\ \amp = -\frac{1}{9} \sum_{n=0}^\infty 2^nx^n + \frac{2}{3}\sum_{n=0}^\infty \binom{n+2-1}{1}2^n x^n + \frac{13}{9}\sum_{n=0}^\infty (-1)^nx^n\text{.} \end{align*}

Dari fungsi pembangkit ini, kita dapat langsung membaca bahwa

\begin{equation*} r_n = -\frac{1}{9}2^n + \frac{2(n+1)}{3}2^{n} + \frac{13}{9}(-1)^n = \frac{5}{9} 2^n + \frac{2}{3}n2^n + \frac{13}{9}(-1)^n\text{.} \end{equation*}

Persamaan rekurensi dalam kedua contoh pada bagian ini juga dapat diselesaikan menggunakan teknik yang telah kita pelajari sebelumnya dalam bab ini. Salah satu kemungkinan manfaat pendekatan fungsi pembangkit untuk persamaan nonhomogen ialah bahwa pendekatan ini tidak mengharuskan kita menentukan bentuk yang sesuai bagi solusi partikular. Namun, metode fungsi pembangkit sering mengharuskan fungsi pembangkit yang dihasilkan diuraikan menggunakan pecahan parsial. Kedua pendekatan memiliki kelebihan dan kekurangan; jadi, kecuali Anda diminta menggunakan metode tertentu, pilihlah metode yang tampak paling sesuai untuk situasi yang dihadapi. Pada bagian berikutnya, kita akan melihat persamaan rekurensi yang paling mudah diselesaikan menggunakan fungsi pembangkit karena persamaan tersebut nonlinear.

Sblm Ke Atas Lnjt