Lewati ke konten utama

Indeks Sblm Naik Lnjt

\(\newcommand{\set}[1]{\{#1\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\text{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\ds}{\displaystyle} \newcommand{\mbf}[1]{\mathbf{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Subbab 9.2 Persamaan Rekurensi Linear

Apa kesamaan semua contoh pada bagian sebelumnya? Hasil akhir yang berhasil kita peroleh adalah suatu rekurensi linear, yang memberi tahu cara menghitung suku \(n^\text{th}\) suatu barisan jika sejumlah nilai sebelumnya diketahui (dan mungkin juga bergantung secara tak rekursif pada \(n\text{,}\) seperti pada contoh terakhir). Lebih tepatnya, suatu persamaan rekurensi disebut linear jika berbentuk

\begin{equation*} c_0a_{n+k}+ c_1a_{n+k-1} + c_2a_{n+k-2} + \dots+c_ka_{n} = g(n), \end{equation*}

dengan \(k\ge1\) suatu bilangan bulat, \(c_0,c_1,\dots,c_k\) adalah konstanta dengan \(c_0,c_k\neq0\text{,}\) dan \(g:\ints\rightarrow\reals\) suatu fungsi. (Objek yang baru saja kita definisikan sebenarnya lebih tepat disebut persamaan rekurensi linear dengan koefisien konstan, karena kita mensyaratkan agar \(c_i\) merupakan konstanta dan melarangnya bergantung pada \(n\text{.}\) Kita tidak akan memakai penjelas tambahan ini, tetapi akan menyebut persamaan rekurensi linear dengan koefisien tak konstan apabila \(c_i\) diperbolehkan menjadi fungsi dari \(n\text{.}\)) Suatu persamaan linear bersifat homogen jika fungsi \(g(n)\) di ruas kanan adalah fungsi nol. Sebagai contoh, barisan Fibonacci memenuhi persamaan rekurensi linear homogen

\begin{equation*} a_{n+2} - a_{n+1} - a_n = 0. \end{equation*}

Perhatikan bahwa dalam contoh ini, \(k=2\text{,}\) \(c_0=1\text{,}\) dan \(c_k=-1\text{.}\)

Sebagai contoh kedua, barisan dalam Contoh 9.4 memenuhi persamaan rekurensi linear homogen

\begin{equation*} t_{n+2} - 3t_{n+1} + t_n = 0. \end{equation*}

Sekali lagi, \(k=2\) dengan \(c_0=c_k=1\text{.}\)

Di sisi lain, barisan \(r_n\) yang didefinisikan dalam Subbagian 9.1.3 memenuhi persamaan rekurensi linear nonhomogen

\begin{equation*} r_{n+1} - r_{n} = n+1. \end{equation*}

Dalam hal ini, \(k=1\text{,}\) \(c_0=1\text{,}\) dan \(c_k=-1\) .

Tujuan langsung kita adalah mengembangkan teknik untuk menyelesaikan persamaan rekurensi linear, baik yang homogen maupun nonhomogen. Kita akan dapat menuntaskan persoalan penyelesaian persamaan rekurensi linear homogen dan membahas semacam metode “tebak dan uji” yang dapat digunakan untuk menangani jenis nonhomogen yang lebih rumit.

Sblm Ke Atas Lnjt