Solusi Relasi Rekurensi Linier Homogen

martha yunanda kombinatorika

Setelah paham tentang pengertian Relasi rekurensi Linear, non-linear, Homogen dan tak homogen. Berikut akan dibahas tentang solusi penyelesaian relasi rekurensi Linear Homogen.

Solusi relasi rekurensi Linear homogen 1

Solusi dari relasi rekurensi $a_n=ca_{n−1}$ , n≥0, c konstan, dan $a_0=A$ dirumuskan dengan $a_n=Ac^n$ .

Pembuktian:
Penyelesaian permasalahan relasi rekurensi linear dilakukan dengan pendekatan awal dimana solusi dari

$a_n=r^n$ , dimana r konstan. Ingat kembali,

$a_n=r^n$ adalah solusi dari relasi rekurensi

$a_n = c_1a_{n_1} + c_2a_{n-2} + \ldots +c_ka_{n-k}$
jika 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 jika dan hanya jika r adalah solusi dari persamaan terakhir.

Contoh Soal dan Penyelesaian Rekurensi Linear Homogen 1
Soal 1:
Solusi relasi rekurensi

$a_n=7a_{n−1}$ , dimana n≥0 dan

$a_2=98$ !

Pembahasan:
Bentuk alternatif dari relasi

$a_n=7a_{n−1}$ untuk n≥0 dan

$a_2=98$ . Oleh karena itu solusi umumnya mempunyai bentuk

$a_n=a_0(7^n)$ . Karena

$a_2=98=a_0(7^2), akibatnya$ a_0=2

$, dan$ a_n=2(7^n)$ untuk n≥0.

Soal 2:
Temukan

$a_{12}$ jika

$a^2_n=5a^2_{n−1}$ ; dimana

$a_n$ >0 untuk n≥0, dan

$a_0$ =2

Pembahasan:

Walau relasi rekurensi ini tak-linear, jika dimisalkan

$b_n=a^2_n$ , maka diperoleh relasi yang baru

$b_n=5b_{n−1}$ untuk n≥0, dan

$b_0=4$ , yang merupakan relasi 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 relasi rekurensi Linear homogen 2

Misal $c_1$ dan $c_2$ adalah bilangan real. Misalkan pula $r^2−c_1^r−c_2=0$ memiliki dua akar berbeda yaitu $r_1$ dan $r_2$ . Maka barisan ( $a_n$ ) adalah solusi dari relasi rekurensi $a_n=c_1a_{n-1}+c_2a_{n-2}$ jika dan hanya jika $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ untuk n = 0,1,2,...., dimana α1 dan α2 konstan.

Pembuktian:
Akan digunakan 2 proposisi dalam pembuktian ini,
(i) jika

$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 relasi rekurensi

Karena

$r_1$ dan

$r_2$ adalah 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$ adalah solusi rekurensi.

(ii) jika 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$ ) adalah solusi relasi 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 relasi rekurensi$ a_n=2(a_{n−1}−a_{n−2})

$, dimana n≥2 dan$ a_0=1

$,$ a_2=2

$. Pembahasan: Persamaan karakteristik dari relasi rekurensi tersebut adalah$ r^2−2r+2=0

$, dan akar-akarnya adalah$ r_1=1+i

$dan$ r_2=1−i

$. Sehingga, barisan ($ a_n

$) adalah solusi relasi rekurensi tersebut jika 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 relasi 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 relasi rekurensi Linear homogen 3

Misal $c_1$ dan $c_2$ adalah bilangan real dengan $c_2≠0$ . Misalkan pula $r^2−c_1r−c_2=0$ memiliki akar kembar yaitu $r_1=r_2=r$ . Maka barisan ( $a_n$ ) adalah solusi dari relasi rekurensi $a_n=c_1a_{n−1}+c_2a_{n−2}$ jika dan hanya jika $a_n=\alpha_1r^n+\alpha_2nr^n$ untuk n = 0,1,2,...., dimana α1 dan α2 konstan.

Contoh Soal
Carilah solusi dari relasi 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$ adalah r=3. Sehingga, solusi dari relasi 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 menyelesaikan kedua persamaan di atas, diperoleh nilai α1=1 dan α2=1. Akibatnya, solusi dari relasi rekurensi tersebut,

$\begin{align*} a_n=3^n + n3^n.\end{align*}$

solusi relasi rekurensi linier homogen jika ordenya lebih dari dua

Misalkan

$c_1,c_2,…,c_k$ adalah bilangan real. Misalkan pula persamaan karakteristik

$\begin{align*} r^k-c_1r^{k-1}-\ldots- c_k =0 \end{align*}$ memiliki k akar yang berbeda yaitu $r_1,r_2,…,r_k$ . Maka barisan ( $a_n$ ) adalah solusi dari relasi rekurensi $\begin{align*} a_n=c_1a_{n-1}+c_2a_{n-2}+\ldots+c_ka_{n-k} \end{align*}$ jika dan hanya jika $\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 relasi 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 relasi rekurensi ini adalah

$r^3 - 6r^2 + 11r -6 = 0$ akar-akar karakteristiknya adalah

$r_1=1,r_2=2, r_3=3$ , karena

$r^3 - 6r^2 + 11r -6 = (r-1)(r-2)(r-3)$

solusi relasi 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 bisa disebut,

$a_n= 1 - 2^n + 2.3^n$

solusi rekurensi linier homogen orde lebih dari dua jika persamaan karakteristiknya memiliki 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$

memiliki t akar yang berbeda yaitu

$r_1$ sebanyak

$m_1$ ,

$r_2$ sebanyak

$m_2$ ,...,

$r_t$ sebanyak

$m_t$ sedemikian hingga

$m_i$ ≥1 dengan i=1,2,…,t dan

$m_1+m_2+…,m_t=k$ . Maka

barisan (

$a_n$ ) adalah solusi dari relasi rekurensi

$a_n=c_1a_{n-1}+c_2a_{n-2}+\ldots+c_ka_{n-k}$

jika 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 relasi 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 relasi rekurensi ini adalah

$r^3 + 3r^2 + 3r + 1 = 0$ sebab Karena

$r^3 + 3r^2 + 3r + 1 =(r+1)^3$ , r=-1

solusi relasi 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 bisa ditulis,