Subbagian Pratinjau Bagian
Selidiki!
Anda memiliki banyak persegi berukuran
\(1\times 1\) dan domino berukuran
\(1\times 2\text{.}\) Anda ingin menyusunnya untuk membentuk lajur berukuran
\(1 \times 15\text{.}\) Ada berapa cara untuk melakukannya?
Bagaimana jika persegi-persegi tersebut tersedia dalam tiga warna berbeda dan domino-domino tersebut tersedia dalam empat warna berbeda? Mengapa pertanyaan kedua ini lebih mudah daripada pertanyaan pertama?
Petunjuk.
Mulailah dengan menyusun relasi rekurensi. Bagaimana hubungan berbagai lajur
\(1\times 3\) dan lajur
\(1 \times 4\) dengan lajur
\(1 \times 5\text{?}\)
Dalam
Subbab 4.3 kita melihat bahwa jika barisan selisih pada suatu tingkat bersifat konstan, barisan awal memiliki rumus tertutup berbentuk polinomial. Adakah barisan yang selisihnya tidak pernah konstan? Seperti apakah rumus tertutupnya?
Perhatikan barisan Fibonacci:
\begin{equation*}
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\text{.}
\end{equation*}
Jika kita memperhatikan selisih pertamanya, kita memperoleh barisan berikut:
\begin{equation*}
1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots\text{,}
\end{equation*}
yang merupakan barisan Fibonacci itu sendiri. Hal ini tidak mengherankan karena barisan Fibonacci didefinisikan oleh relasi rekurensi \(F_n = F_{n-1} + F_{n-2}\text{.}\) Relasi tersebut tepatnya mengatakan bahwa untuk memperoleh suku berikutnya dalam barisan, kita mengambil suku saat ini lalu menambahkan... salah satu suku dalam barisan!
Tentu saja, jika kita mengambil selisih berikutnya, kita kembali memperoleh barisan yang sama, dan demikian seterusnya. Jadi, tidak ada selisih ke-
\(n\) yang akan menjadi konstan.
Barisan lain yang memiliki perilaku ini adalah pangkat-pangkat 2:
\begin{equation*}
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, \ldots
\end{equation*}
yang barisan selisihnya adalah
\begin{equation*}
1, 2, 4, 8, 16, 32, 64, 128, 256, \ldots\text{.}
\end{equation*}
Kita juga dapat melihatnya dari relasi rekurensi karena
\begin{equation*}
a_n = 2a_{n-1} = a_{n-1} + a_{n-1}\text{.}
\end{equation*}
Laju pertumbuhan barisan ini—dan pada umumnya setiap barisan geometri—sebanding dengan barisan itu sendiri.
Jika pernah mempelajari kalkulus, Anda mungkin ingat bahwa fungsi yang laju perubahannya (turunannya, dalam konteks kalkulus) sebanding dengan fungsi itu sendiri adalah fungsi eksponensial. Demikian pula di sini, barisan geometri yang memiliki rumus tertutup eksponensial memiliki laju perubahan yang sebanding dengan barisan itu sendiri.
Dalam bagian ini, kita akan menyelidiki barisan yang berubah dengan laju sebanding dengan barisan itu sendiri dan melihat bahwa semuanya memiliki rumus tertutup eksponensial atau variasinya.
Lembar Kerja Kegiatan Pratinjau
1.
Subbagian Menjumlahkan Barisan Geometri: Kalikan, Geser, dan Kurangkan
Misalkan sebuah mesin permen mengeluarkan permen menurut barisan geometri: mula-mula 1 butir, kemudian 2 butir, lalu 4 butir, 8 butir, dan seterusnya. Berapa jumlah seluruh permen yang Anda terima setelah menggunakan mesin itu 10 kali?
Kita dapat menyusun barisan jumlah parsial \(1, 1+2, 1+2+4, 1+2+4+8, \ldots\text{,}\) yang menghasilkan
\begin{equation*}
1, 3, 7, 15, 31, 63, \ldots
\end{equation*}
Barisan ini bukan barisan geometri, tetapi hampir menyerupainya. Bahkan, jika kita menambahkan 1 pada setiap suku, kita memperoleh barisan yang jelas tampak seperti barisan geometri \(2, 4, 8, 16, 32, 64,\ldots\text{.}\) Jadi, kita dapat menduga bahwa rumus tertutup barisan jumlah tersebut adalah \(2^{n+1} - 1\text{,}\) dengan suku pertamanya berindeks 0. Jika dugaan ini benar, jawaban untuk pertanyaan tentang permen adalah \(2^{10} - 1 = 1023\text{.}\)
Pengamatan yang lebih menarik adalah bahwa barisan jumlah parsial suatu barisan geometri kembali memiliki bentuk yang hampir geometris. Mari kita pelajari cara menghitung jumlah barisan geometri secara umum.
Kita tidak dapat begitu saja membalikkan urutan dan menjumlahkannya seperti ketika menjumlahkan barisan aritmetika. Dapatkah Anda melihat alasannya? Kita memperoleh suku yang sama berulang kali karena terdapat selisih konstan. Jadi, ketika kita menambahkan selisih itu dalam satu arah, kita mengurangkan selisih tersebut dalam arah sebaliknya sehingga tersisa jumlah yang konstan. Untuk penjumlahan geometri, kita menggunakan teknik yang berbeda.
Contoh 4.4.1.
Berapakah
\(3 + 6 + 12 + 24 + \cdots + 12288\text{?}\)
Penyelesaian.
Kalikan setiap suku dengan 2, yaitu rasio tetapnya. Kita memperoleh
\(2S = 6 + 12 + 24 + \cdots + 24576\text{.}\) Sekarang kurangkan:
\(2S - S = -3 + 24576 = 24573\text{.}\) Karena
\(2S - S = S\text{,}\) kita telah memperoleh jawabannya.
Agar proses dalam contoh di atas terlihat lebih jelas, kita dapat menuliskannya dengan cara berikut:
| \(S=\) |
\(3 \, +\) |
\(6 + 12 + 24 + \cdots + 12288\) |
|
| \(- \qquad 2S=\) |
|
\(6 + 12 + 24 + \cdots + 12288\) |
\(+ 24576\) |
| \(-S = \) |
\(3 \, +\) |
\(0 + 0 + 0 + \cdots + 0 \) |
\(-24576\) |
Kemudian, bagi kedua ruas dengan
\(-1\) dan kita memperoleh hasil yang sama untuk
\(S\text{.}\) Gagasannya adalah bahwa dengan mengalikan jumlah tersebut dengan rasio tetap, setiap suku berubah menjadi suku berikutnya. Kita menggeser penjumlahan tersebut sehingga hampir semua suku saling menghapus ketika dikurangkan, dan hanya menyisakan suku pertama serta suku terakhir yang baru.
Contoh 4.4.2.
Temukan rumus tertutup untuk
\(S(n) = 2 + 10 + 50 + \cdots + 2\cdot 5^n\text{.}\)
Penyelesaian.
Rasio persekutuannya adalah 5. Jadi, kita memiliki
| \(S\) |
\(= 2 + 10 + 50 + \cdots + 2\cdot 5^n\) |
| \(- \qquad 5S\) |
\(= ~~~~~~10 + 50 + \cdots + 2\cdot 5^n + 2\cdot5^{n+1}\) |
| \(-4S\) |
\(= 2 - 2\cdot5^{n+1}\) |
Dengan demikian,
\(S = \dfrac{2-2\cdot 5^{n+1}}{-4}\text{.}\)
Meskipun teknik ini mungkin tampak baru, Anda barangkali pernah menggunakannya.
Contoh 4.4.3.
Nyatakan
\(0.464646\ldots\) sebagai pecahan.
Penyelesaian.
Misalkan
\(N = 0.46464646\ldots\text{.}\) Perhatikan
\(0.01N\text{.}\) Kita memperoleh:
| \(N =\) |
\(0.4646464\ldots\) |
| \(- \qquad 0.01N =\) |
\(0.00464646\ldots\) |
| \(0.99N =\) |
\(0.46\) |
Jadi,
\(N = \frac{46}{99}\text{.}\) Apa yang baru saja kita lakukan? Kita memandang desimal berulang
\(0.464646\ldots\) sebagai jumlah barisan geometri
\(0.46, 0.0046, 0.000046, \ldots\) dengan rasio tetap
\(0.01\text{.}\) Perbedaan utamanya adalah bahwa sekarang kita menghitung jumlah geometri
tak hingga, sehingga tidak ada suku “terakhir” tambahan yang perlu diperhitungkan. Sebenarnya, hasil ini diperoleh dengan mengambil limit, seperti yang dilakukan dalam kalkulus ketika kita menghitung jumlah geometri
tak hingga.
Sebagai rangkuman, kini kita dapat menemukan rumus tertutup untuk barisan
\(a_n\) yang laju pertumbuhannya berupa fungsi eksponensial:
\(a_n - a_{n-1} = b_n\text{,}\) dengan
\(b_n\) merupakan barisan geometri (yakni fungsi eksponensial). Rumus tertutup seperti apa yang kita peroleh? Ternyata berupa fungsi eksponensial
lain!
Subbagian Teknik Akar Karakteristik
Misalkan kita ingin menyelesaikan relasi rekurensi yang dinyatakan sebagai kombinasi dua suku sebelumnya, misalnya \(a_n = a_{n-1} + 6a_{n-2}\text{.}\) Dengan kata lain, kita ingin menemukan fungsi dari \(n\) yang memenuhi \(a_n - a_{n-1} - 6a_{n-2} = 0\text{.}\) Perhatikan bagaimana kita membangun barisan ini secara iteratif.
\begin{align*}
a_2 \amp = a_1 + 6a_0 \\
a_3 \amp = a_2 + 6a_1 = a_1 + 6a_0 + 6a_1\\
a_4 \amp = a_3 + 6a_2 = a_1 + 6a_0 + 6a_1 + 6^2a_0 +6a_1
\end{align*}
Mari berhenti di sini dan mengakui bahwa perhitungannya mulai menjadi sangat rumit. Namun, kita melihat bahwa pada setiap langkah, salah satu hal yang dilakukan adalah mengalikan hasil iterasi sebelumnya dengan 6. Jadi, rumus tertutup kita akan memuat \(6\) yang dikalikan berulang kali. Oleh karena itu, masuk akal untuk menduga bahwa penyelesaiannya memuat bagian yang berbentuk geometris. Mungkin penyelesaiannya berbentuk \(r^n\) untuk suatu konstanta \(r\text{.}\)
Hal yang menguntungkan adalah kita mengetahui cara memeriksa apakah suatu rumus benar-benar merupakan penyelesaian relasi rekurensi: substitusikan rumus itu. Apa yang terjadi jika kita menyubstitusikan \(r^n\) ke dalam relasi rekurensi di atas? Kita memperoleh
\begin{equation*}
r^n - r^{n-1} - 6r^{n-2} = 0\text{.}
\end{equation*}
Sekarang selesaikan persamaan untuk \(r\text{:}\)
\begin{equation*}
r^{n-2}(r^2 - r - 6) = 0\text{,}
\end{equation*}
Dengan memfaktorkan, kita memperoleh \(r = -2\) atau \(r = 3\) (atau \(r = 0\text{,}\) meskipun nilai ini tidak membantu kita). Hasil ini menunjukkan bahwa \(a_n = (-2)^n\) merupakan penyelesaian relasi rekurensi tersebut, demikian pula \(a_n = 3^n\text{.}\) Manakah yang benar? Keduanya benar selama kita belum menentukan syarat awal. Perhatikan bahwa kita juga dapat menggunakan \(a_n = (-2)^n + 3^n\text{.}\) Atau \(a_n = 7(-2)^n + 4\cdot 3^n\text{.}\) Bahkan, untuk sembarang \(a\) dan \(b\text{,}\) \(a_n = a(-2)^n + b 3^n\) merupakan penyelesaian (cobalah menyubstitusikannya ke dalam relasi rekurensi). Untuk menemukan nilai \(a\) dan \(b\text{,}\) gunakan syarat awal.
Pengamatan ini mengarahkan kita pada teknik yang lebih umum untuk menyelesaikan relasi rekurensi. Perhatikan bahwa kita selalu dapat mengeluarkan faktor
\(r^{n-2}\) seperti di atas. Jadi, kita sebenarnya hanya perlu memperhatikan bagian lainnya. Bagian lain ini kita sebut
persamaan karakteristik dari relasi rekurensi tersebut. Kita ingin menemukan akar-akar persamaan karakteristik, yang disebut
akar karakteristik.
Akar Karakteristik.
Untuk relasi rekurensi \(a_n + \alpha a_{n-1} + \beta a_{n-2} = 0\text{,}\) polinomial karakteristiknya adalah
\begin{equation*}
x^2 + \alpha x + \beta
\end{equation*}
yang menghasilkan persamaan karakteristik:
\begin{equation*}
x^2 + \alpha x + \beta = 0\text{.}
\end{equation*}
Jika \(r_1\) dan \(r_2\) adalah dua akar berbeda dari polinomial karakteristik (yakni, penyelesaian persamaan karakteristik), penyelesaian relasi rekurensi tersebut adalah
\begin{equation*}
a_n = ar_1^n + br_2^n\text{,}
\end{equation*}
dengan \(a\) dan \(b\) merupakan konstanta yang ditentukan oleh syarat awal.
Contoh 4.4.4.
Selesaikan relasi rekurensi
\(a_n = 7a_{n-1} - 10 a_{n-2}\) dengan
\(a_0 = 2\) dan
\(a_1 = 3\text{.}\)
Penyelesaian.
Tuliskan kembali relasi rekurensinya sebagai \(a_n - 7a_{n-1} + 10a_{n-2} = 0\text{.}\) Sekarang susun persamaan karakteristiknya:
\begin{equation*}
x^2 - 7x + 10 = 0
\end{equation*}
lalu selesaikan untuk \(x\text{:}\)
\begin{equation*}
(x - 2) (x - 5) = 0\text{,}
\end{equation*}
sehingga \(x = 2\) dan \(x = 5\) merupakan akar karakteristik. Oleh karena itu, kita mengetahui bahwa penyelesaian relasi rekurensi tersebut berbentuk
\begin{equation*}
a_n = a 2^n + b 5^n\text{.}
\end{equation*}
Untuk menemukan \(a\) dan \(b\text{,}\) substitusikan \(n =0\) dan \(n = 1\) sehingga diperoleh sistem dua persamaan dengan dua peubah yang belum diketahui:
\begin{align*}
2 \amp = a 2^0 + b 5^0 = a + b\\
3 \amp = a 2^1 + b 5^1 = 2a + 5b\text{.}
\end{align*}
Penyelesaian sistem ini memberikan \(a = \frac{7}{3}\) dan \(b = -\frac{1}{3}\text{,}\) sehingga penyelesaian relasi rekurensinya adalah
\begin{equation*}
a_n = \frac{7}{3}2^n - \frac{1}{3} 5^n\text{.}
\end{equation*}
Barangkali relasi rekurensi yang paling terkenal adalah
\(F_n = F_{n-1} + F_{n-2}\text{,}\) yang bersama syarat awal
\(F_0 = 0\) dan
\(F_1= 1\) mendefinisikan barisan Fibonacci. Namun, perhatikan bahwa relasi ini tepat merupakan jenis relasi rekurensi yang dapat diselesaikan dengan teknik akar karakteristik. Ketika kita menerapkannya, satu-satunya perbedaan adalah bahwa persamaan karakteristiknya tidak dapat difaktorkan, sehingga kita harus menggunakan rumus kuadrat untuk menemukan akar karakteristik. Hasilnya adalah bilangan irasional ketiga yang paling terkenal, yaitu
\(\varphi\text{,}\) sang
rasio emas.
Sebelum meninggalkan teknik akar karakteristik, kita perlu memikirkan apa yang mungkin terjadi ketika menyelesaikan persamaan karakteristik. Dalam contoh di atas, polinomial karakteristik memiliki dua akar berbeda. Akar-akar tersebut dapat berupa bilangan bulat atau mungkin bilangan irasional (yang harus ditemukan dengan rumus kuadrat). Dalam kasus seperti ini, kita mengetahui bentuk penyelesaian relasi rekurensinya.
Namun, polinomial karakteristik mungkin hanya memiliki satu akar. Hal ini dapat terjadi jika polinomial karakteristik dapat difaktorkan menjadi
\((x - r)^2\text{.}\) Dalam kasus ini,
\(r^n\) tetap merupakan penyelesaian relasi rekurensi, tetapi kita tidak dapat menemukan penyelesaian untuk semua syarat awal dengan bentuk umum
\(a_n = ar_1^n + br_2^n\text{,}\) sebab kita tidak dapat membedakan
\(r_1^n\) dari
\(r_2^n\text{.}\) Untungnya, ada jalan keluar:
Teknik Akar Karakteristik untuk Akar Berulang.
Misalkan relasi rekurensi \(a_n = \alpha a_{n-1} + \beta a_{n-2}\) memiliki polinomial karakteristik dengan hanya satu akar \(r\text{.}\) Maka, penyelesaian relasi rekurensi tersebut adalah
\begin{equation*}
a_n = ar^n + bnr^n
\end{equation*}
dengan \(a\) dan \(b\) merupakan konstanta yang ditentukan oleh syarat awal.
Perhatikan faktor tambahan
\(n\) dalam
\(bnr^n\text{.}\) Faktor ini memungkinkan kita menentukan konstanta
\(a\) dan
\(b\) berdasarkan syarat awal.
Contoh 4.4.5.
Selesaikan relasi rekurensi
\(a_n = 6a_{n-1} - 9a_{n-2}\) dengan syarat awal
\(a_0 = 1\) dan
\(a_1 = 4\text{.}\)
Penyelesaian.
Polinomial karakteristiknya adalah \(x^2 - 6x + 9\text{.}\) Kita menyelesaikan persamaan karakteristik
\begin{equation*}
x^2 - 6x + 9 = 0
\end{equation*}
dengan memfaktorkan:
\begin{equation*}
(x - 3)^2 = 0,
\end{equation*}
sehingga \(x =3\) merupakan satu-satunya akar karakteristik. Oleh karena itu, kita mengetahui bahwa penyelesaian relasi rekurensinya berbentuk
\begin{equation*}
a_n = a 3^n + bn3^n
\end{equation*}
untuk suatu konstanta \(a\) dan \(b\text{.}\) Sekarang gunakan syarat awal:
\begin{align*}
a_0 = 1 \amp = a 3^0 + b\cdot 0 \cdot 3^0 = a\\
a_1 = 4 \amp = a\cdot 3 + b\cdot 1 \cdot3 = 3a + 3b\text{.}
\end{align*}
Karena \(a = 1\text{,}\) kita memperoleh \(b = \frac{1}{3}\text{.}\) Oleh karena itu, penyelesaian relasi rekurensinya adalah
\begin{equation*}
a_n = 3^n + \frac{1}{3}n3^n\text{.}
\end{equation*}
Meskipun kita tidak akan membahas contoh yang lebih rumit daripada contoh-contoh ini, teknik akar karakteristik dapat diterapkan pada relasi rekurensi yang jauh lebih rumit. Sebagai contoh,
\(a_n = 2a_{n-1} + a_{n-2} - 3a_{n-3}\) memiliki polinomial karakteristik
\(x^3 - 2 x^2 - x + 3\text{.}\) Jika kita mengetahui cara memfaktorkan polinomial berderajat 3 (atau lebih) semacam itu, kita dapat dengan mudah menemukan akar karakteristik dan kemudian menyelesaikan relasi rekurensinya (jika terdapat 3 akar berbeda, penyelesaiannya berbentuk
\(a_n = ar_1^n + br_2^n + cr_3^n\)). Akar karakteristik juga mungkin berupa bilangan kompleks.
Namun, teknik akar karakteristik hanya berguna untuk menyelesaikan relasi rekurensi dalam bentuk tertentu:
\(a_n\) dinyatakan sebagai kombinasi linear sejumlah suku sebelumnya. Relasi semacam ini disebut
relasi rekurensi homogen linear dengan koefisien konstan. Istilah “homogen” mengacu pada kenyataan bahwa relasi rekurensi tidak memuat suku tambahan selain kelipatan suku-suku
\(a_j\text{.}\) Sebagai contoh,
\(a_n = 2a_{n-1} + 1\) bersifat
tak homogen karena terdapat konstanta tambahan 1. Ada metode umum untuk menyelesaikan relasi semacam ini, tetapi kita tidak akan membahasnya di sini selain melalui metode teleskopik atau iterasi yang dijelaskan di atas.
