Barisan
Salah satu struktur diskrit yang banyak dibahas adalah barisan (
sequence), yaitu suatu daftar terurut. Sebagai contoh, daftar terurut $1,3,5,7,9, \cdots$ merupakan barisan.
Barisan adalah fungsi dengan domain integer tak negatif $\{0,1,2,3,\cdots\}$. Nilai fungsi ini di $n$ dituliskan dengan $a_n$. Selanjutnya $a_n$ dinamakan suku ke $n$. Barisan dengan suku-suku $a_n$ dituliskan $\{a_n\}$.
Pada seluruh pembahasan tentang barisan, notasi $\cdots$ berarti suku-suku $a_n$ diteruskan tanpa batas. Barisan pada definisi di atas juga dinamakan barisan tak hingga. Barisan $\{a_n\}$ dapat dituliskan sukunya dengan
\[ a_1,a_2, a_3, \cdots.\]
Suku $a_n$ kadang-kadang dinyatakan dalam bentuk rumus.
Contoh
Perhatikan barisan $\{a_n\}$ dengan suku ke $n$ dinyatakan dengan rumus
\[ a_n=\frac{1}{n}.\]
Di dalam barisan ini, $a_1=\frac{1}{1}=1, a_2=\frac{1}{2}, a_3=\frac{1}{3}$ dan seterusnya.
Jadi jika dituliskan suku-sukunya maka barisan ini adalah
\[ 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \cdots \]
Barisan geometrik adalah barisan yang berbentuk
\[ a,ar,ar^2,ar^3, \cdots, ar^n, \cdots\]
dengan $a$ dan $r$ bilangan real. Bilangan $a$ dinamakan suku awal dan $r$ dinamakan rasio.
Contoh
Barisan $\{a_n\}$ dengan $a_n=\frac{3}{2^n}$ merupakan barisan geometrik dengan suku awal $a=3$ dan rasio $r=\frac{1}{2}$. Hal ini dapat dijelaskan dengan menuliskan kembali barisan ini menjadi
\[ a_n=\frac{3}{2^n}=3\cdot \left(\frac{1}{2}\right)^n.\]
Suku-suku barisan ini adalah
\[ a_0=3, \quad a_1=\frac{3}{2},\quad a_2= \frac{3}{4}, \quad a_3=\frac{3}{8}, \quad a_4=\frac{3}{16}, \quad \cdots .\]
Contoh
Barisan $\{b_n\}$ dengan $b_n=(-1)^n$ dapat dituliskan
\[ b_n=1\cdot (-1)^n,\]
sehingga merupakan barisan geometrik dengan suku awal $a=1$ dan rasio $r=-1$. Barisan ini dapat dituliskan dengan
\[ 1,-1,1,-1,1,-1, \cdots.\]
Contoh
Barisan $\{c_n\}$ dengan $c_n=2\cdot 3^n$ merupakan barisan geometri dengan suku awal $a=2$ dan rasio $r=3$. Barisan ini dapat dituliskan dengan
\[ 2, 6, 18, 54, 162, \cdots.\]
Barisan aritmetika adalah barisan berbentuk
\[ a, a+d, a+2d, a+3d, \cdots, a+nd, \cdots\]
dengan $a$ dan $d$ bilangan real. Bilangan $a$ dinamakan suku awal dan $d$ dinamakan selisih atau beda.
Contoh
Barisan $\{s_n\}$ dengan $s_n=3+2n$ merupakan barisan aritmetik dengan suku awal $3$ dan beda $2$. Barisan ini dapat dituliskan
\[ 3, 5, 7, 9, 11, 13, \cdots.\]
Contoh
Barisan $\{t_n\}$ dengan $t_n=5-n$ merupakan barisan aritmetik dengan suku awal $5$ dan beda $-1$, sebab $t_n=5-n=5+(-1)n$. Suku-suku barisan ini adalah
\[ 5, 4,3,2,1,0,-1,-2,-3,\cdots.\]
Barisan yang sering digunakan dalam ilmu komputer adalah barisan berbentuk
\[ a_1,a_2,a_3, \cdots, a_n,\]
yakni barisan yang hanya memiliki berhingga suku. Barisan demikian dinamakan
string. String juga dituliskan dengan
\[ a_1a_2a_3\cdots a_n.\]
Panjang string menyatakan banyaknya suku di dalam string. String yang tidak memiliki suku dinamakan
string kosong dituliskan dengan $\lambda$.
String kosong memiliki panjang nol.
Di atas telah dicontohkan bahwa barisan dapat dituliskan dengan mendaftarkan beberapa suku awal dan dilanjutkan dengan bentuk umum suku ke $n$. Suku ke $n$ suatu barisan bisa tergantung pada suku-suku sebelumnya.
Relasi rekurensi
Relasi rekurensi barisan $\{a_n\}$ adalah suatu persamaan yang menyatakan $a_n$ di dalam satu atau lebih suku dari suku-suku sebelumnya.
Suatu barisan dinamakan penyelesaian suatu relasi rekurensi jika suku-suku barisan tersebut memenuhi relasi rekurensi.
Contoh
Perhatikan barisan
\[ 1, 4, 7, 10, 13, \cdots.\]
Jika pada barisan ini $a_0=1$, maka suku ke $n$ barisan ini dapat dituliskan sebagai persamaan suku sebelumnya, yaitu
\[ a_n=a_{n-1}+3,\qquad n=1,2,3,\cdots.\]
Oleh karena itu $a_n=a_{n-1}+3$ merupakan relasi rekurensi barisan tersebut.
Contoh
Diketahui barisan $\{a_n\}$ memenuhi relasi rekurensi $a_n=a_{n-1}+5$ untuk $n=1,2,3,\cdots$. Jika $a_0=3$, carilah nilai $a_1,a_2$ dan $a_3$.
Penyelesaian
Dari relasi rekurensi $a_n=a_{n-1}+5$ diperoleh
\[
\begin{array}{ll}
a_1&=a_0+5=3+5=8\\
a_2&=a_1+5=8+5=13\\
a_3&=a_2+5=13+5=18.
\end{array}
\]
Contoh barisan dengan relasi rekurensi lebih dari satu suku adalah barisan berikut.
Barisan Fibonacci $\{a_n\}$ adalah barisan dengan suku-suku
\[
\begin{array}{lll}
a_0&=&0, \\
a_1&=&1 \\
a_n&=&a_{n-2}+a_{n-1}, \quad n=2,3,4,\cdots.
\end{array}
\]
Contoh
Carilah suku $a_n$ dengan $n=2,3,4,5$ pada barisan Fibonacci.
Penyelesaian
Dari relasi rekurensi barisan Fibonacci diperoleh
\[
\begin{array}{ll}
a_2&=a_0+a_1=0+1=1\\
a_3&=a_1+a_2=1+1=2\\
a_4&=a_2+a_3=1+2=3\\
a_5&=a_3+a_4=2+3=5.
\end{array}
\]
Suatu rumus dikatakan penyelesaian relasi rekurensi jika rumus tersebut merupakan bentuk umum suku ke $n$ barisan. Rumus ini dinamakan rumus tertutup.
Contoh
Diberikan relasi rekurensi $a_n=2a_{n-1}-a_{n-2}$ dengan $n=2,3,4,\cdots$. Tunjukkan bahwa barisan $\{a_n\}$ dengan $a_n=3n$ merupakan penyelesaian relasi rekurensi tersebut.
Penyelesaian
Karena $a_n=3n$, maka $a_{n-1}=3(n-1)$ dan $a_{n-2}=3(n-2)$. Oleh karena itu
\[
\begin{array}{lll}
2a_{n-1}-a_{n-2}&=2\cdot 3(n-1)-3(n-2)\\
&=(6n-6)-(3n-6)=3n\\
&=a_n,
\end{array}
\]
yang berarti $a_n=3n$ merupakan penyelesaian relasi rekurensi tersebut.
Contoh
Tunjukan bahwa barisan $\{a_n\}$ dengan $a_n=2(-4)^n+3$ merupakan penyelesaian relasi rekurensi $a_n=-3a_{n-1}+4a_{n-2}$.
Penyelesaian
Dari rumus $a_n=2(-4)^n+3$, diperoleh $a_{n-1}=2(-4)^{n-1}+3$ dan $a_{n-2}=2(-4)^{n-2}+3$.
Oleh karena itu
\[
\begin{array}{lll}
- 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\\
&=&(-4)^{n-2}[-6(-4)+8]+3\\
&=&(-4)^{n-2}\cdot 32+3\\
&=&(-4)^{n-2}\cdot (-4)^2 \cdot 2+3\\
&=&2(-4)^n+3\\
&=&=a_n.
\end{array}
\]
Dalam banyak hal barisan hanya dituliskan beberapa suku awalnya.
Untuk suku berikutnya perlu dicari rumus umumnya.
Contoh
Carilah rumus untuk barisan berikut:
- $1,\frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \cdots$.
- $-1, 2, 5, 8, 11, \cdots$.
- $1, -\frac{1}{2}, \frac{1}{4}, -\frac{1}{8}, \frac{1}{16}, \cdots$.
Penyelesaian
Suatu barisan bisa memiliki lebih dari satu rumus umum suku ke $n$.
Rumus umum baisan di atas misalnya adalah
- $a_n=\frac{1}{n}$ demgan $n=1,2,3,\cdots$.
- $a_n=3n-1$ dengan $n=0,1,2,3,\cdots$.
- $a_n=(-\frac{1}{2})^n$ dengan $n=0,1,2,3,\cdots$.
Deret
Notasi $\sum$ adalah notasi penjumlahan, dibaca "sigma" dengan definisi
\[ \sum_{i=k}^{n} a_i = a_k+a_{k+1}+a_{k+2}+\cdots + a_n.\]
Contoh
- $\displaystyle \sum_{i=0}^{8} a_i=a_0+a_1+a_2+a_4+a_5+a_6+a_7+a_8$.
- $\displaystyle \sum_{i=1}^5 i^2=1^2+2^2+3^2+4^2+5^2=55$.
- $\displaystyle \sum_{i=2}^7(-1)^i=(-1)^2+(-1)^3+(-1)^4+(-1)^5+(-1)^6+(-1)^7=0$.
Jika $a$ dan $r$ bilangan real dengan $r\neq 0$, maka
\[ \sum_{i=0}^n ar^i=
\begin{cases}
\displaystyle \frac{ar^{n+1}-a}{r-1}, &\text{ jika } r\neq 1\\
(n+1)a, &\text{ jika } r=1.
\end{cases}
\]
Bukti
Dituliskan $S_n=\sum_{i=0}^n ar^i$ dengan $r \neq 1$. Jadi
\[
\begin{array}{lll}
S_n=\sum_{i=0}^n ar^i&=a+ar+ar^2+ar^3+\cdots+ar^n\\
rS_n=\sum_{i=0}^n ar^{i+1}&= ar+ar^2+ar^3+\cdots+ar^n+ar^{n+1}
\end{array}
\]
Oleh karena itu
\[ rS_n-S_n=ar^{n+1}-a\]
atau dituliskan kembali menjadi
\[ (r-1)S_n=ar^{n+1}-a.\]
Selanjutnya dengan membagi kedua ruas dengan $r-1$ diperoleh $S_n=\frac{ar^{n+1}-a}{r-1}$.
Untuk $r=1$,
\begin{eqnarray*}
S_n&=\sum_{i=0}^n ar^i=\sum_{i=0}^n a \cdot1^i=\sum_{i=0}^n a =\underbrace{a+a+\cdots+a}_{\mbox{(n+1) suku}}=(n+1)a.
\end{eqnarray*}
Contoh
Carilah jumlah $\sum_{i=0}^{9} 3\cdot 2^i$.
Penyelesaian
Pada jumlahan tersebut $a=3$, $r=2$ dan $n=9$. Oleh karena itu
\[ \sum_{i=0}^9 3\cdot 2^i =\frac{3\cdot 2^{9+1}-3}{2-1}=3\cdot 2^{10}-3=3\cdot 1024-3=3069. \]
Contoh
Carilah jumlah $\sum_{i=0}^{10} \frac{5}{2^i}$
Penyelesaian
Perhatikan bahwa $\sum_{i=0}^{10} \frac{5}{2^i}=\sum_{i=0}^{10} 5\cdot (\frac{1}{2})^i$, yakni
$a=5$, $r=\frac{1}{2}$ dan $n=10$.
Oleh karena itu
\[ \sum_{i=0}^{10} \frac{5}{2^i} =\frac{5\cdot (\frac{1}{2})^{11}-5}{\frac{1}{2}-1}=
\frac{5\cdot (\frac{1}{2})^{11}-5}{-\frac{1}{2}}=-5\cdot (\frac{1}{2})^{10}+10=-\frac{5}{1024}+10=\frac{10235}{1024}.
\]
Jumlahan kadang-kadang juga dalam bentuk $\sum_{i=k}^n\sum_{j=l}^m a_ib_j$ yang dinamakan jumlahan ganda (double summation).
Contoh
Carilah $\sum_{i=1}^3\sum_{j=1}^4 ij$.
Penyelesaian
Untuk setiap $i=1,2,3$ dicari terlebih dahulu $\sum_{j=1}^4 ij$. Jadi
Untuk $i=1$
\[ \sum_{j=1}^4 ij= \sum_{j=1}^4 j =1+2+3+4=10,\]
Untuk $i=2$
\[ \sum_{j=1}^4 ij= \sum_{j=1}^4 2 j =2\cdot 1+ 2\cdot 2+ 2\cdot 3+2\cdot 4=20,\]
Untuk $i=3$,
\[ \sum_{j=1}^4 ij= \sum_{j=1}^4 3 j =3\cdot 1+ 3\cdot 2+ 3\cdot 3+3\cdot 4=30,\]
Dengan demikian
\[ \sum_{i=1}^3\sum_{j=1}^4 ij=10+20+30=60.\]