Lewati ke konten utama

Subbab 9.5 Memformalkan pendekatan kita terhadap persamaan rekurensi

Sejauh ini, pendekatan kita untuk menyelesaikan persamaan rekurensi didasarkan pada intuisi, dan kita belum banyak menjelaskan mengapa solusi-solusi yang diberikan merupakan solusi umum. Dalam bagian ini, kita berusaha memperbaiki kekurangan tersebut. Pengetahuan tentang bahasa aljabar linear akan berguna untuk sisa bagian ini, tetapi tidak mutlak diperlukan.
Teknik kita untuk menyelesaikan persamaan rekurensi berakar pada suatu konsep yang sangat penting dalam matematika, yakni ruang vektor. Ingatlah bahwa ruang vektor
 1 
Agar lebih lengkap, seharusnya kita mengatakan bahwa yang dibicarakan ialah ruang vektor atas medan bilangan real. Namun, dalam mata kuliah kita, hanya jenis ruang vektor inilah yang akan ditinjau. Karena itu, kita cukup menggunakan frasa singkat “ruang vektor”.
terdiri atas himpunan \(V\) yang elemen-elemennya disebut vektor; selain itu, terdapat operasi biner yang disebut penjumlahan, dengan jumlah vektor \(x\) dan \(y\) dinyatakan oleh \(x+y\text{;}\) selanjutnya, terdapat operasi yang disebut perkalian skalar, yang menggabungkan skalar (bilangan real) \(\alpha\) dan vektor \(x\) untuk membentuk hasil kali yang dinyatakan oleh \(\alpha x\text{.}\) Operasi-operasi ini memenuhi sifat-sifat berikut:
  1. \(x+y=y+x\) untuk setiap \(x,y\in V\text{.}\)
  2. \(x+(y+z) = (x+y)+z\text{,}\) untuk setiap \(x,y,z\in V\text{.}\)
  3. Terdapat vektor yang disebut nol dan dinyatakan oleh \(0\) sedemikian sehingga \(x+0=x\) untuk setiap \(x\in V\text{.}\) Catatan: Sekali lagi, kita menggunakan simbol \(0\) untuk sesuatu selain bilangan.
  4. Untuk setiap elemen \(x\in V\text{,}\) terdapat elemen \(y\in V\) yang disebut invers aditif dari \(x\) dan dinyatakan oleh \(-x\text{,}\) sedemikian sehingga \(x+(-x)=0\text{.}\) Sifat ini memungkinkan kita mendefinisikan pengurangan, i.e., \(x-y= x+(-y)\text{.}\)
  5. \(1x=x\) untuk setiap \(x\in V\text{.}\)
  6. \(\alpha(\beta x) = (\alpha\beta)x\text{,}\) untuk setiap \(\alpha,\beta\in\reals\) dan setiap \(x\in V\text{.}\)
  7. \(\alpha(x+y)=\alpha x + \alpha y\) untuk setiap \(\alpha\in\reals\) dan setiap \(x,y\in V\text{.}\)
  8. \((\alpha +\beta) x = \alpha x + \beta x\text{,}\) untuk setiap \(\alpha,\beta\in\reals\) dan setiap \(x\in V\text{.}\)
Jika \(V\) merupakan ruang vektor, fungsi \(\phi\colon V\rightarrow V\) disebut operator linear, atau cukup operator, apabila \(\phi(x+y)=\phi(x)+\phi(y)\) dan \(\phi(\alpha x)=\alpha\phi(x)\text{.}\) Jika \(\phi\colon V\rightarrow V\) merupakan operator, lazimnya kita menuliskan \(\phi x\text{,}\) bukan \(\phi(x)\text{,}\) sehingga menghemat sepasang tanda kurung. Himpunan semua operator pada ruang vektor \(V\) itu sendiri merupakan ruang vektor, dengan penjumlahan yang didefinisikan oleh \((\phi+\rho)x = \phi x +\rho x\) dan perkalian skalar oleh \((\alpha\phi)x=\alpha(\phi x)\text{.}\)
Dalam bab ini, kita berfokus pada ruang vektor real \(V\) yang terdiri atas semua fungsi berbentuk \(f\colon\ints\rightarrow\reals\text{.}\) Penjumlahan didefinisikan oleh \((f+g)(n)= f(n)+g(n)\text{,}\) sedangkan perkalian skalar didefinisikan oleh \((\alpha f)(n)=\alpha(f(n))\text{.}\)

Subbagian 9.5.1 Teorema Utama

Berikut adalah teorema dasar tentang penyelesaian persamaan rekurensi (yang dinyatakan dalam bentuk persamaan operator pemajuan)—dan meskipun kita tidak akan membuktikan hasil lengkapnya, kita akan memberikan kerangka yang cukup lengkap sehingga perincian yang hilang tidak terlalu sulit untuk dilengkapi.
Kesimpulan bahwa himpunan \(W\) dari semua solusi merupakan subruang dari \(V\) dapat langsung diperoleh, sebab
\begin{equation*} p(A)(f+g)=p(A)f+p(A)g\quad\text{ dan } \quad p(A)(\alpha f)=\alpha p(A)(f). \end{equation*}
Bagian yang memerlukan sedikit usaha ialah menunjukkan bahwa \(W\) merupakan subruang berdimensi \(k\text{.}\) Setelah hal itu terbukti, untuk menyelesaikan persamaan operator pemajuan dalam bentuk yang diberikan pada Teorema 9.18, cukup dicari suatu basis bagi ruang vektor \(W\text{.}\) Setiap solusi hanyalah kombinasi linear dari vektor-vektor basis. Dalam beberapa subbagian berikut, kita menguraikan cara mencapai tujuan tersebut.

Subbagian 9.5.2 Kasus Awal

Pengembangannya berlangsung melalui induksi (mengejutkan, bukan?), dengan kasus \(k=1\) sebagai kasus dasar. Dalam kasus ini, kita mempelajari persamaan sederhana berbentuk \((c_0A+c_1)f=0\text{.}\) Setelah membagi dengan \(c_0\) dan menuliskannya kembali menggunakan pengurangan, bukan penjumlahan, jelas bahwa yang kita hadapi hanyalah persamaan berbentuk \((A-r)f=0\) dengan \(r\neq0\text{.}\)

Bukti.
Pertama, kita menunjukkan bahwa \(f(n)=cr^n\) untuk setiap \(n\ge0\) melalui induksi pada \(n\text{.}\) Kasus dasarnya langsung diperoleh karena \(c=f(0) = cr^0\text{.}\) Sekarang, misalkan \(f(k)=cr^k\) untuk suatu bilangan bulat tak negatif \(k\text{.}\) Maka \((A-r)f=0\) menyiratkan \(f(k+1)-rf(k)=0\text{,}\) i.e.,
\begin{equation*} f(k+1)=rf(k)= rcr^k=cr^{k+1}. \end{equation*}
Argumen yang sangat serupa menunjukkan bahwa \(f(-n) = cr^{-n}\) untuk setiap \(n\ge0\text{.}\)

Bukti.
Misalkan \(f\) merupakan solusi (9.5.1), dan misalkan \(f_1=f-f_0\text{.}\) Maka
\begin{equation*} p(A)f_1 = p(A)(f-f_0)=p(A)f-p(A)f_0=g-g=0. \end{equation*}
Hal ini menyiratkan bahwa \(f_1\in W\) dan \(f=f_0+f_1\text{,}\) sehingga semua solusi (9.5.1) memang memiliki bentuk yang diinginkan.
Dengan menggunakan kedua hasil terdahulu, sekarang kita dapat memberikan kerangka langkah induksi dalam bukti Teorema 9.18, setidaknya untuk kasus ketika polinom dalam operator pemajuan memiliki akar-akar berbeda.

Bukti.
Kasus \(k=1\) diberikan oleh Lema 9.19. Sekarang, misalkan kita telah membuktikan teorema tersebut untuk suatu bilangan bulat positif \(m\text{,}\) lalu perhatikan kasus \(k=m+1\text{.}\) Tuliskan kembali (9.5.3) sebagai
\begin{equation*} (A-r_1)(A-r_2)\dots(A-r_m)[(A-r_{m+1})f]=0. \end{equation*}
Berdasarkan hipotesis induksi, jika \(f\) merupakan solusi (9.5.3), maka \(f\) juga merupakan solusi persamaan nonhomogen
\begin{equation} (A-r_{m+1})f=d_1r_1^n+d_2r_2^n+\dots+d_mr_m^n.\tag{9.5.4} \end{equation}
Untuk mencari solusi partikular \(f_0\) dari (9.5.4), kita mencari solusi berbentuk
\begin{equation} f_0(n)= c_1 r_1^n+c_2 r_2^n+\dots+c_m r_m^n.\tag{9.5.5} \end{equation}
Di sisi lain, perhitungan sederhana menunjukkan bahwa untuk setiap \(i=1,2,\dots,m\text{,}\) kita mempunyai
\begin{equation*} (A-r_{m+1})c_i r_i^n=c_i r_i^{n+1}-r_{m+1}c_i r_i^n=c_i (r_i-r_{m+1})r_i^n, \end{equation*}
sehingga cukup dipilih \(c_i\) sedemikian sehingga \(c_i(r_i-r_{m+1})=d_i\) untuk setiap \(i=1,2,\dots,m\text{.}\) Hal ini dapat dilakukan karena \(r_{m+1}\) berbeda dari \(r_i\) untuk \(i=1,2,\dots m\text{.}\)
Sekarang kita mempunyai solusi partikular \(f_0(n)=\sum_{i=1}^{m} c_i r_i^n\text{.}\) Selanjutnya, kita meninjau persamaan homogen yang bersesuaian, \((A-r_{m+1})f=0\text{.}\) Solusi umum persamaan ini berbentuk \(f_1(n)=c_{m+1}r_{m+1}^n\text{.}\) Dengan demikian, setiap solusi persamaan semula berbentuk
\begin{equation*} f(n)=f_0(n)+f_1(n) = c_1r_1^n+c_2r_2^n+\dots+c_m r_m^n+c_{m+1}r_{m+1}^n, \end{equation*}
persis seperti yang kita inginkan!

Subbagian 9.5.3 Akar Berulang

Bukti yang diberikan dalam bagian sebelumnya dapat dimodifikasi secara langsung untuk memperoleh hasil berikut. Perinciannya kita tinggalkan sebagai latihan.

Subbagian 9.5.4 Kasus Umum

Dengan menggabungkan hasil-hasil pada bagian sebelumnya, kita dapat segera menuliskan solusi umum sebarang persamaan homogen berbentuk \(p(A)f=0\text{,}\) asalkan kita dapat memfaktorkan polinom \(p(A)\text{.}\) Perhatikan bahwa secara umum solusi ini membawa kita ke medan bilangan kompleks, sebab akar polinom berkoefisien real kadang-kadang merupakan bilangan kompleks—dengan bagian imajiner tak nol.
Kita menutup bagian ini dengan satu contoh lagi untuk memperlihatkan betapa cepatnya solusi umum suatu persamaan operator pemajuan homogen \(p(A)f=0\) dapat langsung dibaca, asalkan \(p(A)\) sudah difaktorkan.

Contoh 9.23.

Perhatikan persamaan operator pemajuan
\begin{equation*} (A-1)^5(A+1)^3(A-3)^2(A+8)(A-9)^4f=0. \end{equation*}
Maka setiap solusi berbentuk
\begin{align*} f(n)=\amp c_1+c_2n+c_3n^2+c_4n^3+c_5n^4\\ \amp +c_6(-1)^n+c_7n(-1)^n+c_8n^2(-1)^n\\ \amp +c_93^n+c_{10}n3^n\\ \amp +c_{11}(-8)^n\\ \amp +c_{12}9^n +c_{13}n 9^n+c_{14}n^2 9^n +c_{15}n^39^n. \end{align*}
SblmKe AtasLnjt