Solusi Kekerabatan Rekurensi Linier Homogen
Setelah paham wacana pengertian Relasi rekurensi Linear, non-linear, Homogen dan tak homogen. Berikut akan dibahas wacana solusi penyelesaian hubungan rekurensi Linear Homogen.
Solusi hubungan rekurensi Linear homogen 1
Pembuktian:
Penyelesaian permasalahan hubungan rekurensi linear dilakukan dengan pendekatan awal dimana solusi dari $a_n=r^n$, dimana r konstan. Ingat kembali, $a_n=r^n$ yaitu solusi dari hubungan rekurensi
$a_n = c_1a_{n_1} + c_2a_{n-2} + \ldots +c_ka_{n-k}$
bila dan hanya jika
$r^n=c_1r^{n-1}+c_2r^{n-2}+ \ldots+c_kr^{n-k}$
Jika disamakan,
$a_n=r^n$
$ c_1a_{n_1} + c_2a_{n-2} + \ldots +c_ka_{n-k}= r^n=c_1r^{n-1}+c_2r^{n-2}+ \ldots+c_kr^{n-k}$
Dibagi $r^{n-k}$ Diperoleh,
$\begin{align*} r^k - c_1r^{k-1} - c_2r^{k-2} - \ldots - c_k = 0 \end{align*}$
Akibatnya:
Barisan ($a_n$) dengan $a_n=r^n$ merupakan solusi bila dan hanya bila r yaitu solusi dari persamaan terakhir.
Contoh Soal dan Penyelesaian Rekurensi Linear Homogen 1
Soal 1:
Solusi hubungan rekurensi $a_n=7a_{n−1}$, dimana n≥0 dan $a_2=98$ !
Pembahasan:
Bentuk alternatif dari hubungan $a_n=7a_{n−1}$ untuk n≥0 dan $a_2=98$. Oleh lantaran itu solusi umumnya mempunyai bentuk $a_n=a_0(7^n)$. Karena $a_2=98=a_0(7^2), akhirnya $a_0=2$, dan $a_n=2(7^n)$ untuk n≥0.
Soal 2:
Temukan $a_{12}$ bila $a^2_n=5a^2_{n−1}$; dimana $a_n$>0 untuk n≥0, dan $a_0$=2
Solusi hubungan rekurensi Linear homogen 2
Akan dipakai 2 proposisi dalam pembuktian ini,
(i) bila $r_1$ dan $r_2$ adalah akar-akar dari persamaan karakteristik, dan α1,α2 konstan, maka barisan (an) dengan $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ merupakan solusi dari hubungan rekurensi
Karena $r_1$ dan $r_2$ yaitu akar - akar dari $r^2−c_1r−c2=0$, maka $r^2_1=c_1r_1+c_2$ dan $r^2_2=c_1r_2+c_2$
Bisa ditulis kesamaan:
$\begin{align*} c_1a_{n-1}+c_2a_{n-2}&=c_1(\alpha_1r_1^{n-1}+\alpha_2r_2^{n-1})+c_2(\alpha_1r_1^{n-2}+\alpha_2r_2^{n-2})\\ &= \alpha_1r_1^{n-2}(c_1r_1+c_2)+\alpha_2r_2^{n-2}(c_1r_2+c_2)\\ &= \alpha_1r_1^{n-2}r_1^2+\alpha_2r_2^{n-2}r_2^2\\ &= \alpha_1r_1^n+\alpha_2r_2^n\\ &=a_n \end{align*}$
Terbukti $a_n$ dengan $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ yaitu solusi rekurensi.
(ii) bila barisan ($a_n$) merupakan solusi, maka $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ untuk α1 dan α2 yang konstan.
misal bahwa ($a_n$) yaitu solusi hubungan rekurensi, dengan syarat awal $a_0=C_0$ dan $a_1=C_1$. Akan ditunjukkan bahwa ada α1 dan α2 yang konstan sehingga barisan ($a_n$) dengan $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ memenuhi syarat awal yang sama. Perhatikan,
$a_0 = C_0 = \alpha_1 + \alpha_2\\ a_1 = C_1 = \alpha_1r_1 + \alpha_2r_2 $
Dari persamaan pertama, diperoleh $\alpha_2=C_0 - \alpha_1$. Dengan mensubstitusikan nilai α2 ke persamaan kedua diperoleh
$\begin{align*} C_1 = \alpha_1r_1 + (C_0 - \alpha_1)r_2 \end{align*}$
Akibatnya
$\begin{align*} C_1 = \alpha_1(r_1 - r_2) + C_0r_2 \end{align*}$
Ini memperlihatkan
$\begin{align*} \alpha_1 = \frac{C_1 - C_0r_2}{r_1 - r_2} \end{align*}$
dan
$\begin{align*} \alpha_2= C_0 - \alpha_1 = C_0 - \frac{C_1 - C_0r_2}{r_1 - r_2}=
\frac{C_0r_1 - C_1}{r_1 - r_2} \end{align*}$ (syarat $r_1 \neq r_2$
memenuhi dua syarat awal (sebagai solusi). Bisa disimpulkan,
Contoh Soal Penyelesaian Rekurensi Linear Homogen 2
Soal 1: Tentukan $(1+\sqrt{3}i)^{10}$
Pembahasan:
Misalkan $z=1+ \sqrt {3i}$, maka $x=1$, $y= \sqrt 3$, r=2, dan θ= \frac { \pi}{3}$.
$\begin{align*} (1+\sqrt{3}i)^{10} &= 2^{10}(cos \ \frac{10\pi}{3} + i \ sin \
\frac{10\pi}{3})\\ &= 2^{10}(cos \ \frac{4\pi}{3} + i \ sin \ \frac{4\pi}{3})\\
&= 2^{10}((-\frac{1}{2}) - (\frac{\sqrt{3}}{2})i)\\ &= (-2^9)(1+\sqrt{3}i) \end{align*}$
Soal 2: Selesaikan hubungan rekurensi $a_n=2(a_{n−1}−a_{n−2})$, dimana n≥2 dan $a_0=1$, $a_2=2$.
Pembahasan:
Persamaan karakteristik dari hubungan rekurensi tersebut yaitu $r^2−2r+2=0$, dan akar-akarnya yaitu $r_1=1+i$ dan $r_2=1−i$. Sehingga, barisan ($a_n$) yaitu solusi hubungan rekurensi tersebut bila dan hanya jika
$ \begin{align*} a_n = \alpha_1(1+i)^n + \alpha_2(1-i)^n, \end{align*}$
Berdasarkan teorema DeMoivre,
$\begin{align*} a_n &= \alpha_1(\sqrt{2})^n(cos \ \frac{n\pi}{4} + i \ sin \
\frac{n\pi}{4}) + \alpha_2(\sqrt{2})^n(cos \ \frac{-n\pi}{4} + i \sin \ \frac{-n\pi}{4})\\ &= \alpha_1(\sqrt{2})^n(cos \ \frac{n\pi}{4} + i \ sin \
\frac{n\pi}{4}) + \alpha_2(\sqrt{2})^n(cos \ \frac{n\pi}{4} - i \ sin \ \frac{n\pi}{4})\\ &= (\sqrt{2})^n(k_1 \ cos \ \frac{n\pi}{4} + k_2 \ \ sin \ \frac{n\pi}{4}) \end{align*}$
dimana $k_1 = \alpha_1+\alpha_2$ dan $k_2=(\alpha_1-\alpha_2)i$. Dengan memasukkan nilai dari syarat awal, akan diperoleh
$\begin{align*} a_0 &= 1 = (\sqrt{2})^0(k_1 \ cos \ 0 + k_2 \ sin \ 0) = k_1\\
a_1 &= 2 = (\sqrt{2})^1(k_1 \ cos \ \frac{\pi}{4} + k_2 \ \ sin \ \frac{\pi}{4}) = 1 + k_2, \end{align*}$
sehingga $k_1=1$ dan $k_2=1$. Jadi, solusi dari hubungan rekurensi $a_n=2(a_{n−1}−a_{n−2})$, dimana n≥2 dan $a_0=1$, $a_2=2$ adalah
$\begin{align*} a_n=(\sqrt{2})^n(\ cos \ \frac{n\pi}{4} + \ \ sin \ \frac{n\pi}{4}), n \geq 0. \end{align*}$
Solusi hubungan rekurensi Linear homogen 3
Contoh Soal
Carilah solusi dari hubungan rekurensi $a_n=6a_{n−1}−9a_{n−2}$ dengan syarat awal $a_0=1$ dan $a_1=6$
Pembahasan:
Akar dari persamaan $r_2−6r+9=0$ yaitu r=3. Sehingga, solusi dari hubungan rekurensi ini adalah
$\begin{align*} a_n=\alpha_13^n + \alpha_2n3^n \end{align*}$
Sumber http://www.marthamatika.com/
Solusi hubungan rekurensi Linear homogen 1
Solusi dari hubungan rekurensi $a_n=ca_{n−1}$, n≥0, c konstan, dan $a_0=A$ dirumuskan dengan $a_n=Ac^n$.
Penyelesaian permasalahan hubungan rekurensi linear dilakukan dengan pendekatan awal dimana solusi dari $a_n=r^n$, dimana r konstan. Ingat kembali, $a_n=r^n$ yaitu solusi dari hubungan rekurensi
$a_n = c_1a_{n_1} + c_2a_{n-2} + \ldots +c_ka_{n-k}$
bila dan hanya jika
$r^n=c_1r^{n-1}+c_2r^{n-2}+ \ldots+c_kr^{n-k}$
Jika disamakan,
$a_n=r^n$
$ c_1a_{n_1} + c_2a_{n-2} + \ldots +c_ka_{n-k}= r^n=c_1r^{n-1}+c_2r^{n-2}+ \ldots+c_kr^{n-k}$
Dibagi $r^{n-k}$ Diperoleh,
$\begin{align*} r^k - c_1r^{k-1} - c_2r^{k-2} - \ldots - c_k = 0 \end{align*}$
Akibatnya:
Barisan ($a_n$) dengan $a_n=r^n$ merupakan solusi bila dan hanya bila r yaitu solusi dari persamaan terakhir.
Contoh Soal dan Penyelesaian Rekurensi Linear Homogen 1
Soal 1:
Solusi hubungan rekurensi $a_n=7a_{n−1}$, dimana n≥0 dan $a_2=98$ !
Pembahasan:
Bentuk alternatif dari hubungan $a_n=7a_{n−1}$ untuk n≥0 dan $a_2=98$. Oleh lantaran itu solusi umumnya mempunyai bentuk $a_n=a_0(7^n)$. Karena $a_2=98=a_0(7^2), akhirnya $a_0=2$, dan $a_n=2(7^n)$ untuk n≥0.
Soal 2:
Temukan $a_{12}$ bila $a^2_n=5a^2_{n−1}$; dimana $a_n$>0 untuk n≥0, dan $a_0$=2
Pembahasan:
Walau hubungan rekurensi ini tak-linear, bila dimisalkan $b_n=a^2_n$, maka diperoleh hubungan yang gres $b_n=5b_{n−1}$ untuk n≥0, dan $b_0=4$, yang merupakan hubungan rekurensi linear dengan solusi $b_n=4(5^n)$. Dengan demikian $a_n=2( \sqrt 5)^n$ untuk n≥0, dan $a_{12}=2( \sqrt 6)^{12}=31250$.Solusi hubungan rekurensi Linear homogen 2
Misal $c_1$ dan $c_2$ yaitu bilangan real. Misalkan pula $r^2−c_1^r−c_2=0$ mempunyai dua akar berbeda yaitu $r_1$ dan $r_2$. Maka barisan ($a_n$) yaitu solusi dari hubungan rekurensi $a_n=c_1a_{n-1}+c_2a_{n-2}$ bila dan hanya bila $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ untuk n = 0,1,2,...., dimana α1 dan α2 konstan.Pembuktian:
Akan dipakai 2 proposisi dalam pembuktian ini,
(i) bila $r_1$ dan $r_2$ adalah akar-akar dari persamaan karakteristik, dan α1,α2 konstan, maka barisan (an) dengan $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ merupakan solusi dari hubungan rekurensi
Karena $r_1$ dan $r_2$ yaitu akar - akar dari $r^2−c_1r−c2=0$, maka $r^2_1=c_1r_1+c_2$ dan $r^2_2=c_1r_2+c_2$
Bisa ditulis kesamaan:
$\begin{align*} c_1a_{n-1}+c_2a_{n-2}&=c_1(\alpha_1r_1^{n-1}+\alpha_2r_2^{n-1})+c_2(\alpha_1r_1^{n-2}+\alpha_2r_2^{n-2})\\ &= \alpha_1r_1^{n-2}(c_1r_1+c_2)+\alpha_2r_2^{n-2}(c_1r_2+c_2)\\ &= \alpha_1r_1^{n-2}r_1^2+\alpha_2r_2^{n-2}r_2^2\\ &= \alpha_1r_1^n+\alpha_2r_2^n\\ &=a_n \end{align*}$
Terbukti $a_n$ dengan $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ yaitu solusi rekurensi.
(ii) bila barisan ($a_n$) merupakan solusi, maka $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ untuk α1 dan α2 yang konstan.
misal bahwa ($a_n$) yaitu solusi hubungan rekurensi, dengan syarat awal $a_0=C_0$ dan $a_1=C_1$. Akan ditunjukkan bahwa ada α1 dan α2 yang konstan sehingga barisan ($a_n$) dengan $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ memenuhi syarat awal yang sama. Perhatikan,
$a_0 = C_0 = \alpha_1 + \alpha_2\\ a_1 = C_1 = \alpha_1r_1 + \alpha_2r_2 $
Dari persamaan pertama, diperoleh $\alpha_2=C_0 - \alpha_1$. Dengan mensubstitusikan nilai α2 ke persamaan kedua diperoleh
$\begin{align*} C_1 = \alpha_1r_1 + (C_0 - \alpha_1)r_2 \end{align*}$
Akibatnya
$\begin{align*} C_1 = \alpha_1(r_1 - r_2) + C_0r_2 \end{align*}$
Ini memperlihatkan
$\begin{align*} \alpha_1 = \frac{C_1 - C_0r_2}{r_1 - r_2} \end{align*}$
dan
$\begin{align*} \alpha_2= C_0 - \alpha_1 = C_0 - \frac{C_1 - C_0r_2}{r_1 - r_2}=
\frac{C_0r_1 - C_1}{r_1 - r_2} \end{align*}$ (syarat $r_1 \neq r_2$
memenuhi dua syarat awal (sebagai solusi). Bisa disimpulkan,
Contoh Soal Penyelesaian Rekurensi Linear Homogen 2
Soal 1: Tentukan $(1+\sqrt{3}i)^{10}$
Pembahasan:
Misalkan $z=1+ \sqrt {3i}$, maka $x=1$, $y= \sqrt 3$, r=2, dan θ= \frac { \pi}{3}$.
$\begin{align*} (1+\sqrt{3}i)^{10} &= 2^{10}(cos \ \frac{10\pi}{3} + i \ sin \
\frac{10\pi}{3})\\ &= 2^{10}(cos \ \frac{4\pi}{3} + i \ sin \ \frac{4\pi}{3})\\
&= 2^{10}((-\frac{1}{2}) - (\frac{\sqrt{3}}{2})i)\\ &= (-2^9)(1+\sqrt{3}i) \end{align*}$
Soal 2: Selesaikan hubungan rekurensi $a_n=2(a_{n−1}−a_{n−2})$, dimana n≥2 dan $a_0=1$, $a_2=2$.
Pembahasan:
Persamaan karakteristik dari hubungan rekurensi tersebut yaitu $r^2−2r+2=0$, dan akar-akarnya yaitu $r_1=1+i$ dan $r_2=1−i$. Sehingga, barisan ($a_n$) yaitu solusi hubungan rekurensi tersebut bila dan hanya jika
$ \begin{align*} a_n = \alpha_1(1+i)^n + \alpha_2(1-i)^n, \end{align*}$
Berdasarkan teorema DeMoivre,
$\begin{align*} a_n &= \alpha_1(\sqrt{2})^n(cos \ \frac{n\pi}{4} + i \ sin \
\frac{n\pi}{4}) + \alpha_2(\sqrt{2})^n(cos \ \frac{-n\pi}{4} + i \sin \ \frac{-n\pi}{4})\\ &= \alpha_1(\sqrt{2})^n(cos \ \frac{n\pi}{4} + i \ sin \
\frac{n\pi}{4}) + \alpha_2(\sqrt{2})^n(cos \ \frac{n\pi}{4} - i \ sin \ \frac{n\pi}{4})\\ &= (\sqrt{2})^n(k_1 \ cos \ \frac{n\pi}{4} + k_2 \ \ sin \ \frac{n\pi}{4}) \end{align*}$
dimana $k_1 = \alpha_1+\alpha_2$ dan $k_2=(\alpha_1-\alpha_2)i$. Dengan memasukkan nilai dari syarat awal, akan diperoleh
$\begin{align*} a_0 &= 1 = (\sqrt{2})^0(k_1 \ cos \ 0 + k_2 \ sin \ 0) = k_1\\
a_1 &= 2 = (\sqrt{2})^1(k_1 \ cos \ \frac{\pi}{4} + k_2 \ \ sin \ \frac{\pi}{4}) = 1 + k_2, \end{align*}$
sehingga $k_1=1$ dan $k_2=1$. Jadi, solusi dari hubungan rekurensi $a_n=2(a_{n−1}−a_{n−2})$, dimana n≥2 dan $a_0=1$, $a_2=2$ adalah
$\begin{align*} a_n=(\sqrt{2})^n(\ cos \ \frac{n\pi}{4} + \ \ sin \ \frac{n\pi}{4}), n \geq 0. \end{align*}$
Solusi hubungan rekurensi Linear homogen 3
Misal $c_1$ dan $c_2$ yaitu bilangan real dengan $c_2≠0$. Misalkan pula $r^2−c_1r−c_2=0$ mempunyai akar kembar yaitu $r_1=r_2=r$. Maka barisan ($a_n$) yaitu solusi dari hubungan rekurensi $a_n=c_1a_{n−1}+c_2a_{n−2}$ bila dan hanya bila $a_n=\alpha_1r^n+\alpha_2nr^n $untuk n = 0,1,2,...., dimana α1 dan α2 konstan.
Contoh Soal
Carilah solusi dari hubungan rekurensi $a_n=6a_{n−1}−9a_{n−2}$ dengan syarat awal $a_0=1$ dan $a_1=6$
Pembahasan:
Akar dari persamaan $r_2−6r+9=0$ yaitu r=3. Sehingga, solusi dari hubungan rekurensi ini adalah
$\begin{align*} a_n=\alpha_13^n + \alpha_2n3^n \end{align*}$
substitusikan nilai dari syarat awal $a_0=1$ dan $a_1=6$ diperoleh
$\begin{align*} a_0&= 1 =\alpha_1\\ a_1&=\alpha_1.3 + \alpha_2.3 \end{align*}$
dengan menuntaskan kedua persamaan di atas, diperoleh nilai α1=1 dan α2=1. Akibatnya, solusi dari hubungan rekurensi tersebut,
$\begin{align*} a_n=3^n + n3^n.\end{align*}$
solusi hubungan rekurensi linier homogen bila ordenya lebih dari dua
Misalkan $c_1,c_2,…,c_k$ yaitu bilangan real. Misalkan pula persamaan karakteristik
$\begin{align*} r^k-c_1r^{k-1}-\ldots- c_k =0 \end{align*}$ mempunyai k akar yang berbeda yaitu $r_1,r_2,…,r_k$. Maka barisan ($a_n$) yaitu solusi dari hubungan rekurensi $ \begin{align*} a_n=c_1a_{n-1}+c_2a_{n-2}+\ldots+c_ka_{n-k} \end{align*}$jika dan hanya bila $\begin{align*} a_n=\alpha_1r_1^n+\alpha_2r_2^n+\ldots+\alpha_kr_k^n \end{align*}$ untuk n = 0,1,2,...., dimana α1,α2,…,αk konstan.
Contoh Soal:
Solusi dari hubungan rekurensi $a_n=6a_{n-1}-11a_{n-2}+6a_{n-3}$ dengan syarat awal $a_0=2, a_1=5, a_2=15 $ adalah...
Pembahasan:
Persamaan karakteristik polinomial hubungan rekurensi ini yaitu $r^3 - 6r^2 + 11r -6 = 0$ akar-akar karakteristiknya yaitu $r_1=1,r_2=2, r_3=3$, lantaran $r^3 - 6r^2 + 11r -6 = (r-1)(r-2)(r-3)$
solusi hubungan rekurensi ini berbentuk
$a_n=\alpha_1.1^n + \alpha_2.2^n + \alpha_3.3^n $
Untuk menemukan nilai α1,α2, dan α3, kita gunakan syarat awal yang telah ditentukan sebelumnya, yaitu $a_0=2, a_1=5, a_2=15 $.
$\begin{align*} a_0 &= 2 = \alpha_1 + \alpha_2 + \alpha_3\\ a_1 &= 5 = \alpha_1 + \alpha_2.2 + \alpha_3.3 \\ a_2 &= 15 = \alpha_1 + \alpha_2.4 + \alpha_3.9 \end{align*}$
Setelah diselesaikan (subtitusi-eliminasi) diperoleh nilai α1=1 , α2=−1, dan α3=2
sehingga solusinya dapat disebut, $a_n= 1 - 2^n + 2.3^n$
solusi rekurensi linier homogen orde lebih dari dua bila persamaan karakteristiknya mempunyai beberapa akar yang kembar
Misalkan $c_1,c_2,…,c_k $adalah bilangan real. Misalkan pula persamaan karakteristik $r^k-c_1r^{k-1}-\ldots- c_k =0 $
mempunyai t akar yang berbeda yaitu $r_1$ sebanyak $m_1$, $r_2$ sebanyak $m_2$ ,..., $r_t$ sebanyak $m_t$ sedemikian sampai $m_i$≥1 dengan i=1,2,…,t dan $m_1+m_2+…,m_t=k$. Maka
barisan ($a_n$) yaitu solusi dari hubungan rekurensi
$a_n=c_1a_{n-1}+c_2a_{n-2}+\ldots+c_ka_{n-k}$
bila dan hanya jika
$\begin{align*} a_n=&(\alpha_{1,0}+\alpha_{1,1}n+\ldots+\alpha_{1,m_1-1}n^{m_1-1})r_1^n\\ &+ (\alpha_{2,0}+\alpha_{2,1}n+\ldots+\alpha_{2,m_2-1}n^{m_2-1})r_2^n\\ &+\ldots+(\alpha_{t,0}+\alpha_{t,1}n+\ldots+\alpha_{t,m_t-1}n^{m_t-1})r_t^n \end{align*}$
untuk n = 0,1,2,...., dimana α$_{i,j}$ konstan untuk 1≤i≤t dan 0≤j≤m$_i$−1
Contoh Soal:
Temukan solusi dari hubungan rekurensi $a_n=-3a_{n-1} - 3a_{n-2} - a_{n-3}$ dengan syarat awal $a_0=1,a_1=−2, a_2=−1$.
Pembahasan:
Persamaan karakteristik dari hubungan rekurensi ini yaitu $r^3 + 3r^2 + 3r + 1 = 0$ alasannya yaitu Karena $r^3 + 3r^2 + 3r + 1 =(r+1)^3$ , r=-1
solusi hubungan rekurensi ini berbentuk
$a_n=\alpha_{1,0}(-1)^n+\alpha_{1,1}n(-1)^n+\alpha_{1,2}n^2(-1)^n $
masukkan syarat awalnya.
$\begin{align*} a_0 &= 1 = \alpha_{1,0}\\ a_1 &= -2 = -\alpha_{1,0} - \alpha_{1,1} - \alpha_{1,2}\\ a_2 &= -1 = \alpha_{1,0} + 2\alpha_{1,1}+ 4\alpha_{1,2} \end{align*}$
Selesaikan tiga persamaan diatas dan diperoleh akan α$_{1,0}$=1,α$_{1,1}$=3, dan α$_{1,2}$=−2
Dan solusinya dapat ditulis,
$a_n=(-1)^n+3n(-1)^n - 2n^2(-1)^n$
Post a Comment for "Solusi Kekerabatan Rekurensi Linier Homogen"