Barisan Bilangan

Dasar-Dasar Barisan dan Notasi Sigma dan Produk¶

Dalam analisis matematika, barisan merupakan struktur fundamental yang merepresentasikan urutan objek matematis yang disusun berdasarkan pola tertentu. Dalam konteks matematika, pemahaman yang mendalam mengenai sifat-sifat barisan beserta teknik manipulasi notasinya merupakan prasyarat multak sebelum mempelajari teknik penyederhanaan deret, induksi matematika, dan relasi rekursif.

Mencari Pola Barisan¶

Menemukan pola adalah langkah pertama dalam analisis barisan yang tidak diketahui formulanya. Dalam level olimpiade, pola barisan jarang berupa aritmatika atau geometri sederhana. Beberapa pendekatan utama meliputi:

1. Pola Polinomial (Metode Selisih Bertingkat)
   Jika selisih antara suku-suku yang berurutan pada barisan membentuk suatu konstant pada tingkat ke-$k$, maka suku umum $a_n$ dapat diekspresikan sebagai polinomial berderajat $k$. Dalam kurikulum sekolah standar, pencarian koefisien polinomial ini umumnya menggunakan eliminasi pada sistem persamaan linier yang sangat memakan waktu. Untuk mempercepat analisis di tingkat olimpiade, kita menggunakan pendekatan kombinatorik yang diformalkan melalu Metode Beda Hingga Newton

   Dengan menggunakan Teorema Newton ini, pencarian rumus suku ke-$n$ tidak lagi memerlukan pemecahan sistem persamaan linier yang rumit. Kita hanya perlu menyusun barisan selisih bertingkatnya, mengambil angka pertama dari setiap tingkatan tersebut, dan mensubstitusikannya langsung sebagai pengali pada suku-suku koefisien binomial.

2. Pola Eksponensial / Rasio Geometri
   Ditandai dengan rasio pembagian antara suku yang berdekatan bernilai konstan atau membentuk pola pangkat. Poal umumnya melibatkan bentuk eksponensial $C^n$.

3. Pola Alternasi (Tanda Berganti)
   Barisan yang tandanya atau sifatnya berubah secara periodik (misal positif-negatif, atau genap-ganjil). Biasanya melibatkan komponen $(-1)^n$ atau pemisahan barisan menjadi sub-barisan untuk indeks genap $(a_{2k})$ dan ganjil $(a_{2k-1})$.

4. Pola Faktorial
   Muncul apabila pertumbuhan nilai suku membesar dengan sangat drastis melebihi fungsi eksponensial, biasanya melibatkan bentuk perkalian menurun $n!=n\times (n-1)\times \cdot \times 1$

Notasi Sigma¶

Untuk merepresentasikan penjumlahan beruntun dari suku-suku suatu barisan secara ringkas, matematika menggunakan abjad Yunani kapital Sigma $(\Sigma)$. Penggunaan notasi ini multak diperlukan untuk menyederhanakan ekspresi aljabar yang panjang dan menghindari penulisan titik-titik $\cdots$ yang ambil secara analitik.

Simbol $i$ disebut sebagai indeks penjumlahan (variabel \textit{dummy}), $n$ adalah batas bawah, dan $n$ adalah batas atas. Indeks $i$ dapat diganti dengan huruf lain seperti $j, k$, atau $t$ tanpa mengubah makna matematisnya.

Sifat-Sifat Operasional Notasi Sigma Misalkan $a_i$ dna $b_i$ adalah barisan bilangan real, dan $c$ adalah suatu konstan real. maka berlaku sifat-sifat operasional dasar berikut

1. Sifat penjumlahan konstanta\

   $$\sum_{i=1}^{n}c= n\cdot c$$

   (7)

2. Sifat homogenitas\

   $$\sum_{i=m}^{n} n\cdot a_i = c\sum_{i=m}^{n} a_i$$

   (8)

3. Sifat aditif\

   $$\sum_{i=m}^{n} (a_i \pm b_i) = \sum_{i=m}^{n} a_i + \sum_{i=m}^{n}b_i$$

   (9)

4. Sifat pemecahan batas\

   $$\sum_{i=m}^{n}a_i = \sum_{i=m}^{p}a_i + \sum_{i=p+1}^{n}a_i$$

   (10)

5. Sifat pergeseran indeks\

   $$\sum_{i=m}^{n} a_i = \sum_{i=m}^{n+k} a_{i-k} = \sum_{i=m-k}^{n-k} a_{i+k}$$

   (11)

Notasi Produk¶

Analogi dengan notasi Sigma untuk penjumlahan berurutan, notasi huruf Yunani kapital Pi ($\Pi$) digunakan untuk menyatakan operasi perkalian beruntun dari suku-suku suatu barisan.

Sebagai ilustrasi aplikatif, penulisan operasi faktorial $n!$ dapat didefinisikan secara eksak menggunakan notasi ini

Sifat-sifat Operasioan Notasi Produk Misalkan $a_i$ dan $b_i$ adalah barisan bilangan real, dan $c$ adalah konstanta real. Operasi perkalian berurutan tunduk pada hukum-hukum berikut

1. Sifat perkalian konstanta\

   $$\prod_{i=1}^{n}c=c^n$$

   (14)

2. Sifat Homogenitas\

   $$\prod_{i=1}^{n} (c\cdot a_i) = c^n \cdot \prod_{i=1}^{n} a_i$$

   (15)

3. Sifat multiplikatif\

   $$\prod_{i=m}^{n} (a_i \cdot b_i) = \left( \prod_{i=m}^{n} a_i \right) \cdot \left( \prod_{i=m}^{n} b_i \right)$$

   (16)
   $$\prod_{i=m}^{n} \left(\frac{a_i}{b_i}\right) = \frac{\prod_{i=m}^{n} a_i}{\prod_{i=m}^{n} b_i}$$

   (17)

4. Sifat pergeseran indeks\

   $$\prod_{i=m}^{n} a_i = \prod_{i=m+k}^{n+k} a_{i-k}$$

   (18)

5. Hubungan identitas produk dan sigma\

   $$\ln \left( \prod_{i=m}^{n} a_i \right) = \sum_{i=m}^{n} \ln(a_i)$$

   (19)

Barisan dan Deret Aritmatika dan Geometri¶

Setelah menguasai representasi notasi operasi penjumlahan dan perkalian, analisis dilanjutnkan pada dua struktur barisan paling fundamental dalam matematika komponen diskrit, yaitu barisan aritmatika dan barisan geometri. Pada tingkat kompetisi, evaluasi terhadap kedua barisan ini tidak lagi berfokus pada visualisasi prosedural mentah, melainkan pada sifat-sifat analitik, karakteristik fungsional, perilaku limit (konvergensi), serta struktur gabungan (hibrida).

Barisan dan Deret Aritmatika¶

Sebuah barisan bilangan real $(a_n)$ dikatakan sebagai barisan aritmatika jika dan hanya jika selisih antara dua suku yang berurutan selalu konstan. Nilai konstan ini disebut sebagai beda ($b$). Secara rekursif, didefinisikan $a_{n+1}-a_n=b$. Suku umum ke-$n$ dirumuskan secara eksplisit sebagai:

Secara analitik, suku ke-$n$ dari barisan aritmatika dapat dipandang sebagai sebuah fungsi linier terhadap indeks $n$, yaitu $a_n = f(n) = bn+(a_1-b)$, di maana beda $(b)$ bertindak sebagai gradien (kemiringan) garis dan $(a_1-b)$ bertindak sebagai intersept-$y$ pada ruang kontinu.

Deret aritmatika $(S_n)$ didefinisikan sebagai jumlahan dari $n$ suku pertama barisan aritmatika. Formula baku jumlahan ini adalah:

Jika diekspansi terhadap variabel $n$, rumus $S_n$ akan membentuk sebuah fungsi kuadrat tanpa konstanta:

Karakteristik ini sangat krusial dalam identifikasi soal: jika sebuah deret $S_n$ dinyatakan dalam bentuk $An^2 + Bn$, maka deret tersebut mutlak merupakan deret aritmtaika dengan beda $b=2A$ dan suku pertama $a_1 = A+B$

Sifat-sifat Teoretis Lanjutan:

1. Sifat simteri indeks
   Untuk sembarng indeks $i, j, k, m \in \mathbb{N}$, jika berlaku kondisi keterikatan indeks $i+j=k+m$, maka berlaku identitas penjumlahan:

   $$a_i + a_j = a_k + a_m$$

   (23)

2. Suku tengah
   Jika banyaknya suku $n$ adalah bilangan ganjil, maka terdapat suku tengah eksak pada indeks $t=\frac{n+1}{2}$ yang memenuhi hubungan rataan:

   $$a_t=\frac{a_1+a_n}{2} \implies S_n = n\cdot a_t$$

   (24)

3. Trik representasi simetris
   Untuk menyederhanakan perhitungan sistem persamaan aljabar yang melibatkan jumlahan suku-suku aritmtaika, pemilihan variabel sebaiknya disusun secara simetris di sekitar suku tengah

   • Untuk 3 suku: $a-b, a, a+b$

   • Untuk 4 suku: $a-3b, a-b, a+b, a+3b$

Barisan dan Deret Geometri¶

Sebuah barisan bilangan real $(a_n)$ dengan unsur non-nol dikatakn sebagai barisan geometri jika dan hanya jika rasio pembagian antara dua suku yang berurutan selalu konstan. Nilia konstan ini disebut sebagai rasio ($r$). Secara rekursif, didefinisikan $\frac{a_{n+1}}{a_n}=r$. Suku umum ke-$n$ dirumuskan secara eksplisit sebagai:

Secara analitik, suku ke-$n$ dari barisan geometri dapat dipandang sebagai fungsi eksponensial terhadap indeks $n$. Jika kita mentransformasikan barisan geometri melalui fungsi logaritma, maka barisan baru $b_n=\ln (a_n)$ secar otomatis akan membentuk barisan aritmatika dengan beda sebesar $\ln (r)$.

Jumlahan $n$ suku pertama dari barisan geometri dirumuskan secara aljabar melalui formula pecahan berikut (untuk $r\neq 1$)

Sifat-sifat Teoretis Lanjutan

1. Sifat simetri multiplikatif indeks
   Untuk sembarang indeks $i, j, k, m\in \mathbb{N}$, jik berlaku kondisi keterikatan indeks $i+j=k+m$, mk berlaku identitas perkalian:

   $$a_i \cdot a_j = a_k \cdot a_m$$

   (27)

2. Suku tengah geometri
   Jika banyaknya suku $n$ adalah ganjil, maka kuadrat dari suku tengah $a_t$ pada indeks $t=\frac{n+1}{2}$ setara dengan hasil kali suku-ujungnya:

   $$a_t^2 = a_1\cdot a_n = |a_t|=\sqrt{a_1\cdot a_n}$$

   (28)

3. Trik representasi simetris
   Jika soal olimpiade melibatkan hasil kali dari suku-suku barisan geometri, modifikasi variabel berikut sangat disarankan

   • Untuk 3 suku: $\frac{a}{r}, a, ar$

Deret Geometri Tak Hingga dan Konvergensinya¶

Ketika batas atas jumlahan deret geometri diperluas hingga tak hingga $(n\to \infty)$, deret tersebtu bertransformasi menjadi deret geometri tak hingga, dinotasikan dengan

Perilaku dari $S_\infty$ dievaluasi berdasarkan nilai limit dari barisan jumlahan parsialnya $(S_n)$ ketika $n$ menuju tak hingga. Secara matematis, evaluasi analitik ini terbagi menjadi dua kondisi rigid:

1. Kondisi Konvergen (Memiliki Nilai Limit Tetap)
   Deret dikatakan konvergen (memusat menju suatu nilai real tertentu) jika dan hanya jika rasio $r$ berada secara ketakt di dalam interval terbuka:

   $$0<|r|<1$$

   (30)

   Berdasarkan analisi limit, jika $0<|r|<1$, maka nilai $\lim_{n\to \infty} r^n=0$. Akibatnya, formula jumlahan parsial bertransformasi menjadi:

   $$S_\infty = \lim_{n\to\infty} \frac{a_1(1-r^n)}{1-r} = \frac{a_1(1-0)}{1-r} = \frac{a_1}{1-r}$$

   (31)

2. Kondisi Divergen (Tidak Memiliki Nilai Limit Tetap)
   Deret dikatakan divergan (menyebar menuju tak hingga atau berosilasi) jika dan hanya jika rasio memenuhi kondisi $|r|\geq 1$ a. Jika $r\geq 1$, nilai jumlahan akan bertumbuh tanpa batas menuju $\infty$ atau $-\infty$ b. Jika $r\leq -1$, nilai jumlahan akan berosilasi secara ekstrem dan tidak pernah menetap pada satu titik koordinat linier.

Barisan dan Deret Aritmatika-Geometri (Hibrida)¶

Dalam beberap kasus tingkat lanjut, kita akan menemui sebuah barisan hibrida yang suku-sukunya dibentuk oleh hasil kali komponen barisan aritmatika dan komponen barisan geometri yang bersesuaian. Struktur ini dinamakan Arithmetico-Geometric Progression (AGP)

Suku ke-$n$ dari barisan hibrida ini memiliki struktur analitik:

Di mana $a_1$ adalah suku pertama aritmatika, $b$ adalah beda aritmatika, dan $r$ rasio geometri. Deret jumlahan parsial $n$ suku dari barisan ini dituliskan sebagai

Untuk mencari rumus tertutup dari $S_n$ tanpa menghafal formula yang sangat kompleks, olimpiade matematika mengajarkan teknik manipulasi pengosongan linier. Langkah-langkahnya adalah sebagai berikut:
Tuliskan persamaan $S_n$

Kalikan seluruh ruas dengan rasio $r$, lalu geser penulisannya satu suku ke kanan agar derajat variabel $r$ selaras:

Kurangkan persamaan pertama dengan persamaan kedua $\left((1-r)S_n\right)$

Hasi pengurangan mereduksi komponen aritmatika menjadi beda konstan $b$, menyisakan deret geometri murni di bagian tengah:

Dengan membagig seluruh ruas dengan $(1-r)$, didapatkan rumus jumlahan parsial tertutup untuk deret aritmatika-geometri

Apabila deret hibrida ini diperluas hingga tak hingga ($n\to \infty$) dengan prasyarat konvergensi geometri $0<|r|<1$, maka suku-suku yang mengandung komponen $\lim_{n\to\infty}r^n$ dan $\lim_{n\to\infty}n\cdot r^n$ akan bernilai nol. Melalui proses limitasi tersebut, formula deret hibrida tak hingga tereduksi secara elegan menjadi:

Prinsip Deret Teleskopik¶

Dalam kompetisi matematika, evaluasi penjumlahan atau perkalian beruntun dengan jumlah suku yang sangat besar (atau bahkan tak hingga) hampir tidak pernah diselesaikan melalui komputasi manual satu per satu. Pendekatan analitik yang paling tangguh untuk mereduksi kompleksitas deret semacam ini adalah melalui Prinsip Teleskopik.

Istilah “teleskopik” diadaptasi dari mekanisme tabung teleskop bajak laun (teropong lipat) kuno, yang terdiri dari banyak segmen silinder memanjang, namun dapat melihat dan menyusut ke dalam dirinya sendiri hingga hanya menyisakan segmen ujung paling luar. Secara matematis, prinsip ini memanfaatkan sifat pembatalan beruntun (saling menghilangakan) dari suku-suku yang berdekatan.

Konsep Dasar Pembatalan Suku (Teleskopik Penjumlahan)¶

Prinsip teleskopik pada penjumlahan terjadi ketika setiap suku dalam suatu deret dapat didekomposisi (dipecah) menjadi selisih dua nilai yang berurutan dari suatu barisan pendukung.

atau sebaliknya.

Jika kondisi ini terpenuhi, maka jumlahan deret tersebut akan mengalami pembatalan berantai:

Ekspansi deret ini akan menghasilkan:

Perhatikan bahwa suku $-b_2$ dibatalkan oleh $+b_2$, suku $-b_3$ dibatalkan oleh $+b_3$, dan seterusnya, memicu efek domino yang membatalkan seluruh suku di bagian tengah deret. Sisanya hanyalah suku pertama dari kurung pertama dan suku kedua dari kurang terakhir

Dalam persoalan OSN tingkat lanjut, suku penolah sering kali tidak berjarak 1 indek, melainkan $d$ indeks: $a_k = b_k - b_{k+d}$. Pada kasus ini, suku-suku yang tidak memiliki pasangan pembatalan di awal dan di akhir deret akan tersisa sebanyak $d$ suku.

Sebagai contoh, jika $a_k=b_k-b_{k+2}$, maka

Aplikasi Faktorisasi Aljabar dan Pecahan Parsial¶

Kendala umum dalam menerapkan prinsip teleskopik bukanlah pada proses mencoret suku yang dibatalkan, melainkan pada keahlian memanipulasi suku $a_k$ agar termodifikasi menjadi bentuk selisih $b_k-b_{k+1}$. Instrumen aljabar paling lazim untuk melakukan hal ini adalah dekomposisi Pecahan Parsial

Salah satu contoh kasus fundamental yaitu suku penyebut berderajat dua. Tinjau kembali suku barisan berbentuk pecahan rasional berikut:

Melalui identitas pecahan parsial, bentuk tersebut dapat direduksi secara ekuivalen menjadi selisih dua pecahan tunggal

Di sini, kita telah berhasil mengkonstruksikan barisan pembatal $b_k=\frac{1}{k}$. Apabila kita menjumlahan $a_k$ dari $k=1$ hingga $k=n$, kita mendapatkan

Manipulasi identitas ini dapat diperumum (digeneralisasi) untuk sembarang selisih konstanta pada penyebutnya. Untuk sembarang konstanta $d\neq 0$

Persamaan ini sangat vital dan wajib dikuasai secara intuitif. Pengali $\frac{1}{d}$ di depan tanda kurung mutlak diperlukan sebagai kompensasi (faktor korelasi) untuk menyetarakan pembilangannya.

Teleskopik Perkalian¶

Prinsip pembatalan berantai tidak bekerja secara eksklusif pada operasi penjumlahan, melainkan juga berlaku secara identik dna ekuivalen pada operasi perkalian beruntun. Bentuk teleskopik pada perkalian didasarkan pada eliminiasi pembilang dan penyebut (saling membagi menjadi angka 1)

Misalkan kita mengevaluasi produk $\prod_{k=1}^{n}a_k$. Jika suku umum $a_k$ dapat direpresentasikan sebagai rasio (hasil bagi) dari dua suku yang berurutan pada barisan penolong ($b_k$), yakni

Maka, perkalian parsial hingga suku ke-$n$ akan mengalami pencoretan silang diagonal

Melalui eliminasi faktor persekutuan antara pembilang dan penyebut pada pecahan yang bersebelahan, seluruh faktor di tengah deret akan lenyap, menyisakan pembilangan dari suku terakhir dan penyebut dari suku pertama.

Pembuktian dengan Induksi Matematika¶

Dalam matematika tingkat lanjut, kita sering kali berhadapan dengan pernyataan analitik, rumus barisan, atau teorema yang diklaim bernilai benar untuk setiap bilangan asli $n\in \mathbb{N}$. Untuk membuktikan kebenaran pernyataan pada himpunan yang tak hingga besarnya ini, kita tidak mungkin melakukan uji coba substitusi satu per satu secara manual. Instrumen pembuktian deduktif yang paling valid, formal, dan diakui secara absolut untuk menangani kasus ini adalah induksi matematika

Secara konseptual, induksi matematika dapat dianologikan dengan efek domino yang disusun berderet hingga tak hingga. Jika kita dapat menjatuhkan domino pertama, dan kita memiliki jaminan bahwa jatunya sebuah domino pasti akan menjatuhkan domino tepat di depannya, maka kita dapat menyimpulkan secara logis bahwa seluruh domino tersebut pada akhirnya akan jatuh.

Prinsip Induks Matematika Dasar¶

Prinsip Induksi Matematika Dasar bertumpu Aksioma Peano dan Sifat Terurut Sempurna (\textit{Well-Ordering Principle}) dari himpunan bilangan asli.

Misalkan $P(n)$ adalah sebuah proposisi (pernyataan matematis) yang bergnatung pada bilangan asli $n$. Jika kedua aksioma berikut dapat dibuktikan bernilai benar

1. Langkah Dasar: Proposisi $P(1)$ benar

2. Langkah Induksi: Untuk setiap bilangan asli $k$, jika diamsusikan bahwa $P(k)$ bernilai benar (asumsi ini disebut sebagai hipotesis induksi), maka dapat dibuktikan bahwa proposisi $P(k+1)$ juga bernilai benar

Maka, dapat disimpulkan bahwa $P(n)$ bernilai benar untuk setiap bilangan asli $n\geq 1$

Induksi Matematika Kuat¶

Dalam beberapa kasus pembuktian barisan rekursif atau teori bilangan kompleks, asumsi kebenaran pada suku tepat sebelumnya, yakni $P(k)$, tidak memberikan amunisi informasi yang cukup untuk membuktikan $P(k+1)$. Oleh karena itu, kita mendayagunakan bentuk induksi yang lebih komprehensif yang dikenal sebagai induksi matematika kuat.

Meskipun disebut “kuat”, secara struktur logika matematis, induksi kuat ekuivalen sepenuhnya dengan induksi dasar. Perbedaannya hanya terletak pada keluasan asumsi di langkah induksi.

Misalkan $P(n)$ adalah sebuah proposisi yang bergantung pada bilangan asli $n$. Jika dapat dibuktikan bahwa:

1. Langkah dasar: Proposisi $P(1)$ bernilai benar. (Sering kali diperlukan pengujian beberapa dasar tambahan seperti $P(2), P(3), \cdots$), bergantung pada derajat rekursif.

2. Langkah Induksi: Untuk sembarang bilangan asli $k$, jika diasumsikan bahwa seluruh proposisi sebelumnya yaitu $P(1), P(2), P(3), \cdots, P(k)$ bernilai benar secara simultan, maka dapat dibuktikan bahwa $P(k+1)$ juga bernilai benar.

Maka dapat disimpulan bahwa $P(n)$ bernilai benar untuk semua $n\in \mathbb{N}$

Barisan Rekursif Linier¶

Dalam pembahasan sebelumnya, kita menentukan suku ke-$n$ dari suatu barisan menggunakan rumus eksplisit yang bergantung langsung pada variabel indeks $n$. Namun, terdapat kelas barisan yang sangat luas di mana suatu suku didefinisikan berdasarkan kombinasi dari suku-suku sebelumnya. Barisan dengan karakteristik seperti ini disebut sebagai barisan rekursif atau relasi rekurensi.Pada tingkat kompetisi, penguasaan terhadap teknik reduksi aljabar untuk menyelesaikan relasi rekurensi linier merupakan salah satu instrumen paling vital dalam memecahkan masalah kombinatorik enumeratif, teori bilangan, maupun pemodelan aljabar tingkat lanjut.

Definisi dan Relasi Rekurensi Linier Berderajat Satu¶

Relasi rekurensi linier homogen berderajat satu hanya melibatkan satu suku tepat sebelum suku ke-$n$. Bentuk umumnya adalah:

dengan nilai awal $x_0$ atau $x_1$ yang diketahui.

Penyelesaian dari bentuk homogen derajat satu ini dapat diturunkan secara langsung secara berantai (iterasi):

Secara fungsional, relasi rekurensi linier homogen berderajat satu tidak lain adalah bentuk rekursif dari Barisan Geometri dengan rasio $c$.

Relasi Rekurensi Linier Berderajat Dua dan Persamaan Karakteristik¶

Relasi rekurensi linier homogen berderajat dua mendefinisikan suku ke-$n$ berdasarkan dua suku tepat sebelumnya. Bentuk umum dari relasi ini adalah:

di mana $A$ dan $B$ adalah konstanta real dengan $B \neq 0$, serta diperlukan dua nilai awal konstan (misalnya $x_0$ dan $x_1$) agar solusi barisan bersifat unik (tunggal)

Berdasarkan analogi penyelesaian derajat satu yang menghasilkan solusi eksponensial, kita dapat mengasumsikan (menebak) bahwa solusi dari relasi derajat dua ini juga memiliki struktur eksponensial murni, yaitu $x_n = r^n$ untuk suatu konstanta $r \neq 0$.Substitusikan pemisalan $x_n = r^n$ ke dalam relasi rekurensi utama:

Bagi kedua ruas dengan $r^{n-2}$ (karena $r \neq 0$), sehingga kita memperoleh sebuah persamaan kuadrat:

Persamaan kuadrat terakhir ini disebut sebagai Persamaan Karakteristik dari relasi rekurensi tersebut, dan akar-akar penyelesaiannya ($r_1$ dan $r_2$) disebut sebagai Akar Karakteristik.

Solusi eksplisit dari barisan $x_n$ akan bergantung sepenuhnya pada karakteristik dari akar-akar persamaan kuadrat tersebut, yang terbagi menjadi dua kasus rigid:

1. Kasus 1: Dua Akal Real Berbeda ($r_1 \neq r_2$)
   Jika diskriminan persamaan karakteristik bernilai positif ($D > 0$), maka diperoleh dua akar real yang berbeda, $r_1$ dan $r_2$. Karena relasi ini bersifat linier, maka kombinasi linier dari kedua solusi eksponensial tersebut juga merupakan solusi. Solusi umum dari barisan dirumuskan sebagai:

   $$x_n = C_1 r_1^n + C_2 r_2^n$$

   (58)

   di mana $C_1$ dan $C_2$ adalah konstanta real sembarang yang nilainya ditentukan secara spesifik melalui substitusi nilai awal $x_0$ dan $x_1$.

2. Kasus 2: Akar Real Kembar ($r_1 = r_2 = r$)
   Jika diskriminan persamaan karakteristik bernilai nol ($D = 0$), maka persamaan hanya menghasilkan satu akar real tunggal berserikat ($r$). Dalam situasi ini, bentuk $x_n = C_1 r^n + C_2 r^n$ tidak valid karena kedua suku dapat digabungkan dan kehilangan satu derajat kebebasan konstan. Sifat ketergantungan linier ini diselesaikan dengan menyisipkan variabel indeks $n$ pada suku kedua. Solusi umumnya dirumuskan sebagai:

   $$x_n = (C_1 + C_2 n)r^n = C_1 r^n + C_2 n r^n$$

   (59)

Barisan Fibonacci dan Lucas¶

Dua contoh barisan rekursif linier berderajat dua yang paling termasyhur dan memiliki kelimpahan sifat teorema di dalam olimpiade matematika adalah Barisan Fibonacci dan Barisan Lucas. Kedua barisan ini didefinisikan menggunakan relasi rekurensi yang identik secara struktural, namun dibedakan secara fundamental oleh nilai basis (kondisi awal) yang digunakan.

Karena kedua barisan di atas mematuhi relasi rekurensi $x_n - x_{n-1} - x_{n-2} = 0$, maka persamaan karakteristik untuk kedua barisan tersebut adalah sama, yaitu:

Menggunakan rumus kuadrat (rumus abc), diperoleh dua akar karakteristik berbeda:

Perhatikan sifat aljabar unik dari kedua akar ini: $\phi + \psi = 1$, $\phi \cdot \psi = -1$, dan $\phi - \psi = \sqrt{5}$.\ Melalui substitusi nilai awal masing-masing barisan untuk mencari konstanta $C_1$ dan $C_2$, kita dapat mendeduksikan Rumus Binet yang memberikan formula eksplisit non-rekursif untuk mencari suku ke-$n$:

• Rumus Binet untuk Fibonacci ($F_n$):\

  $$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}} = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right]$$

  (62)

• Rumus Binet untuk Lucas ($L_n$):\

  $$L_n = \phi^n + \psi^n = \left(\frac{1+\sqrt{5}}{2}\right)^n + \left(\frac{1-\sqrt{5}}{2}\right)^n$$

  (63)

Suku-suku pada barisan Fibonacci dan Lucas saling terikat erat melalui berbagai identitas aljabar yang mengagumkan. Beberapa identitas yang paling sering muncul sebagai teorema di OSN meliputi:

• Hubungan Inter-Barisan:\

  $$L_n = F_{n-1} + F_{n+1}\\ F_n = L_{n-1} + L_{n+1}$$

  (64)

• Identitas Jumlahan Linier Fibonacci:\

  $$\sum_{i=1}^n F_i = F_{n+2} - 1$$

  (65)

• Identitas Jumlahan Kuadrat Fibonacci:\

  $$\sum_{i=1}^n F_i^2 = F_n F_{n+1}$$

  (66)

• Identitas Cassini:
  Sifat deterministik yang menunjukkan osilasi selisih kuadrat suku tengah dengan hasil kali suku ujungnya.

  $$F_{n-1}F_{n+1} - F_n^2 = (-1)^n$$

  (67)

Dalam ranah Teori Bilangan Olimpiade, aspek aritmatika keterbagian suku-suku Fibonacci diatur oleh hukum-hukum keterikatan indeks yang sangat rigid:

• Sifat Keterbagian Indeks:\ Untuk $m \geq 3$, suku Fibonacci $F_m$ habis membagi $F_n$ jika dan hanya jika indeks $m$ habis membagi indeks $n$.

  $$F_m \mid F_n \iff m \mid n$$

  (68)

  (Contoh: karena $3 \mid 6$, maka $F_3 \mid F_6$, yaitu $2 \mid 8$, yang mana terbukti benar).

• Sifat Pembagi Persekutuan Terbesar (FPB): Operasi FPB pada dua suku Fibonacci memiliki sifat invarian yang setara dengan operasi FPB pada indeks-indeksnya.

  $$\text{FPB}(F_m, F_n) = F_{\text{FPB}(m, n)}$$

  (69)

• Koprima Berurutan: Dua suku Fibonacci yang terletak berdampingan (berurutan) dipastikan selalu relatif prima (saling koprima).

  $$\text{FPB}(F_n, F_{n+1}) = 1 \quad \text{untuk setiap } n \in \mathbb{N}$$

  (70)

Menganalisis Periode Barisan¶

Dalam studi matematika diskret dan teori bilangan, tidak semua barisan bertumbuh tanpa batas menuju tak hingga. Sering kali, terutama ketika barisan tersebut dioperasikan dalam ranah aritmatika modular, nilai-nilai suku pada barisan tersebut akan mengalami pengulangan dengan pola yang tetap. Memahami perilaku siklik atau periodik dari suatu barisan merupakan kunci untuk menyelesaikan persoalan evaluasi suku ke-$n$ di mana nilai $n$ bernilai sangat masif.

Konsep Barisan Periodik¶

Secara formal, sebuah barisan bilangan $(x_n)$ dikatakan periodik jika terdapat suatu bilangan asli $p \geq 1$ dan suatu bilangan asli $N \geq 1$ sedemikian sehingga berlaku kesamaan:

Bilangan asli $p$ terkecil yang memenuhi kondisi tersebut disebut sebagai periode fundamental (atau sekadar periode) dari barisan tersebut. Terdapat dua klasifikasi keketatan pada sifat periodik ini:

1. Periodik Murni (Strictly Periodic):
   Jika kondisi berulang tercapai sejak basis awal, yakni pada $N = 1$. Pengulangan siklus berlangsung sempurna tanpa ada “ekor” di awal barisan.

2. Periodik pada Akhirnya (Eventually Periodic):
   Jika kondisi berulang baru tercapai pada suatu indeks $N > 1$. Barisan ini memiliki fase transisi ireguler di awal sebelum akhirnya memasuki pola berulang yang stabil.

Sifat Periodik Barisan dalam Operasi Modulo¶

Konvergensi barisan menuju suatu siklus pengulangan paling sering dijumpai ketika kita mengevaluasi barisan rekursif linier dalam modulo suatu bilangan asli $m$. Terdapat sebuah landasan logis dalam kombinatorika yang menjamin bahwa setiap relasi rekurensi linier atas operasi modulo mutlak akan bersifat periodik: Prinsip Sarang Merpati (Pigeonhole Principle).

Misalkan kita mengobservasi sebuah barisan rekursif linier berderajat $k$, di mana setiap suku baru dikalkulasikan murni berdasarkan konfigurasi $k$ suku sebelumnya secara berurutan. Dalam modulo $m$, suatu bilangan hanya dapat memetakan dirinya ke dalam salah satu dari $m$ buah sisa pembagian yang mungkin, yakni Himpunan Residu $\{0, 1, 2, \dots, m-1\}$.

Karena status (keadaan) operasional dari barisan rekursif ini ditentukan secara unik oleh susunan $k$ buah elemen berurutan, maka hanya akan terdapat tepat $m^k$ permutasi susunan status berbeda yang mungkin terjadi. Berdasarkan Prinsip Sarang Merpati, apabila kita mengekspansi barisan tersebut hingga melebihi batas $m^k$ langkah, maka dipastikan setidaknya ada satu konfigurasi status yang termanifestasi lebih dari satu kali.

Misalkan konfigurasi $(x_i, x_{i+1}, \dots, x_{i+k-1})$ identik secara kongruensi modulo $m$ dengan konfigurasi $(x_j, x_{j+1}, \dots, x_{j+k-1})$ dengan jarak $i < j$. Mengingat suku-suku progresif selanjutnya didefinisikan murni oleh formula yang sama terhadap status pendahulunya, maka pola barisan secara kausalitas akan mereplikasi dirinya terus-menerus mulai dari indeks tersebut. Jarak selisih $(j - i)$ inilah yang membentuk fondasi untuk merumuskan kelipatan dari periode barisannya.

Dalam problematika OSN, instruksi untuk “mencari angka satuan” sesungguhnya bersifat ekuivalen secara aritmatika dengan mengevaluasi nilai barisan pada kongruensi modulo 10. Serupa dengan hal tersebut, pencarian dua digit terakhir adalah manifestasi dari evaluasi modulo 100. Pengeksploitasian sifat periodik ini menjadi satusatunya instrumen deterministik untuk mengurai suku dengan indeks astronomis (seperti $a_{2026^{2026}}$), sebab analisis hanya bertumpu pada sisa pembagian indeks raksasa tersebut oleh panjang periode fundamentalnya.

Penerapan konsep periodisitas paling elok dan ekstensif di dalam kurikulum olimpiade matematika teoretis terfokus pada Barisan Fibonacci dalam operasi modulo. Periode dengan mana siklus residu Barisan Fibonacci mereplikasi diri dalam modulo $m$ dikenal melalui terminologi khusus, yakni Periode Pisano, yang dinotasikan secara formal sebagai $\pi(m)$.

Relasi rekurensi eksak untuk Fibonacci adalah $F_{n+1} = F_n + F_{n-1}$. Dalam operasi kongruensi modulo $m$, relasi linier ini memegang keistimewaan karena fungsi rekurensinya dapat diinversi (dibalik arahnya) untuk melacak kembali suku-suku historisnya tanpa timbul ambiguitas operasional:

Berdasarkan kelenturan analisis mundur (backward analysis) ini, manakala teridentifikasi sebuah blok status $(F_j, F_{j+1})$ yang memiliki kesesuaian nilai modulo dengan blok status lain $(F_k, F_{k+1})$, maka penelusuran balik akan menuntun keduanya secara sinkron menuju pangkalan basis awal $(F_0, F_1) \equiv (0, 1) \pmod m$.

Konsekuensi analitik terpentingnya adalah: Barisan Fibonacci dalam ranah modulo $m$ selalu merupakan barisan periodik murni. Setiap fasenya dijamin tanpa pengecualian selalu diawali oleh residu kombo $0, 1$.

Struktur dari Periode Pisano mengidap beberapa properti baku yang sering diekstraksi sebagai aksioma cepat pada kompetisi matematika:

1. Siklus Modulo 10 (Analisis Satuan):

   Angka satuan dari deret Fibonacci dipastikan membentuk siklus sempurna tiap 60 indeks secara berkesinambungan. Secara sintaktik ditulis $\pi(10) = 60$. Implikasinya, untuk menentukan angka satuan dari sebuah suku seperti $F_{2026}$, komputasi direduksi menjadi penelusuran $2026 \equiv 46 \pmod{60}$, mengindikasikan bahwa angka satuan $F_{2026}$ berkesesuaian eksak dengan angka satuan $F_{46}$.

2. Kalkulasi Siklus Baku (Konstanta Bantuan):

   • $\pi(2) = 3$ (Menghasilkan deret paritas berulang: $0, 1, 1, 0, 1, 1, \dots$)

   • $\pi(3) = 8$

   • $\pi(4) = 6$

   • $\pi(5) = 20$

   • $\pi(100) = 300$ (Dua presisi digit terbelakang dari entitas Fibonacci menduplikasi diri per siklus 300 suku).

3. Paritas Periode:

   Eksklusif untuk bilangan bulat penguji $m > 2$, panjang metrik dari Periode Pisano $\pi(m)$ tidak pernah membentuk bilangan ganjil; panjangnya niscaya merupakan suatu bilangan genap.

4. Hukum Multiplikatif Teori Bilangan:

   Properti fungsi Pisano berlaku koheren terhadap kelipatan modul yang komposit. Misalkan dioperasikan pada dua basis modul bulat $a$ dan $b$ yang dijamin relatif prima atau saling koprima ($\text{FPB}(a, b) = 1$). Maka nilai periode untuk sintesis modulonya setara dengan Kelipatan Persekutuan Terkecil (KPK) parsialnya:

   $$\pi(ab) = \text{KPK}\big(\pi(a), \pi(b)\big)$$

   (73)

   Pembuktian langsung: $\pi(10) = \pi(2 \times 5) = \text{KPK}\big(\pi(2), \pi(5)\big) = \text{KPK}(3, 20) = 60$.