Relasi rekurens (recurrence relation), kadang disebut sebagai relasi pengulangan, adalah persamaan yang secara rekursif mendefinisikan barisan yang sukunya ditentukan oleh satu atau beberapa suku sebelumnya. Banyak sekali masalah yang dapat dimodelkan dalam relasi rekurens, misalnya kasus kelahiran kelinci dan teka-teki Menara Hanoi.
Relasi rekurens memiliki bentuk yang bermacam-macam. Saat membahas relasi rekurens, kita berupaya untuk mencari solusinya, yaitu barisan yang dinyatakan secara eksplisit, bukan rekursif, dan merepresentasikan suku-suku yang sama sebagaimana dinyatakan oleh relasi rekurens tersebut. Beberapa di antaranya dapat dengan mudah diselesaikan secara iteratif atau menggunakan cara tertentu yang juga ampuh. Namun, ada juga relasi rekurens yang sulit untuk diselesaikan.
Di antara itu semua, sejumlah relasi rekurens dengan kriteria tertentu dapat diselesaikan dengan menggunakan prosedur yang sistematis. Kita namai relasi rekurens homogen linear dengan koefisien konstan. Relasi rekurens tersebut menyatakan suku dari suatu barisan sebagai kombinasi linear dari suku-suku sebelumnya. Ada dua alasan utama kita mempelajarinya secara mendalam. Pertama, banyak masalah yang dapat direpresentasikan sebagai relasi rekurens dengan kriteria seperti itu. Kedua, relasi rekurens tersebut dapat diselesaikan dengan cara yang sistematis. Kita mendefinisikannya sebagai berikut.
Definisi: Relasi Rekurens Homogen Linear dengan Koefisien Konstan
$$a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_k a_{n-k}$$dengan $c_1, c_2, \cdots, c_k$ merupakan bilangan real dan $c_k \neq 0.$
Relasi Rekurens Berderajat $\large{k}$
Relasi rekurens $a_n$ dikatakan berderajat $k$ jika $a_n$ dinyatakan dalam $k$ suku sebelumnya pada barisan.
Contoh:
- $a_n = 3a_{n-1}$ merupakan relasi rekurens berderajat $1.$
- $a_n = 5a_{n-2}-3a_{n-1}$ merupakan relasi rekurens berderajat $2.$
- $a_n = \dfrac12a_{n-5}$ merupakan relasi rekurens berderajat $5.$
Relasi Rekurens Linear
Relasi rekurens $a_n$ berderajat $k$ dikatakan linear jika ekspresi $a_{n-i}$ berpangkat satu untuk setiap $1 \le i \le k.$
Perhatikan contoh dan noncontoh berikut.
- $a_n = 4a_{n-1}$ merupakan relasi rekurens linear.
- $a_n = 5a_{n-1} + 3a_{n-2}^2$ bukan relasi rekurens linear karena ekspresi $a_{n-2}$ berpangkat dua.
- $a_n = (7a_{n-3})^3 + 5a_{n-1}$ bukan relasi rekurens linear karena ekspresi $a_{n-3}$ berpangkat tiga.
Relasi Rekurens Homogen
Relasi rekurens $a_n$ dikatakan homogen (homogeneous) jika tidak ada ekspresi yang berdiri sendiri tanpa melibatkan suku sebelumnya dari barisan.
Perhatikan contoh dan noncontoh berikut.
- $a_n = -10a_{n-1} + 5a_{n-2}$ merupakan relasi rekurens homogen.
- $a_n = 4a_{n-3} + 7a_{n-1}-10$ bukan relasi rekurens homogen karena keberadaan ekspresi $-10.$
- $a_n = 4a_{n-2} + 7n$ bukan relasi rekurens homogen karena keberadaan ekspresi $7n.$
Relasi Rekurens dengan Koefisien Konstan
Relasi rekurens $a_n$ berderajat $k$ dikatakan berkoefisien konstan jika setiap koefisien dari ekspresi $a_{n-i}$ dengan $1 \le i \le k$ merupakan konstanta yang nilainya tidak bergantung pada $n.$
Perhatikan contoh dan noncontoh berikut.
- $a_n = \sqrt2 a_{n-3}$ merupakan relasi rekurens berderajat $3$ dengan koefisien konstan.
- $a_n = n a_{n-2} + 4a_{n-1}$ merupakan relasi rekurens berderajat $2$ dengan koefisien tidak konstan. Hal ini dikarenakan koefisien $a_{n-2}$ yang tidak berupa konstanta, yaitu $n.$
- $a_n = (2n-3) a_{n-5} + a_{n-2} + a_{n-1}$ merupakan relasi rekurens berderajat $5$ dengan koefisien tidak konstan. Hal ini dikarenakan koefisien $a_{n-5}$ yang tidak berupa konstanta, yaitu $2n-3.$
Menyelesaikan Relasi Rekurens Homogen Linear dengan Koefisien Konstan
Pendekatan dasar yang bisa dipakai untuk menyelesaikan relasi rekurens homogen linear adalah dengan mencari solusi berbentuk $a_n = r^n$ dengan $r$ sebagai konstanta. Perhatikan bahwa $a_n = r^n$ merupakan solusi dari relasi rekurens $$a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k}$$jika dan hanya jika
$$r^n=c_1r^{n-1} + c_2r^{n-2} + \cdots + c_kr^{n-k}.$$Ketika kedua ruas pada persamaan di atas dibagi oleh $r^{n-k},$ kemudian ruas kanan dijadikan nol, diperoleh
$$r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots-c_{k-1}r-c_k = 0.$$Akibatnya, barisan $\{a_n\}$ dengan $a_n = r^n$ merupakan solusi dari relasi rekurens jika dan hanya jika $r$ merupakan solusi dari persamaan terakhir. Persamaan terakhir di atas selanjutnya dinamakan persamaan karakteristik (characteristic equation), sedangkan solusinya disebut sebagai akar karakteristik (characteristic root).
Teorema 1
Teorema 2
Teorema 3
$$a_n = \alpha_1r_1^n + \alpha_2r_2^n + \cdots + \alpha_kr_k^n$$ untuk $n \in \{0, 1, 2, \cdots\}$ serta $\alpha_1, \alpha_2, \cdots, \alpha_k$ merupakan konstanta.
Teorema 4
$$\begin{aligned} a_n = &~ (\alpha_{1, 0} + \alpha_{1, 1}n + \cdots + \alpha_{1, m_1-1}n^{m_1-1})r_1^n \\ & + (\alpha_{2, 0} + \alpha_{2, 1}n + \cdots + \alpha_{2, m_2-1}n^{m_2-1})r_2^n + \cdots \\ & + (\alpha_{t, 0} + \alpha_{t, 1}n + \cdots + \alpha_{t, m_t-1}n^{m_t-1})r_t^n \end{aligned}$$untuk $n \in \{0, 1, 2, \cdots\}$ serta $\alpha_{i, j}$ merupakan konstanta dengan $1 \le i \le t$ dan $0 \le j \le m_i-1.$
Artikel ini ditulis berdasarkan beberapa sumber, termasuk sumber berbahasa Inggris. Salah satu sumber yang digunakan adalah buku “Discrete Mathematics and Its Applications” yang ditulis oleh Kenneth H. Rosen. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.
$$\begin{array}{ccc} \hline \text{No.} & \text{Bahasa Indonesia} & \text{Bahasa Inggris} \\ \hline 1. & \text{Relasi Rekurens} & \text{Recurrence Relation} \\ 2. & \text{Homogen} & \text{Homogeneous} \\ 3. & \text{Konstanta} & \text{Constant} \\ 4. & \text{Persamaan Karakteristik} & \text{Characteristic Equation} \\ 5. & \text{Akar Karakteristik} & \text{Characteristic Root} \\ 6. & \text{Barisan Rekursif} & \text{Recursive Sequence} \\ 7. & \text{Menara Hanoi} & \text{Tower of Hanoi} \\ 8. & \text{Barisan Fibonacci} & \text{Fibonacci Sequence} \\ 9. & \text{Barisan Lucas} & \text{Lucas Sequence} \\ 10. & \text{Kondisi Awal} & \text{Initial Condition} \\ 11. & \text{Nilai Awal} & \text{Initial Value} \\ 12. & \text{Untaian Bit} & \text{Bitstring} \\ \hline \end{array}$$
Berikut ini merupakan soal dan pembahasan mengenai relasi rekurens homogen linear dengan koefisien konstan. Semoga dapat dijadikan referensi untuk memantapkan penguasaan materi.
Baca: Soal dan Pembahasan – Relasi Rekurens dengan Fungsi Pembangkit
Quote by Merry Riana
Bagian Pilihan Ganda
Soal Nomor 1
Diketahui relasi rekurens $a_n = 5a_{n-1}$ untuk $n \ge 1.$ Pernyataan berikut yang tidak tepat mengenai relasi rekurens tersebut adalah $\cdots \cdot$
- $a_n$ merupakan relasi rekurens berderajat $1$
- $a_n$ merupakan relasi rekurens dengan koefisien konstan
- $a_n$ merupakan relasi rekurens homogen
- $a_n$ merupakan relasi rekurens linear
- Jika $a_0 = 5,$ maka nilai dari $a_3$ sama dengan $125$
Diketahui $a_n = 5a_{n-1}$ untuk $n \ge 1.$ Relasi rekurens tersebut berderajat $1,$ homogen, linear, dan memiliki koefisien konstan. Namun, untuk $a_0 = 5,$ diperoleh $a_1 = 5(5) = 25,$ $a_2 = 5(25) = 125,$ dan $a_3 = 5(125) = 625.$ Ini menunjukkan bahwa pernyataan pada opsi E tidak tepat.
(Jawaban E)
Soal Nomor 2
Manakah dari relasi rekurens berikut yang termasuk relasi rekurens homogen linear berderajat $3$ dengan koefisien konstan?
A. $a_n = 3a_{n-1} + 4a_{n-2} + 5a_{n-3}.$
B. $a_n = 4a_{n-3} + 8.$
C. $a_n = 8a_{n-2} + 9a_{n-4}.$
D. $a_n = 3a_{n-1} + 7a_{n-2}^2.$
E. $a_n = n^2 \cdot a_{n-1} + 7a_{n-2}-9a_{n-3}.$
Cek opsi A:
Relasi rekurens itu merulakan relasi rekurens homogen linear berderajat $3$ dengan koefisien konstan.
Cek opsi B:
Relasi rekurens itu linear, berderajat $3$, berkoefisien konstan, tetapi tidak homogen karena memuat ekspresi yang tidak memuat suku sebelumnya pada barisan, yaitu $8.$
Cek opsi C:
Relasi rekurens itu linear, homogen, berkoefisien konstan, tetapi berderajat $4,$ bukan $3.$
Cek opsi D:
Relasi rekurens itu homogen dan berkoefisien konstan, tetapi berderajat $2$ dan juga tidak linear karena ekspresi $a_{n-2}$ berpangkat dua.
Cek opsi E:
Relasi rekurens itu linear, homogen, berderajat $3,$ tetapi tidak berkoefisien konstan. Hal ini dapat dilihat dari koefisien $a_{n-1},$ yakni $n^2,$ yang berarti nilainya bergantung pada $n.$
(Jawaban A)
Soal Nomor 3
Diketahui relasi rekurens $a_n = 4a_{n-1}-3a_{n-2}$ untuk $n \ge 2$ dengan nilai awal $a_0 = 5$ dan $a_1 = 8.$ Nilai dari $a_5$ adalah $\cdots \cdot$
A. $44$ D. $368$
B. $125$ E. $612$
C. $366$
Diketahui $a_n = 4a_{n-1}-3a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 5$ dan $a_1 = 8.$
Akan dihitung nilai dari $a_5$ secara rekursif seperti berikut.
$$\begin{aligned} a_2 & = 4a_1-3a_0 = 4(8)-3(5) = 17 \\ a_3 & = 4a_2-3a_1 = 4(17)-3(8) = 44 \\ a_4 & = 4a_3-3a_2 = 4(44)-3(17) = 125 \\ a_5 & = 4a_4-3a_3 = 4(125)-3(44) = 368 \end{aligned}$$Jadi, nilai dari $\boxed{a_5 = 368}.$
(Jawaban D)
Soal Nomor 4
Solusi dari relasi rekurens $a_n = 2a_{n- 1}$ untuk $n \ge 1$ dengan $a_0 = 3$ adalah $\cdots \cdot$
A. $a_n = 2^n$
B. $a_n = 3^n$
C. $a_n = 2 \cdot 3^n$
D. $a_n = 3 \cdot 2^n$
E. $a_n = 2 \cdot 2^n$
Diketahui $a_n = 2a_{n- 1}$ untuk $n \ge 1$ dengan $a_0 = 3.$
Dengan membagi kedua ruas dengan $a_{n-1},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-1}} & = 2 \\ r & = 2 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut.
Ini berarti solusinya berbentuk $a_n = c \cdot r^n = c \cdot 2^n$ untuk suatu konstanta $c.$
Karena $a_0 = 3,$ diperoleh $a_0 = c \cdot 2^0$ yang berarti $3 = c \cdot 1 = c.$ Jadi, nilai $c = 3.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = 3 \cdot 2^n}.$
(Jawaban D)
Soal Nomor 5
Solusi dari relasi rekurens $a_n = a_{n- 1} + 2a_{n- 2}$ untuk $n \ge 2$ dengan $a_0 = 2$ dan $a_1 = 7$ adalah $\cdots \cdot$
A. $a_n = 3 \cdot 2^n$
B. $a_n =3 \cdot 2^n+(-1)^n$
C. $a_n = 3 \cdot 2^n-(-1)^n$
D. $a_n = 2 \cdot 3^n-(-1)^n$
E. $a_n = -3^n+3 \cdot (-1)^n$
Diketahui $a_n = a_{n- 1} + 2a_{n- 2}$ untuk $n \ge 2$ dengan $a_0 = 2$ dan $a_1 = 7.$
Dengan membagi kedua ruas dengan $a_{n-2},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-2}} & = \dfrac{a_{n-1}}{a_{n-2}} + \dfrac{2a_{n-2}}{a_{n-2}} \\ r^2 & = r + 2 \\ r^2-r-2 & = 0 \\ (r-2)(r+1) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = 2$ atau $r_2 = -1.$ Ini berarti solusinya berbentuk $$a_n = c_1 \cdot r_1^n + c_2 \cdot r_2^n = c_1 \cdot 2^n + c_2 \cdot (-1)^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_0 = 2$ dan $a_1 = 7,$ diperoleh
$$\begin{aligned} a_0 & = c_1 \cdot 2^0 + c_2 \cdot (-1)^0 = 2 \\ a_1 & = c_1 \cdot 2^1 + c_2 \cdot (-1)^1 = 7 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} ~~c_1 + c_2 & = 2 \\ 2c_1-c_2 & = 7 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = 3$ dan $c_2 = -1.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = 3 \cdot 2^n-(-1)^n}.$
(Jawaban C)
Soal Nomor 6
Solusi dari relasi rekurens $a_n = 6a_{n- 1}- 9a_{n- 2}$ untuk $n \ge 2$ dengan $a_0 = 1$ dan $a_1 = 6$ adalah $\cdots \cdot$
A. $a_n = 3^n + 3n$
B. $a_n = 3^n + (3)^{n+1}$
C. $a_n = 3^n + n(3)^{n+1}$
D. $a_n = 3^n-n(3)^n$
E. $a_n = 3^n + n(3)^n$
Diketahui $a_n = 6a_{n- 1}-9a_{n- 2}$ untuk $n \ge 2$ dengan $a_0 = 1$ dan $a_1 = 6.$
Dengan membagi kedua ruas dengan $a_{n-2},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-2}} & = \dfrac{6a_{n-1}}{a_{n-2}} -\dfrac{9a_{n-2}}{a_{n-2}} \\ r^2 & = 6r-9 \\ r^2-6r+9 & = 0 \\ (r-3)(r-3) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar kembar $r = 3.$ Ini berarti solusinya berbentuk
$$a_n = c_1 \cdot 3^n + c_2 \cdot n(3)^n.$$Karena $a_0 = 1$ dan $a_1=6,$ diperoleh
$$\begin{aligned} a_0 & = c_1 \cdot 3^0 + c_2 \cdot 0(3)^0 = 1 \\ a_1 & = c_1 \cdot 3^1 + c_2 \cdot 1(3)^1 = 6 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} ~~c_1 & = 1 \\ 3c_1 + 3c_2 & = 6 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = c_2 = 1.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = 3^n + n(3)^n}.$
(Jawaban C)
Soal Nomor 7
Diketahui solusi dari relasi rekurens $a_n = 5a_{n- 1}-6a_{n- 2}$ untuk $n \ge 2$ dengan $a_0 = 1$ dan $a_1 = 0$ adalah $a_n = A \cdot B^n-C \cdot D^n$ untuk suatu $A, B, C , D \in \mathbb{Z}$ dengan $B < D.$ Nilai dari $A+B+C+D = \cdots \cdot$
A. $6$ C. $10$ E. $14$
B. $8$ D. $12$
Diketahui $a_n = 5a_{n- 1}-6a_{n- 2}$ untuk $n \ge 2$ dengan $a_0 = 1$ dan $a_1 = 0.$
Dengan membagi kedua ruas dengan $a_{n-2},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-2}} & = \dfrac{5a_{n-1}}{a_{n-2}} -\dfrac{6a_{n-2}}{a_{n-2}} \\ r^2 & = 5r-6 \\ r^2-5r+6 & = 0 \\ (r-2)(r-3) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = 2$ atau $r_2 = 3.$ Ini berarti solusinya berbentuk $$a_n = c_1 \cdot r_1^n + c_2 \cdot r_2^n = c_1 \cdot 2^n + c_2 \cdot 3^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_0 = 1$ dan $a_1 = 0,$ diperoleh
$$\begin{aligned} a_0 & = c_1 \cdot 2^0 + c_2 \cdot 3^0 = 1 \\ a_1 & = c_1 \cdot 2^1 + c_2 \cdot 3^1 = 0 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} ~~c_1 + ~~c_2 & = 1 \\ 2c_1+3c_2 & = 0 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = 3$ dan $c_2 = -2.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = 3 \cdot 2^n-2 \cdot 3^n}.$
Diketahui dari soal bahwa solusinya berbentuk $a_n = A \cdot B^n-C \cdot D^n$ untuk suatu $A, B, C \in \mathbb{Z}$ dengan $B<D.$ Ini menunjukkan bahwa nilai $A = 3,$ $B = 2,$ $C = 2,$ dan $D = 3$ sehingga nilai dari $$\boxed{A+B+C+D=3+2+2+3=10}.$$(Jawaban C)
Soal Nomor 8
Solusi dari relasi rekurens $a_n = 6a_{n- 1}- 11a_{n- 2} + 6a_{n- 3}$ untuk $n \ge 3$ dengan $a_0 = 2,$ $a_1 = 5,$ dan $a_2 = 15$ adalah $a_n = A-B \cdot C^n +2 \cdot 3^n$ untuk suatu $A, B, C \in \mathbb{Z}.$ Nilai dari $A+B+C=\cdots \cdot$
A. $1$ C. $3$ E. $7$
B. $2$ D. $5$
Diketahui $a_n = 6a_{n- 1}- 11a_{n- 2} + 6a_{n- 3}$ untuk $n \ge 3$ dengan $a_0 = 2,$ $a_1 = 5,$ dan $a_2 = 15.$
Dengan membagi kedua ruas dengan $a_{n-3},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-3}} & = \dfrac{6a_{n-1}}{a_{n-3}} -\dfrac{11a_{n-2}}{a_{n-3}}+\dfrac{6a_{n-3}}{a_{n-3}} \\ r^3 & = 6r^2-11r+6 \\ r^3-6r^2+11r-6 & = 0 \\ (r-1)(r-2)(r-3) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = 1,$ $r_2 = 3,$ dan $r_3 = 3.$ Ini berarti solusinya berbentuk
$$\begin{aligned} a_n & = c_1 \cdot r_1^n + c_2 \cdot r_2^n + c_3 \cdot r_3^n \\ & = c_1 \cdot 1^n + c_2 \cdot 2^n + c_3 \cdot 3^n \\ & = c_1 + c_2(2)^n + c_3(3)^n \end{aligned}$$untuk suatu konstanta $c_1, c_2,$ dan $c_3.$
Karena $a_0 = 2,$ $a_1 = 5,$ dan $a_2 = 15,$ diperoleh
$$\begin{aligned} a_0 & = c_1 + c_2(2)^0 + c_3(3)^0 = 2 \\ a_1 & = c_1 + c_2(2)^1 + c_3(3)^1 = 5 \\ a_2 & = c_1 + c_2(2)^2 + c_3 (3)^2 = 15 \end{aligned}$$sehingga didapat SPLTV berikut.
$$\begin{cases} c_1 + ~~c_2 + ~~c_3 & = 2 \\ c_1 + 2c_2 + 3c_3 & = 5 \\ c_1 + 4c_2 + 9c_3 & = 15 \end{cases}$$Penyelesaian dari SPLTV di atas adalah $c_1 = 1,$ $c_2 = -1,$ dan $c_3 = 2.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = 1-2 \cdot 2^n +2 \cdot 3^n}.$
Diketahui dari soal bahwa solusinya berbentuk $a_n = A-B \cdot C^n +2 \cdot 3^n$ untuk suatu $A, B, C \in \mathbb{Z}.$ Ini menunjukkan bahwa nilai $A = 1,$ $B = 2,$ dan $C = 2$ sehingga nilai dari $\boxed{A+B+C=1+2+2=5}.$
(Jawaban D)
Soal Nomor 9
Solusi dari relasi rekurens $a_n = 2a_{n- 1}+a_{n- 2}-2a_{n- 3}$ untuk $n \ge 3$ dengan $a_0 = 3,$ $a_1 = 6,$ dan $a_2 = 0$ adalah $a_n = \alpha + \beta(2)^n-2(\gamma)^n$ untuk suatu $\alpha, \beta, \gamma \in \mathbb{Z}.$ Nilai dari $\alpha + \beta + \gamma =\cdots \cdot$
A. $3$ C. $6$ E. $8$
B. $4$ D. $7$
Diketahui $a_n = 2a_{n- 1}+a_{n- 2}-2a_{n- 3}$ untuk $n \ge 3$ dengan $a_0 = 3,$ $a_1 = 6,$ dan $a_2 = 0.$
Dengan membagi kedua ruas dengan $a_{n-3},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-3}} & = \dfrac{2a_{n-1}}{a_{n-3}} +\dfrac{a_{n-2}}{a_{n-3}}-\dfrac{2a_{n-3}}{a_{n-3}} \\ r^3 & = 2r^2+r-2 \\ r^3-2r^2-r+2 & = 0 \\ (r-1)(r^2-r-2) & = 0 \\ (r-1)(r-2)(r+1) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = 1,$ $r_2 = 2,$ dan $r_3 = -1.$ Ini berarti solusinya berbentuk
$$\begin{aligned} a_n & = c_1 \cdot r_1^n + c_2 \cdot r_2^n + c_3 \cdot r_3^n \\ & = c_1 \cdot 1^n + c_2 \cdot 2^n + c_3 \cdot (-1)^n \\ & = c_1 + c_2(2)^n + c_3(-1)^n \end{aligned}$$untuk suatu konstanta $c_1, c_2,$ dan $c_3.$
Karena $a_0 = 3,$ $a_1 = 6,$ dan $a_2 = 0,$ diperoleh
$$\begin{aligned} a_0 & = c_1 + c_2(2)^0 + c_3(-1)^0 = 3 \\ a_1 & = c_1 + c_2(2)^1 + c_3(-1)^1 = 6 \\ a_2 & = c_1 + c_2(2)^2 + c_3(-1)^2 = 0 \end{aligned}$$sehingga didapat SPLTV berikut.
$$\begin{cases} c_1 + ~~c_2 + c_3 & = 3 \\ c_1 + 2c_2-c_3 & = 6 \\ c_1 + 4c_2 + c_3 & = 0 \end{cases}$$Penyelesaian dari SPLTV di atas adalah $c_1 = 6,$ $c_2 = -1,$ dan $c_3 = -2.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = 6-2^n-2(-1)^n}.$
Diketahui dari soal bahwa solusinya berbentuk $a_n = \alpha + \beta(2)^n-2(\gamma)^n$ untuk suatu $\alpha, \beta, \gamma \in \mathbb{Z}.$ Ini menunjukkan bahwa nilai $\alpha = 6,$ $\beta = -1,$ dan $\gamma = -1$ sehingga nilai dari $\boxed{\alpha+\beta+\gamma=6+(-1)+(-1) = 4}.$
(Jawaban B)
Soal Nomor 10
Solusi dari relasi rekurens $a_n = 7a_{n- 2}+6a_{n- 3}$ untuk $n \ge 3$ dengan $a_0 = 9,$ $a_1 = 10,$ dan $a_2 = 32$ adalah $a_n = \alpha(3)^n + \beta(-1)^n+\gamma(-2)^n$ untuk suatu $\alpha, \beta, \gamma \in \mathbb{Z}.$ Nilai dari $\alpha + \beta + \gamma =\cdots \cdot$
A. $6$ C. $9$ E. $12$
B. $8$ D. $10$
Diketahui $a_n = 7a_{n- 2}+6a_{n- 3}$ untuk $n \ge 3$ dengan $a_0 = 9,$ $a_1 = 10,$ dan $a_2 = 32.$
Dengan membagi kedua ruas dengan $a_{n-3},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-3}} & = \dfrac{7a_{n-2}}{a_{n-3}}+\dfrac{6a_{n-3}}{a_{n-3}} \\ r^3 & = 7r+6 \\ r^3-7r-6 & = 0 \\ (r-3)(r^2+3r+2) & = 0 \\ (r-3)(r+1)(r+2) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = 3,$ $r_2 = -1,$ dan $r_3 = -2.$ Ini berarti solusinya berbentuk
$$\begin{aligned} a_n & = c_1 \cdot r_1^n + c_2 \cdot r_2^n + c_3 \cdot r_3^n \\ & = c_1(3)^n + c_2(-1)^n + c_3(-2)^n \end{aligned}$$untuk suatu konstanta $c_1, c_2,$ dan $c_3.$
Karena $a_0 = 9,$ $a_1 = 10,$ dan $a_2 = 32,$ diperoleh
$$\begin{aligned} a_0 & = c_1(3)^0 + c_2(-1)^0 + c_3(-2)^0 = 9 \\ a_1 & = c_1(3)^1 + c_2(-1)^1 + c_3(-2)^1 = 10 \\ a_2 & = c_1(3)^2 + c_2(-1)^2 + c_3(-2)^2 = 32 \end{aligned}$$sehingga didapat SPLTV berikut.
$$\begin{cases} ~~c_1 + c_2 + ~~c_3 & = 9 \\ 3c_1-c_2-2c_3 & = 10 \\ 9c_1 + c_2 + 4c_3 & = 32 \end{cases}$$Penyelesaian dari SPLTV di atas adalah $c_1 = 4,$ $c_2 = 8,$ dan $c_3 = -3.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = 4(3)^n+8(-1)^n-3(-2)^n}.$
Diketahui dari soal bahwa solusinya berbentuk $a_n = \alpha(3)^n + \beta(-1)^n+\gamma(-2)^n$ untuk suatu $\alpha, \beta, \gamma \in \mathbb{Z}.$ Ini menunjukkan bahwa nilai $\alpha = 4,$ $\beta = 8,$ dan $\gamma = -3$ sehingga nilai dari $\boxed{\alpha+\beta+\gamma=4+8+(-3) = 9}.$
(Jawaban C)
Soal Nomor 11
Solusi dari relasi rekurens $a_n = 5a_{n-2}-4a_{n-4}$ untuk $n \ge 4$ dengan $a_0 = 3,$ $a_1 = 2,$ $a_2 = 6,$ dan $a_3 = 8$ adalah $a_n = \delta^n + \phi^n + \sigma$ untuk suatu $\delta, \phi, \sigma \in \mathbb{Z}$ dengan $\delta > \phi.$ Nilai dari $\delta-\phi+\sigma =\cdots \cdot$
A. $1$ C. $3$ E. $6$
B. $2$ D. $4$
Diketahui $a_n = 5a_{n-2}-4a_{n-4}$ untuk $n \ge 4$ dengan $a_0 = 3,$ $a_1 = 2,$ $a_2 = 6,$ dan $a_3 = 8.$
Dengan membagi kedua ruas dengan $a_{n-4},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-4}} & = \dfrac{5a_{n-2}}{a_{n-4}}-\dfrac{4a_{n-4}}{a_{n-4}} \\ r^4 & = 5r^2-4 \\ r^4-5r^2+4 & = 0 \\ (r^2-4)(r^2-1) & = 0 \\ (r+2)(r-2)(r+1)(r-1) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = -2,$ $r_2 = 2,$ $r_3 = -1,$ dan $r_4 = 1.$ Ini berarti solusinya berbentuk
$$\begin{aligned} a_n & = c_1 \cdot r_1^n + c_2 \cdot r_2^n + c_3 \cdot r_3^n + c_4 \cdot r_4^n \\ & = c_1(-2)^n + c_2(2)^n + c_3(-1)^n + c_4(1)^n \\ & = c_1(-2)^n + c_2(2)^n + c_3(-1)^n + c_4 \end{aligned}$$untuk suatu konstanta $c_1, c_2,$ $c_3,$ dan $c_4.$
Karena $a_0 = 3,$ $a_1 = 2,$ $a_2 = 6,$ dan $a_3 = 8,$ diperoleh
$$\begin{aligned} a_0 & = c_1(-2)^0 + c_2(2)^0 + c_3(-1)^0 + c_4 = 3 \\ a_1 & = c_1(-2)^1 + c_2(2)^1 + c_3(-1)^1 + c_4 = 2 \\ a_2 & = c_1(-2)^2 + c_2(2)^2 + c_3(-1)^2 + c_4 = 6 \\ a_3 & = c_1(-2)^3 + c_2(2)^3 + c_3(-1)^3 + c_4 = 8 \end{aligned}$$sehingga didapat sistem persamaan linear empat variabel (SPLEV) berikut.
$$\begin{cases} ~~~~~c_1+~~c_2+c_3+c_4 & = 3 \\ -2c_1+2c_2-c_3+c_4 & = 2 \\ ~~~4c_1+4c_2+c_3+c_4 & = 6 \\ -8c_1+8c_2-c_3+c_4 & = 8\end{cases}$$Penyelesaian dari SPLEV di atas adalah $c_1 = 0,$ $c_2 = 1,$ $c_3 = 1,$ dan $c_4 = 1.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $$\boxed{a_n = 0(-2)^n + 1(2)^n + 1(-1)^n + 1(1)^n = 2^n + (-1)^n + 1}.$$Diketahui dari soal bahwa solusinya berbentuk $a_n = \delta^n + \phi^n + \sigma$ untuk suatu $\delta, \phi, \sigma \in \mathbb{Z}$ dengan $\delta > \phi.$ Ini menunjukkan bahwa nilai $\delta= 2,$ $\phi = -1,$ dan $\sigma = 1$ sehingga nilai dari $\boxed{\delta-\phi+\sigma = 2-(-1)+1=4}.$
(Jawaban D)
Soal Nomor 12
Solusi dari relasi rekurens $\dfrac{3}{a_n} = \dfrac{6}{a_{n-1}} + \dfrac{9}{a_{n-2}}$ untuk $n \ge 2$ dengan $a_0 = 5$ dan $a_1 = -5$ adalah $a_n = \dfrac{A}{B(C)^n}$ untuk suatu $A, B, C \in \mathbb{Z}.$ Nilai dari $A+B+C=\cdots \cdot$
A. $5$ C. $7$ E. $10$
B. $6$ D. $8$
Diketahui $\dfrac{3}{a_n} = \dfrac{6}{a_{n-1}} + \dfrac{9}{a_{n-2}}$ untuk $n \ge 2$ dengan $a_0 = 5$ dan $a_1 = -5.$
Perhatikan bahwa relasi rekurens tersebut tidak linear. Namun, kita bisa melakukan permisalan $b_n = \dfrac{3}{a_n}$ sehingga didapat relasi rekurens homogen linear berderajat $2$ dengan koefisien konstan berikut.
$$b_n = 2b_{n-1} + 3b_{n-2}$$Persamaan karakteristik yang berpadanan dengan relasi rekurens baru ini adalah $r^2-2r-3=0$, atau $(r-3)(r+1)=0$ dengan akar $r_1 = 3$ dan $r_2 = -1.$
Ini berarti solusinya berbentuk $$b_n = c_1 \cdot r_1^n + c_2 \cdot r_2^n = c_1 \cdot 3^n + c_2 \cdot (-1)^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_0 = 5$ dan $a_1 = -5,$ diperoleh $b_0 = \dfrac35$ dan $b_1 = -\dfrac35.$ Akibatnya,
$$\begin{aligned} b_0 & = c_1 \cdot 3^0 + c_2 \cdot (-1)^0 = \dfrac35 \\ b_1 & = c_1 \cdot 3^1 + c_2 \cdot (-1)^1 = -\dfrac35 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} ~~c_1 + c_2 & = \dfrac35 \\ 3c_1-c_2 & = -\dfrac35\end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = 0$ dan $c_2 = \dfrac35.$ Disimpulkan bahwa solusi relasi rekurens baru tersebut adalah $b_n = \dfrac35(-1)^n.$
Terakhir, karena $b_n = \dfrac{3}{a_n},$ didapat $a_n = \dfrac{3}{\frac35(-1)^n} = \dfrac{5}{(-1)^n}.$
Perhatikan bahwa dari soal, solusinya berbentuk $a_n = \dfrac{A}{B(C)^n}$ untuk suatu $A, B, C \in \mathbb{Z}.$ Ini menunjukkan bahwa nilai $A = 5,$ $B = 1,$ dan $C = -1$ sehingga nilai dari $\boxed{A+B+C=5+1+(-1)=5}.$
(Jawaban A)
Soal Nomor 13
Suatu barisan bilangan real $a_1, a_2, a_3, \cdots$ memenuhi $a_1 = 1$, $a_2=\dfrac35$, dan $\dfrac{1}{a_n} = \dfrac{2}{a_{n-1}}-\dfrac{1}{a_{n-2}}$ untuk $n \geq 3$. Bilangan $a_{2.020}$ dapat ditulis sebagai $\dfrac{p}{q}$ dengan $p$ dan $q$ bilangan asli relatif prima. Nilai dari $p+q$ adalah $\cdots \cdot$
A. $1.347$ D. $2.021$
B. $1.348$ E. $4.044$
C. $2.020$
Diketahui $\dfrac{1}{a_n} = \dfrac{2}{a_{n-1}}-\dfrac{1}{a_{n-2}}$ untuk $n \geq 3$ dengan $a_1 = 1$ dan $a_2 = \dfrac35.$
Perhatikan bahwa relasi rekurens tersebut tidak linear. Namun, kita bisa melakukan permisalan $b_n = \dfrac{1}{a_n}$ sehingga didapat relasi rekurens homogen linear berderajat $2$ dengan koefisien konstan berikut.
$$b_n = 2b_{n-1}-b_{n-2}$$Persamaan karakteristik yang berpadanan dengan relasi rekurens baru ini adalah $r^2-2r+1=0$, atau $(r-1)(r-1)=0$ dengan akar kembar $r = 1.$
Ini berarti solusinya berbentuk $$\begin{aligned} b_n & = c_1 \cdot r_1^n + c_2n \cdot r_2^n \\ & = c_1 \cdot 1^n + c_2 \cdot n(1)^n \\ & = c_1 + nc_2 \end{aligned}$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_1 = 1$ dan $a_2 = \dfrac35,$ diperoleh $b_1 = 1$ dan $b_1 = \dfrac53.$ Akibatnya,
$$\begin{aligned} b_1 & = c_1 + 1(c_2) = 1 \\ b_2 & = c_1 + 2 (c_2)=\dfrac53 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} c_1 + ~~c_2 & = 1 \\ c_1+2c_2 & = \dfrac53 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = \dfrac13$ dan $c_2 = \dfrac23.$ Disimpulkan bahwa solusi relasi rekurens baru tersebut adalah $b_n = \dfrac13 + \dfrac23n.$
Terakhir, karena $b_n = \dfrac{1}{a_n},$ didapat $$a_n = \dfrac{1}{\dfrac13n + \dfrac23n} = \dfrac{3}{1+2n}.$$Dengan demikian, nilai dari $$a_{2.020} = \dfrac{3}{1+2(2.020)} = \dfrac{1}{1.347}.$$Karena $1$ dan $1.347$ relatif prima, diperoleh $p = 1$ dan $q = 1.347$ sehingga $\boxed{p+q=1.348}.$
(Jawaban A)
Soal Nomor 14
Solusi dari relasi rekurens $a_n = 6a_{n-1}-12a_{n-2}+8a_{n-3}$ dengan $a_0 = 5,$ $a_1 = 4,$ dan $a_2 = 88$ adalah $a_n = \left(A-\dfrac{29}{2}n + \dfrac{23}{2}n^2\right)B^n.$ Nilai dari $A+B=\cdots \cdot$
A. $3$ C. $5$ E. $9$
B. $4$ D. $7$
Diketahui $a_n = 6a_{n-1}-12a_{n-2}+8a_{n-3}$ dengan $a_0 = 5,$ $a_1 = 4,$ dan $a_2 = 88.$
Dengan membagi kedua ruas dengan $a_{n-3},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-3}} & = \dfrac{6a_{n-1}}{a_{n-3}}-\dfrac{12a_{n-2}}{a_{n-3}}+\dfrac{8a_{n-3}}{a_{n-3}} \\ r^3 & = 6r^2-12r+8 \\ r^3-6r^2+12r-8 & = 0 \\ (r-2)(r^2-4r+4) & = 0 \\ (r-2)(r-2)(r-2) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_0 = 2$ bermultiplisitas $3.$ Ini berarti solusinya berbentuk
$$\begin{aligned} a_n & = (c_1 + c_2n + c_3n^2)r_0^n \\ & = (c_1 + c_2n + c_3n^2)2^n. \end{aligned}$$untuk suatu konstanta $c_1, c_2,$ dan $c_3.$
Karena $a_0 = 5,$ $a_1 = 4,$ dan $a_2 = 88,$ diperoleh
$$\begin{aligned} a_0 & = (c_1 + c_2(0) + c_3(0)^2)2^0 = 5 \\ a_1 & = (c_1 + c_2(1) + c_3(1)^2)2^1 = 4 \\ a_2 & = (c_1 + c_2(2) + c_3(2)^2)2^2 = 88 \end{aligned}$$sehingga didapat SPLTV berikut.
$$\begin{cases} c_1 & = 5 \\ c_1 + ~~c_2 + ~~c_3 & = 2 \\ c_1+2c_2+4c_3 & = 22 \end{cases}$$Penyelesaian dari SPLTV di atas adalah $c_1 = 5,$ $c_2 = -\dfrac{29}{2},$ dan $c_3 = \dfrac{23}{2}.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = \left(5-\dfrac{29}{2}n + \dfrac{23}{2}n^2\right)2^n}.$
Diketahui dari soal bahwa solusinya berbentuk $a_n = \left(A-\dfrac{29}{2}n + \dfrac{23}{2}n^2\right)B^n.$ Ini menunjukkan bahwa nilai $A = 5$ dan $B = 2$ sehingga nilai dari $\boxed{A+B=5+2=7}.$
(Jawaban D)
Bagian Uraian
Soal Nomor 1
Periksa apakah $\{a_n\}$ dengan rumus eksplisit berikut merupakan solusi dari relasi rekurens $a_n = -3a_{n-1}+4a_{n-2}$ untuk nilai awal yang diberikan.
- $a_n = 0$ dengan $a_0 = a_1 = 0.$
- $a_n = 1$ dengan $a_0 = a_1 = 1.$
- $a_n = (-4)^n$ dengan $a_0 = 1$ dan $a_1 = -4.$
- $a_n = 2(-4)^n + 3$ dengan $a_0 = 5$ dan $a_1 = -5.$
Jawaban a)
Diketahui $\{a_n\}$ dengan $a_n = 0$ dan $a_n = -3a_{n-1}+4a_{n-2}$ dengan $a_0 = a_1 = 0.$ Karena $a_n = 0,$ diperoleh $a_{n-1} = 0$ dan $a_{n-2} = 0.$
Perhatikan bahwa
$$\begin{aligned} -3a_{n-1}+4a_{n-2} & = -3(0) + 4(0) \\ & = 0 \\ & = a_n. \end{aligned}$$Jadi, disimpulkan bahwa $\{a_n\}$ dengan $a_n = 0$ merupakan solusi dari relasi rekurens $a_n = -3a_{n-1}+4a_{n-2}$ dengan $a_0 = a_1 = 0.$
Jawaban b)
Diketahui $\{a_n\}$ dengan $a_n = 1$ dan $a_n = -3a_{n-1}+4a_{n-2}$ dengan $a_0 = a_1 = 1.$ Karena $a_n = 1,$ diperoleh $a_{n-1} = 1$ dan $a_{n-2} = 1.$
Perhatikan bahwa
$$\begin{aligned} -3a_{n-1}+4a_{n-2} & = -3(1) + 4(1) \\ & = 1 \\ & = a_n. \end{aligned}$$Jadi, disimpulkan bahwa $\{a_n\}$ dengan $a_n = 1$ merupakan solusi dari relasi rekurens $a_n = -3a_{n-1}+4a_{n-2}$ dengan $a_0 = a_1 = 1.$
Jawaban c)
Diketahui $\{a_n\}$ dengan $a_n = (-4)^n$ dan $a_n = -3a_{n-1}+4a_{n-2}$ dengan $a_0 = 1$ dan $a_1 = -4.$ Karena $a_n = (-4)^n,$ diperoleh $a_{n-1} = (-4)^{n-1}$ dan $a_{n-2} = (-4)^{n-2}.$
Perhatikan bahwa
$$\begin{aligned} -3a_{n-1}+4a_{n-2} & = -3(-4)^{n-1} + 4(-4)^{n-2} \\ & = -3(-4)^{n-1}-1(-4)^{n-1} \\ & = -4(-4)^{n-1} \\ & = (-4)^n \\ & = a_n. \end{aligned}$$Jadi, disimpulkan bahwa $\{a_n\}$ dengan $a_n = (-4)^n$ merupakan solusi dari relasi rekurens $a_n = -3a_{n-1}+4a_{n-2}$ dengan $a_0 = 1$ dan $a_1 = -4.$
Jawaban d)
Diketahui $\{a_n\}$ dengan $a_n = 2(-4)^n + 3$ dan $a_n = -3a_{n-1}+4a_{n-2}$ dengan $a_0 = 5$ dan $a_1 = -5.$ Karena $a_n = 2(-4)^n + 3,$ diperoleh $a_{n-1} = 2(-4)^{n-1} + 3$ dan $a_{n-2} = 2(-4)^{n-2} + 3.$
Perhatikan bahwa
$$\begin{aligned} -3a_{n-1}+4a_{n-2} & = -3(2(-4)^{n-1} + 3)+4(2(-4)^{n-2} + 3) \\ & = -6(-4)^{n-1}-9 + 8(-4)^{n-2} + 12 \\ & = -6(-4)^{n-1} + 8(-4)^{n-2} + 3 \\ & = -6(-4)^{n-1}-2(-4)^{n-1} + 3 \\ & = -8(-4)^{n-1} + 3 \\ & = 2(-4)^n + 3 \\ & = a_n. \end{aligned}$$Jadi, disimpulkan bahwa $\{a_n\}$ dengan $a_n = 2(-4)^n + 3$ merupakan solusi dari relasi rekurens $a_n = -3a_{n-1}+4a_{n-2}$ dengan $a_0 = 5$ dan $a_1 = -5.$
Soal Nomor 2
Tentukan solusi dari setiap relasi rekurens berikut.
- $a_n = a_{n-1} + 6a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 3$ dan $a_1 = 6.$
- $a_n = 7a_{n-1}-10a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 2$ dan $a_1 = 1.$
- $a_n = 6a_{n-1}-8a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 4$ dan $a_1 = 10.$
Jawaban a)
Diketahui $a_n = a_{n-1} + 6a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 3$ dan $a_1 = 6.$
Dengan membagi kedua ruas dengan $a_{n-2},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-2}} & = \dfrac{a_{n-1}}{a_{n-2}} + \dfrac{6a_{n-2}}{a_{n-2}} \\ r^2 & = r + 6 \\ r^2-r-6 & = 0 \\ (r-3)(r+2) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = 3$ atau $r_2 = -2.$ Ini berarti solusinya berbentuk $$a_n = c_1 \cdot r_1^n + c_2 \cdot r_2^n = c_1 \cdot 3^n + c_2 \cdot (-2)^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_0 = 3$ dan $a_1 = 6,$ diperoleh
$$\begin{aligned} a_0 & = c_1 \cdot 3^0 + c_2 \cdot (-2)^0 = 3 \\ a_1 & = c_1 \cdot 3^1 + c_2 \cdot (-2)^1 = 6 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} ~~c_1 + ~~c_2 & = 3 \\ 3c_1-2c_2 & = 6 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = \dfrac{12}{5}$ dan $c_2 = \dfrac35.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = \dfrac{12}{5}(3)^n + \dfrac35(-2)^n}.$
Jawaban b)
Diketahui $a_n = 7a_{n-1}-10a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 2$ dan $a_1 = 1.$
Dengan membagi kedua ruas dengan $a_{n-2},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-2}} & = \dfrac{7a_{n-1}}{a_{n-2}} -\dfrac{10a_{n-2}}{a_{n-2}} \\ r^2 & = 7r-10 \\ r^2-7r+10 & = 0 \\ (r-2)(r-5) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = 2$ atau $r_2 = 5.$ Ini berarti solusinya berbentuk $$a_n = c_1 \cdot r_1^n + c_2 \cdot r_2^n = c_1 \cdot 2^n + c_2 \cdot 5^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_0 = 2$ dan $a_1 = 1,$ diperoleh
$$\begin{aligned} a_0 & = c_1 \cdot 2^0 + c_2 \cdot 5^0 = 2 \\ a_1 & = c_1 \cdot 2^1 + c_2 \cdot 5^1 = 1 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} ~~c_1 + ~~c_2 & = 2 \\ 2c_1+5c_2 & = 1 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = 3$ dan $c_2 = -1.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = 3(2)^n-5^n}.$
Jawaban c)
Diketahui $a_n = 6a_{n-1}-8a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 4$ dan $a_1 = 10.$
Dengan membagi kedua ruas dengan $a_{n-2},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-2}} & = \dfrac{6a_{n-1}}{a_{n-2}} -\dfrac{8a_{n-2}}{a_{n-2}} \\ r^2 & = 6r-8 \\ r^2-6r+8 & = 0 \\ (r-2)(r-4) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = 2$ atau $r_2 = 4.$ Ini berarti solusinya berbentuk $$a_n = c_1 \cdot r_1^n + c_2 \cdot r_2^n = c_1 \cdot 2^n + c_2 \cdot 4^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_0 = 4$ dan $a_1 = 10,$ diperoleh
$$\begin{aligned} a_0 & = c_1 \cdot 2^0 + c_2 \cdot 4^0 = 4 \\ a_1 & = c_1 \cdot 2^1 + c_2 \cdot 4^1 = 10 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} ~~c_1 + ~~c_2 & = 4 \\ 2c_1+4c_2 & = 10 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = 3$ dan $c_2 = 1.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $\boxed{a_n = 3(2)^n + 4^n}.$
Soal Nomor 3
Tentukan solusi dari setiap relasi rekurens berikut.
- $a_n = 4a_{n-1}-4a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 6$ dan $a_1 = 8.$
- $a_n = -4a_{n-1}-4a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 0$ dan $a_1 = 1.$
- $a_n = \dfrac{a_{n-2}}{4}$ untuk $n \ge 2$ dengan $a_0 = 1$ dan $a_1 = 0.$
Jawaban a)
Diketahui $a_n = 4a_{n-1}-4a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 6$ dan $a_1 = 8.$
Dengan membagi kedua ruas dengan $a_{n-2},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-2}} & = \dfrac{4a_{n-1}}{a_{n-2}} -\dfrac{4a_{n-2}}{a_{n-2}} \\ r^2 & = 4r-4 \\ r^2-4r+4 & = 0 \\ (r-2)^2 & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar kembar $r = 2.$ Ini berarti solusinya berbentuk $$a_n = c_1 \cdot r_1^n + nc_2 \cdot r_2^n = c_1 \cdot (2)^n + c_2 \cdot n(2)^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_0 = 6$ dan $a_1 = 8,$ diperoleh
$$\begin{aligned} a_0 & = c_1 \cdot 2^0 + c_2 \cdot 0(2)^0 = 6 \\ a_1 & = c_1 \cdot 2^1 + c_2 \cdot 1(2)^1 = 8 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} ~~c_1 & = 6 \\ 2c_1+2c_2 & = 8 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = 6$ dan $c_2 = -2.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $$\boxed{a_n = 6 \cdot 2^n-2n \cdot 2^n = (6-2n)2^n}.$$Jawaban b)
Diketahui $a_n = -4a_{n-1}-4a_{n-2}$ untuk $n \ge 2$ dengan $a_0 = 0$ dan $a_1 = 1.$
Dengan membagi kedua ruas dengan $a_{n-2},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-2}} & = -\dfrac{4a_{n-1}}{a_{n-2}} -\dfrac{4a_{n-2}}{a_{n-2}} \\ r^2 & = -4r-4 \\ r^2+4r+4 & = 0 \\ (r+2)^2 & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar kembar $r = -2.$ Ini berarti solusinya berbentuk $$a_n = c_1 \cdot r_1^n + nc_2 \cdot r_2^n = c_1 \cdot (-2)^n + c_2 \cdot n(-2)^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_0 = 0$ dan $a_1 = 1,$ diperoleh
$$\begin{aligned} a_0 & = c_1 \cdot (-2)^0 + c_2 \cdot 0(-2)^0 = 0 \\ a_1 & = c_1 \cdot (-2)^1 + c_2 \cdot 1(-2)^1 = 1 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} ~~~~~c_1 & = 0 \\ -2c_1-2c_2 & = 1 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = 0$ dan $c_2 = -\dfrac12.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $$\boxed{a_n = 0 \cdot (-2)^n-\dfrac12n \cdot (-2)^n = -\dfrac12n \cdot (-2)^n}.$$Jawaban c)
Diketahui $a_n = \dfrac{a_{n-2}}{4}$ untuk $n \ge 2$ dengan $a_0 = 1$ dan $a_1 = 0.$
Dengan membagi kedua ruas dengan $a_{n-2},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-2}} & = \dfrac{a_{n-2}}{4a_{n-2}} \\ r^2 & = \dfrac14 \\ r^2-\dfrac14 & = 0 \\ \left(r+\dfrac12\right)\left(r-\dfrac12\right) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = -\dfrac12$ dan $r_2 = \dfrac12.$ Ini berarti solusinya berbentuk $$a_n = c_1 \cdot r_1^n + nc_2 \cdot r_2^n = c_1 \cdot \left(-\dfrac12\right)^n + c_2 \cdot \left(\dfrac12\right)^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_0 = 1$ dan $a_1 = 0,$ diperoleh
$$\begin{aligned} a_0 & = c_1 \cdot \left(-\dfrac12\right)^0 + c_2 \cdot \left(\dfrac12\right)^0 = 1 \\ a_1 & = c_1 \cdot \left(-\dfrac12\right)^1 + c_2 \cdot \left(\dfrac12\right)^1 = 0 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} ~~~~~~c_1+~~~~c_2 & = 1 \\ -\dfrac12c_1+\dfrac12c_2 & = 0 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = c_2 = \dfrac12.$ Disimpulkan bahwa solusi relasi rekurens tersebut adalah $$\boxed{a_n = \dfrac12 \cdot \left(-\dfrac12\right)^n+\dfrac12n \cdot \left(\dfrac12\right)^n = -\left(-\dfrac12\right)^{n+1} + \left(\dfrac12\right)^{n+1}}.$$
Soal Nomor 4
Tentukan rumus eksplisit dari barisan Fibonacci.
Catatan: Barisan Fibonacci memenuhi relasi rekurens $f_n = f_{n-1} + f_{n-2}$ dengan nilai awal $f_0 = 0$ dan $f_1 = 1.$
Perhatikan bahwa barisan Fibonacci memenuhi relasi rekurens $f_n = f_{n-1} + f_{n-2}$ dengan nilai awal $f_0 = 0$ dan $f_1 = 1.$ Persamaan karakteristik dari relasi rekurens tersebut adalah $r^2-r-1=0$ dengan akar $r_1 = \dfrac{1+\sqrt{5}}{2}$ dan $r_2 = \dfrac{1-\sqrt5}{2}.$ Ini berarti, barisan Fibonacci dapat dinyatakan secara eksplisit sebagai
$$f_n = c_1 \left(\dfrac{1+\sqrt5}{2}\right)^n + c_2 \left(\dfrac{1-\sqrt5}{2}\right)^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena diketahui nilai awal $f_0=0$ dan $f_1=1,$ diperoleh SPLDV berikut.
$$\begin{cases} f_0 & = c_1 + c_2 = 0 \\ f_1 & = c_1 \left(\dfrac{1+\sqrt5}{2}\right) + c_2 \left(\dfrac{1-\sqrt5}{2}\right) = 1 \end{cases}$$SPLDV di atas memiliki penyelesaian $c_1 = \dfrac{1}{\sqrt5}$ dan $c_2 = -\dfrac{1}{\sqrt5}.$
Akibatnya, rumus eksplisit barisan Fibonacci dinyatakan sebagai berikut.
$$\boxed{f_n = \dfrac{1}{\sqrt5} \left(\dfrac{1+\sqrt5}{2}\right)^n-\dfrac{1}{\sqrt5} \left(\dfrac{1-\sqrt5}{2}\right)^n}.$$
Soal Nomor 5
Tentukan rumus eksplisit dari barisan Lucas.
Catatan: Barisan Lucas memenuhi relasi rekurens $f_n = f_{n-1} + f_{n-2}$ dengan nilai awal $f_0 = 2$ dan $f_1 = 1.$
Perhatikan bahwa barisan Lucas memenuhi relasi rekurens $f_n = f_{n-1} + f_{n-2}$ dengan nilai awal $f_0 = 2$ dan $f_1 = 1.$ Persamaan karakteristik dari relasi rekurens tersebut adalah $r^2-r-1=0$ dengan akar $r_1 = \dfrac{1+\sqrt{5}}{2}$ dan $r_2 = \dfrac{1-\sqrt5}{2}.$ Ini berarti, barisan Lucas dapat dinyatakan secara eksplisit sebagai
$$f_n = c_1 \left(\dfrac{1+\sqrt5}{2}\right)^n + c_2 \left(\dfrac{1-\sqrt5}{2}\right)^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena diketahui nilai awal $f_0=2$ dan $f_1=1,$ diperoleh SPLDV berikut.
$$\begin{cases} f_0 & = c_1 + c_2 = 2 \\ f_1 & = c_1 \left(\dfrac{1+\sqrt5}{2}\right) + c_2 \left(\dfrac{1-\sqrt5}{2}\right) = 1 \end{cases}$$SPLDV di atas memiliki penyelesaian $c_1 = c_2 = 1.$
Akibatnya, rumus eksplisit barisan Lucas dinyatakan sebagai berikut.
$$\boxed{f_n = \left(\dfrac{1+\sqrt5}{2}\right)^n+\left(\dfrac{1-\sqrt5}{2}\right)^n}.$$
Soal Nomor 6
Tentukan bentuk umum dari solusi relasi rekurens homogen linear jika persamaan karakteristiknya memiliki akar berikut.
- $1, 1, 1, 1,$ $-2, -2, -2,$ $3, 3, -4.$
- $-1, -1, -1, 2,$ $2, 5, 5, 7, 7.$
Jawaban a)
Dengan menggunakan Teorema 4, bentuk umum dari solusi relasi rekurens homogen linear jika persamaan karakteristiknya memiliki akar $1, -2, 3,$ dan $-4$ dengan multiplisitas berturut-turut $4, 3, 2,$ dan $1$ adalah sebagai berikut.
$$\begin{aligned} a_n = & (\alpha_{1, 0} + \alpha_{1, 1}n + \alpha_{1, 2}n^2 + \alpha_{1, 3}n^3)(1)^n + (\alpha_{2, 0} + \alpha_{2, 1}n + \alpha_{2, 2}n^2)(-2)^n \\ & + (\alpha_{3, 0} + \alpha_{3, 1}n)(3)^n + (\alpha_{4, 0})(-4)^n \end{aligned}$$untuk suatu konstanta $a_{i, j}$ dengan $1 \le i \le 4$ dan $0 \le j \le 3.$
Jawaban b)
Dengan menggunakan Teorema 4, bentuk umum dari solusi relasi rekurens homogen linear jika persamaan karakteristiknya memiliki akar $-1, 2, 5,$ dan $7$ dengan multiplisitas berturut-turut $3, 2, 2,$ dan $2$ adalah sebagai berikut.
$$\begin{aligned} a_n = & (\alpha_{1, 0} + \alpha_{1, 1}n + \alpha_{1, 2}n^2)(-1)^n + (\alpha_{2, 0} + \alpha_{2, 1}n)(2)^n + (\alpha_{3, 0} + \alpha_{3, 1}n)(5)^n \\ & + (\alpha_{4, 0} + \alpha_{4, 1})(7)^n \end{aligned}$$untuk suatu konstanta $a_{i, j}$ dengan $1 \le i \le 4$ dan $0 \le j \le 2.$
Soal Nomor 7
Selesaikan sistem relasi rekurens berikut.
$$\begin{cases} a_n & = 3a_{n-1} + 2b_{n-1} \\ b_n & = a_{n-1} + 2b_{n-1} \end{cases}$$dengan $a_0 = 1$ dan $b_0 = 2.$
Diketahui
$$\begin{cases} a_n & = 3a_{n-1} + 2b_{n-1} && (\cdots 1) \\ b_n & = a_{n-1} + 2b_{n-1} && (\cdots 2) \end{cases}$$dengan $a_0 = 1$ dan $b_0 = 2.$ Dari relasi rekurens $(2),$ diperoleh
$$\begin{aligned} a_{n-1} & = b_n-2b_{n-1} \\ a_n & = b_{n+1}-2b_n. \end{aligned}$$Substitusikan pada relasi rekurens $(1)$ menghasilkan
$$\begin{aligned} b_{n+1}-2b_n & = 3(b_n-2b_{n-1}) + 2b_{n-1} \\ b_{n+1} & = 5b_n-4b_{n-1} \\ b_n & = 5b_{n-1}-4b_{n-2}. \end{aligned}$$Kita peroleh suatu relasi rekurens homogen linear dengan koefisien konstan. Persamaan karakteristiknya adalah $r^2-5r+4=0$ sehingga akar karakteristiknya adalah $r_1 = 1$ dan $r_2 = 4.$ Dengan demikian, solusi relasi rekurens tersebut dinyatakan oleh $b_n = C_1 + C_2(4)^n.$
Untuk $a_0 = 1$ dan $b_0 = 2,$ diperoleh $$b_1 = a_0 + 2b_0 = 1 + 2(2) = 5.$$Dengan demikian, didapat SPLDV berikut.
$$\begin{aligned} b_0 = C_1 + C_2 & = 2 \\ b_1 = C_1 + 4C_2 & = 5 \end{aligned}$$Solusi SPLDV di atas adalah $C_1 = C_2 = 1.$ Jadi, solusi relasi rekurens $b_n = 5b_{n-1}-4b_{n-2}$ adalah $b_n = 1 + 4^n.$
Akibatnya,
$$\begin{aligned} a_n & = b_{n+1}-2b_n \\ & = (1 + 4^{n+1})-2(1+4^n) \\ & = 4^{n+1}-4^n-1. \end{aligned}$$Dengan demikian, penyelesaian dari sistem relasi rekurens tersebut adalah $a_n = 4^{n+1}-4^n-1$ dan $b_n = 1 + 4^n.$
Soal Nomor 8
Sepasang kelinci (jantan dan betina) muda dilepas di suatu pulau terpencil. Asumsikan mereka dapat bertahan hidup di sana, tidak dapat mati, dan tidak ada predator. Sepasang kelinci tidak akan memiliki anak sampai mereka berumur dua bulan. Sesudah berumur dua bulan, sepasang kelinci akan mempunyai sepasang anak (jantan dan betina) setiap bulannya. Nyatakan banyaknya pasangan kelinci di pulau itu pada bulan ke-$n.$
Misalkan $f_n$ menyatakan banyaknya pasangan kelinci pada bulan ke-$n.$ Pada bulan pertama, $f_1 = 1.$ Pada bulan kedua, $f_2 = 1$ karena pasangan kelinci tersebut masih belum bisa bereproduksi.
Banyaknya pasangan kelinci pada bulan ke-$n$ sama dengan banyaknya pasangan kelinci pada bulan sebelumnya, yaitu $f_{n-1},$ ditambah dengan banyaknya kelahiran pasangan kelinci yang baru. Banyaknya kelahiran ini sama dengan banyaknya pasangan kelinci pada dua bulan sebelumnya, yaitu $f_{n-2},$ karena mereka semua sudah dapat melahirkan anak.
Jadi, disimpulkan bahwa banyaknya pasangan kelinci di pulau itu setelah $n$ bulan adalah $\boxed{f_n = f_{n-1} + f_{n-2}}$ dengan nilai awal $f(1) = f(2) = 1.$
Soal Nomor 9
Tentukan relasi rekurens beserta nilai awalnya yang merepresentasikan banyaknya untaian bit dengan panjang $n$ yang tidak memuat bit $0$ secara berurutan.
Misalkan $a_n$ menyatakan banyaknya untaian bit dengan panjang $n$ yang tidak memuat bit $0$ secara berurutan. Untuk $n = 1,$ diperoleh $a_1 = 2$ karena hanya ada satu untaian bit yang tidak memuat bit $0$ secara berurutan, yaitu $0$ dan $1.$ Untuk $n = 2,$ diperoleh $a_2 = 3$ karena hanya ada satu untaian bit yang tidak memuat bit $0$ secara berurutan, yaitu $11, 10,$ dan $01.$
Ada dua kasus yang dapat ditinjau untuk membangun untaian bit dengan panjang $n$ sehingga tidak memuat bit $0$ secara berurutan.
- Pertama, tinjau untaian bit dengan panjang $n-1.$ Tambahkan bit $1$ di ujung untaian sehingga panjangnya sekarang $n.$ Ini berarti, banyaknya untaian bit yang diinginkan pada kasus ini sama dengan nilai dari $a_{n-1}.$
- Kedua, tinjau untaian bit dengan panjang $n-2.$ Tambahkan bit $10$ di ujung untaian sehingga panjangnya sekarang $n.$ Ini berarti, banyaknya untaian bit yang diinginkan pada kasus ini sama dengan nilai dari $a_{n-2}.$
Jadi, disimpulkan bahwa $a_n = a_{n-1} + a_{n-2}$ untuk $n \ge 3$ dengan nilai awal $a_1 = 2$ dan $a_2 = 3.$
Soal Nomor 10
Pada suatu sistem komputer, untaian digit desimal (string of decimal digits) dianggap sebagai kata sandi yang valid jika untaian desimal tersebut memuat sejumlah genap digit $0.$ Sebagai contoh, 188123788 dan 000012482958 merupakan kata sandi yang valid. Namun, 120992329010 tidak valid karena digit $0$ muncul sebanyak tiga kali.
Tentukan relasi rekurens beserta nilai awalnya yang merepresentasikan banyaknya untaian desimal dengan panjang $n$ yang memuat sejumlah genap digit $0.$
Misalkan $a_n$ menyatakan banyaknya untaian digit desimal dengan panjang $n$ yang memuat sejumlah genap digit $0.$ Untuk $n=1,$ diperoleh $a_1 = 9$ karena ada sembilan untaian digit desimal yang digit $0$-nya muncul sebanyak $0$ kali ($0$ adalah bilangan genap) seperti yang tersaji sebagai anggota dalam himpunan berikut.
$$\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$$Ada dua kasus yang dapat ditinjau untuk membangun untaian digit desimal dengan panjang $n$ yang memuat sejumlah genap digit $0.$
- Pertama, tinjau untaian digit desimal dengan panjang $n-1$ yang memuat sejumlah genap digit $0.$ Kemudian, tambahkan satu digit yang bukan $0$ pada ujung untaian. Kita dapat menambahkan digit $1, 2, 3, \cdots, 9$ yang berarti ada $9$ cara melakukannya. Jadi, untuk kasus ini, untaian digit desimal dengan panjang $n$ yang memuat sebanyak genap $0$ ada sebanyak $9a_{n-1}.$
- Kedua, tinjau untaian digit desimal dengan panjang $n-1$ yang memuat sejumlah ganjil digit $0.$ Kemudian, tambahkan satu digit $0$ pada ujung untaian agar digit $0$ menjadi genap. Perhatikan bahwa banyak untaian digit desimal dengan panjang $n-1$ yang memuat sejumlah ganjil digit $0$ $(b_{n-1})$ sama dengan banyak untaian digit desimal dengan panjang $n-1,$ yaitu $10^{n-1}$ karena masing-masing posisi dapat diisi oleh 10 pilihan digit, dikurangi dengan banyak untaian digit desimal dengan panjang $n-1$ yang memuat sebanyak genap $0,$ ditulis
$$b_{n-1} = 10^{n-1}-a_{n-1}.$$Jadi, untuk kasus ini, untaian digit desimal dengan panjang $n$ yang memuat sebanyak genap $0$ ada sebanyak $10^{n-1}-a_{n-1}.$
Dari kasus pertama dan kedua, totalnya adalah $$\boxed{a_n = (9a_{n-1}) + (10^{n-1}-a_{n-1}) = 8a_{n-1} + 10^{n-1}}$$untuk $n \ge 2$ dengan nilai awal $a_1 = 9.$
Soal Nomor 11
Diberikan untaian bit dengan panjang $n.$
- Tentukan relasi rekurens yang menyatakan banyaknya untaian bit dengan panjang $n$ yang memuat untaian $01.$
- Tentukan nilai awalnya.
- Berapa banyak untaian bit dengan panjang tujuh yang memuat untaian $01$?
Jawaban a)
Misalkan $a_n$ menyatakan banyaknya untaian bit dengan panjang $n$ yang memuat untaian $01.$
Tinjau kasus untuk membangun untaian bit dengan panjang $n$ yang memuat untaian $01$ berikut.
- Untaian bit berbentuk $\square~\square \cdots \square~\square~0$ yang memuat untaian $01$ ada sebanyak $a_{n-1}.$
- Untaian bit berbentuk $\square~\square \cdots \square~01$ yang memuat untaian $01$ ada sebanyak $2^{n-2}.$
- Untaian bit berbentuk $\square~\square \cdots \square~011$ yang memuat untaian $01$ ada sebanyak $2^{n-3}.$
- $\cdots \cdots$
- Untaian bit berbentuk $011\cdots1$ yang memuat untaian $01$ ada sebanyak $2^{n-n} = 1.$
- Untaian bit berbentuk $111\cdots1$ yang memuat untaian $01$ ada sebanyak $0.$
Dari sini, diperoleh
$$\begin{aligned} a_n & = a_{n-1} + 2^{n-2} + 2^{n-3} + \cdots + 1\\ & = a_{n-1} + 2^{n-1}-1. \end{aligned}$$Jadi, relasi rekurens yang menyatakan banyaknya untaian bit dengan panjang $n$ yang memuat untaian $01$ adalah $\boxed{a_n = a_{n-1} + 2^{n-1}-1}$ untuk $n \ge 2.$
Jawaban b)
Untuk $n = 1,$ diperoleh $a_1 = 0$ karena tidak ada untaian bit dengan panjang $1$ yang memuat untaian $01.$ Jadi, nilai awal dari relasi rekurens yang dibangun adalah $a_1 = 0.$
Jawaban c)
Diketahui $a_n = a_{n-1} + 2^{n-1}-1$ dengan nilai awal $a_1 = 0.$ Akan dicari nilai dari $a_7$ secara iteratif.
$$\begin{aligned} a_2 & = a_1 + 2^1-1 = 0 + 2-1 = 1 \\ a_3 & = a_2 + 2^2-1 = 1 + 4-1 = 4 \\ a_4 & = a_3 + 2^3-1 = 4 + 8-1 = 11 \\ a_5 & = a_4 + 2^4-1 = 11 + 16-1 = 26 \\ a_6 & = a_5 + 2^5-1 = 26 + 32-1 = 57 \\ a_7 & = a_6 + 2^6-1 = 57 + 64-1 = 120 \end{aligned}$$Jadi, banyak untaian bit dengan panjang tujuh yang memuat untaian $01$ adalah $\boxed{120}.$
Soal Nomor 12
Misalkan terdapat $n$ anak tangga.
- Tentukan relasi rekurens yang menyatakan banyaknya cara menaiki $n$ anak tangga oleh seseorang jika orang tersebut dapat menaiki $1, 2,$ atau $3$ anak tangga sekaligus.
- Tentukan nilai awalnya.
- Berapa banyak cara yang dapat dilakukan orang tersebut untuk menaiki $8$ anak tangga?
Jawaban a)
Misalkan $a_n$ menyatakan banyaknya cara menaiki $n$ anak tangga oleh seseorang jika orang tersebut dapat menaiki $1, 2,$ atau $3$ anak tangga sekaligus.
Tinjau kasus untuk menaiki $n$ anak tangga berikut.
- Naik $1$ anak tangga terlebih dahulu. Berikutnya, kita tinggal perlu menaiki $n-1$ anak tangga lagi. Banyak cara melakukannya adalah $a_{n-1}.$
- Naik $2$ anak tangga terlebih dahulu. Berikutnya, kita tinggal perlu menaiki $n-2$ anak tangga lagi. Banyak cara melakukannya adalah $a_{n-2}.$
- Naik $3$ anak tangga terlebih dahulu. Berikutnya, kita tinggal perlu menaiki $n-3$ anak tangga lagi. Banyak cara melakukannya adalah $a_{n-3}.$
Dari sini, diperoleh
$$a_n = a_{n-1} + a_{n-2} + a_{n-3}.$$Jadi, relasi rekurens yang menyatakan banyaknya cara menaiki $n$ anak tangga oleh seseorang jika orang tersebut dapat menaiki $1, 2,$ atau $3$ anak tangga sekaligus adalah $\boxed{a_n = a_{n-1} + a_{n-2} + a_{n-3}}$ untuk $n \ge 3.$
Jawaban b)
Untuk $n = 1,$ diperoleh $a_1 = 1$ karena hanya ada $1$ cara untuk menaiki $1$ anak tangga. Untuk $n = 2,$ diperoleh $a_2 = 2$ karena ada $2$ cara untuk menaiki $2$ anak tangga, yaitu naik $1-1$ dan $2.$ Untuk $n = 3,$ diperoleh $a_3 = 4$ karena ada $4$ cara untuk menaiki $3$ anak tangga, yaitu naik $1-1-1,$ $1-2,$ $2-1,$ dan $3.$ Jadi, nilai awal dari relasi rekurens yang dibangun adalah $a_1= 1,$ $a_2 = 2,$ dan $a_3 = 4.$
Jawaban c)
Diketahui $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ dengan nilai awal $a_1 = 1,$ $a_2 = 2,$ dan $a_3 = 4.$ Akan dicari nilai dari $a_8$ secara iteratif.
$$\begin{aligned} a_3 & = a_2 + a_1 + a_0 = 1 + 2 + 4 = 7 \\ a_4 & = a_3 + a_2 + a_1 = 2 + 4 + 7 = 13 \\ a_5 & = a_4 + a_3 + a_2 = 13 + 7 + 4 = 24 \\ a_6 & = a_5 + a_4 + a_3 = 24 + 13 + 7 = 44 \\ a_7 & = a_6 + a_5 + a_4 = 44 + 24 + 13 = 81 \\ a_8 & = a_7 + a_6 + a_5 = 81 + 44 + 24 = 149 \end{aligned}$$Jadi, banyak cara yang dapat dilakukan orang tersebut untuk menaiki $8$ anak tangga adalah $\boxed{149}.$
Soal Nomor 13
Papan persegi panjang berukuran $n \times 2$ akan ditutup dengan menggunakan papan-papan kecil berukuran $1 \times 2$ (dapat dirotasi menjadi $2 \times 1$) dan/atau $2 \times 2.$
- Tentukan $a_n,$ yaitu banyaknya cara untuk menutup papan berukuran $n \times 2$ dengan menggunakan dua jenis papan kecil tersebut.
- Berikan formula eksplisit dari $a_n.$
Jawaban a)
Misalkan $a_n$ menyatakan banyaknya cara untuk menutup papan berukuran $n \times 2$ dengan menggunakan papan-papan kecil berukuran $1 \times 2$ (dapat dirotasi menjadi $2 \times 1$) dan/atau $2 \times 2.$ Dari sini, kita tahu bahwa $a_1 = 1$ dan $a_2 = 3.$
Ada tiga kasus yang dapat ditinjau untuk menutup papan tersebut.
- Pertama, tutup papan berukuran $(n-1) \times 2$ dengan $a_{n-1}$ cara. Kemudian, tutup sisa bagian papan yang lain dengan menggunakan satu potong papan berukuran $1 \times 2.$ Jadi, ada $a_{n-1}$ cara yang dapat dilakukan dalam kasus ini.
- Kedua, tutup papan berukuran $(n-2) \times 2$ dengan $a_{n-2}$ cara. Kemudian, tutup sisa bagian papan yang lain dengan menggunakan satu potong papan berukuran $2 \times 2.$ Jadi, ada $a_{n-2}$ cara yang dapat dilakukan dalam kasus ini.
- Terakhir, tutup papan berukuran $(n-2) \times 2$ dengan $a_{n-2}$ cara. Kali ini, tutup sisa bagian papan yang lain dengan menggunakan dua potong papan berukuran $2 \times 1$ (hasil rotasi). Jadi, ada $a_{n-2}$ cara yang dapat dilakukan dalam kasus ini.
Perhatikan bahwa tiga kasus tersebut saling lepas.
Ini berarti, total banyaknya cara untuk menutup papan adalah $$a_n = a_{n-1} + a_{n-2} + a_{n-2} = a_{n-1} + 2a_{n-2}$$untuk $n \ge 3$ dengan $a_1 = 1$ dan $a_2 = 3.$
Jawaban b)
Diketahui relasi rekurens $a_n = a_{n-1} + 2a_{n-2}$ untuk $n \ge 3$ dengan $a_1 = 1$ dan $a_2 = 3.$
Dengan membagi kedua ruas dengan $a_{n-2},$ diperoleh
$$\begin{aligned} \dfrac{a_n}{a_{n-2}} & = \dfrac{a_{n-1}}{a_{n-2}} + \dfrac{2a_{n-2}}{a_{n-2}} \\ r^2 & = r + 2 \\ r^2-r-2 & = 0 \\ (r-2)(r+1) & = 0 \end{aligned}$$yang merupakan persamaan karakteristik dari relasi rekurens tersebut dengan akar $r_1 = 2$ atau $r_2 = -1.$ Ini berarti solusinya berbentuk $$a_n = c_1 \cdot r_1^n + c_2 \cdot r_2^n = c_1 \cdot 2^n + c_2 \cdot (-1)^n$$untuk suatu konstanta $c_1$ dan $c_2.$
Karena $a_1 = 1$ dan $a_2 = 3,$ diperoleh
$$\begin{aligned} a_1 & = c_1 \cdot 2^1 + c_2 \cdot (-1)^1 = 1 \\ a_1 & = c_1 \cdot 2^2 + c_2 \cdot (-1)^2 = 3 \end{aligned}$$sehingga didapat SPLDV berikut.
$$\begin{cases} 2c_1-c_2 & = 1 \\ 4c_1+c_2 & = 3 \end{cases}$$Penyelesaian dari SPLDV di atas adalah $c_1 = \dfrac23$ dan $c_2 = \dfrac13.$ Disimpulkan bahwa formula eksplisit (solusi dari relasi rekurens) dari $a_n$ adalah $\boxed{a_n = \dfrac23(2)^n + \dfrac13(-1)^n}$