Pigeonhole Principle ... (ii)

Lanjutan dari sebelumnya

Kasus F:
Seperti kasus nomor A. Sekarang, di laci ada 12 kaos kaki hitam, 13 kaos kaki putih, 20 kaos kaki biru, 5 kaos kaki merah, 1 kaos kaki hijau, dan 1 kaos kaki kuning. Berapa banyak kaos kaki minimal yang harus diambil agar setidaknya:
a) terdapat 2 kaos kaki yang memiliki warna yang sama
b) terdapat 2 kaos kaki yang memiliki warna yang berbeda.

(Ayo berpikir)...
Jawaban dapat dilihat di bawah... ^^..
Ada juga kasus-kasus lain yang lebih seru dan menantang..
=========================================================================

Jawaban Kasus F:

a)	Kemungkinan terburuk yaitu saat mengambil 6 kaos kaki yang semuanya berbeda warna (hitam, putih, biru, merah, hijau, dan kuning). Oleh karena itu, kaos kaki minimal yang harus diambil agar setidaknya terdapat 2 kaos kaki dengan warna sama adalah 7 buah.
b)	Kemungkinan terburuk yaitu saat mengambil 20 kaos kaki yang semuanya berwarna biru. Oleh karena itu, kaos kaki minimal yang harus diambil agar setidaknya terdapat 2 kaos kaki dengan warna berbeda adalah 21 buah.

Nah, ternyata masalah tersebut dapat ditinjau berdasarkan kemungkinan terburuknya. Berikut di bawah, akan dijelaskan kasus-kasus yang membuat kita harus meninjau kemungkinan terburuknya sebelum menuju kesimpulan...

=========================================================================

Pigeonhole Principle dan Teori Bilangan II

Kasus G:
Diberikan barisan bilangan dari 1,2,3,...,100. Jika dari barisan bilangan tersebut diambil 51 bilangan, buktikan bahwa paling tidak ada 2 bilangan yang selisihnya 50.

Jawab:
Sebelumnya, perhatikan di bawah.
Diberikan barisan dari a+1 sampai 2n, sebagai berikut:

a+1, a+2, a+3, a+4, ... , a+2n-1, a+2n

Dengan demikian, akan terdapat pasangan bilangan yang selisihnya n, seperti (a+1, a+n+1), (a+2, a+n+2), ... , (a+n, a+2n). Jumlah seluruh pasangan ini berjumlah n. Maka, dengan mengambil bilangan yang minimal n+1, maka pasti akan selalu ada pasangan bilangan yang selisihnya n.

Soal di atas diambil a = 0 dan n=50.

Kasus H:
Diberikan barisan bilangan dari 1,2,3,...,100. Jika dari barisan bilangan tersebut diambil 55 bilangan, buktikan bahwa paling tidak ada 2 bilangan yang selisihnya 9.

Jawab:
Perhatikan bahwa sesungguhnya soal ini tidak berbeda jauh dengan soal sebelumnya. Kemungkinan terburuk yaitu dengan mengambil n bilangan dari barisan 2n (dimana n=9), sehingga bilangan yang selisihnya 9 tidak didapat. Berikut akan dijabarkan pemilihan kemungkinan terburuknya:

Dari 1,2,3, ..., 18 dipilih 9 bilangan, yaitu 1,2,3,...,9.
Dari 19, 20, 21, ..., 36 dipilih 9 bilangan, yaitu 19, 20, 21, ... , 27.
Dari 37, 38, 39, ..., 54 dipilih 9 bilangan, yaitu 37, 38, 39, ..., 45.
Dari 55, 56, 57, ..., 72 dipilih 9 bilangan, yaitu 55, 56, 57, ..., 63.
Dari 73, 74, 75, ..., 90 dipilih 9 bilangan, yaitu 73, 74, 75, ..., 81.
Dari 91,92,93,...,100 dipilih 9 bilangan, yaitu dari 91,92,93, ..., 99.

Dengan demikian, bilangan yang terpilih ada 54 bilangan. Masih kurang 1 bilangan untuk mencapai 55 bilangan, dan bilangan apapun yang dipilih akan menyebabkan adanya bilangan yang selisihnya 9, misalnya 100 (100-91 = 9), atau 17 (17-8=9 dan 26-17 = 9). Dengan pemilihan kemungkinan terburuk ini sudah ada bilangan yang selisihnya 9, maka pernyataan di soal terbukti kebenarannya.

Kasus I:
Diberikan barisan bilangan dari 1,2,3,...,100. Jika dari barisan bilangan tersebut diambil 55 bilangan, buktikan bahwa belum tentu ada 2 bilangan yang selisihnya 11.

Jawab:
Sama seperti sebelumnya.
Dari 1,2,3, ..., 22 dipilih 11 bilangan, yaitu 1,2,3,...,11.
Dari 23,24,25, ..., 44 dipilih 11 bilangan yaitu 23,24,25,...,33.
Dari 45,46,47,..., 66 dipilih 11 bilangan, yaitu 45,46,47,..., 55.
Dari 67,68,69, ... , 88 dipilih 11 bilangan, yaitu 67,68,69,...,77.
Dari 89,90,91, ...,100 dipilih 11 bilangan, yaitu 89,90,91,...,99.

Perhatikan bahwa kita sudah memilih 55 bilangan, namun belum ada pasangan bilangan yang selisihnya 11. Maka, pernyataan di soal terbukti.

Note: Seandainya, jumlah bilangan yang diambil adalah 56, maka paling tidak ada 2 bilangan yang selisihnya 11, karena bilangan yang ke-56 akan menyebabkan selisih 11 dengan salah satu dari 55 bilangan yang sudah ada sebelumnya.

Kasus J:
Latihan si Master Catur
Seorang master catur punya 77 hari untuk latihan sebelum turnamen dimulai. Untuk itu ia menerapkan program latihan: setiap hari paling tidak bermain catur sekali, tetapi secara keseluruhan banyaknya permainan tidak lebih dari 132. Buktikan bahwa ada barisan hari berturut-turut disaat ia bermain catur sebanyak tepat 21 kali.

Jawab:
Pertama, ada 77 hari untuk latihan dan setiap hari minimal satu permainan. Kedua ada 132, yaitu banyaknya seluruh permainan maksimal dalam latihan. Jika kita memisalkan  sebagai banyaknya permainan yang telah ia lakukan sampai hari ke-i dengan i = 1, 2, …, 77, maka  paling tidak 1, paling tidak 2, dst, sampai  paling banyak 132. Secara matematika dapat dituliskan sebagai berikut.

Perhatikan bahwa kasus ini identik dengan kasus berikut:
"Diberikan barisan bilangan dari 1,2,3,...,132. Jika dari barisan bilangan tersebut diambil 77 bilangan, buktikan bahwa paling tidak ada 2 bilangan yang selisihnya 21."

Maka, kasus ini sama seperti Kasus H sebelumnya.

Tinjau kemungkinan terburuknya:
Dari 1,2,3, ..., 42 dipilih 21 bilangan, yaitu 1,2,3,...,21.
Dari 43,44,45, ..., 84 dipilih 21 bilangan yaitu 43,44,45,..., 63.
Dari 85, 86, 87, ..., 126 dipilih 21 bilangan, yaitu 85,86,87, ..., 105.
Dari 127,128, ...,132 dipilih semuanya (6 bilangan), yaitu 127,128,129,...,132.

Sudah ada 69 bilangan yang dipilih. Artinya, 1 bilangan lagi yang dipilih, apapun itu, mengakibatkan ada pasangan yang selisihnya 21. Artinya, 70 bilangan saja sudah cukup untuk membuat adanya paling tidak 2 bilangan yang selisihnya 21, sedangkan di soal tertulis "77 bilangan" yang artinya kondisi yang berlebih.

Jadi, terbukti bahwa ada barisan hari berturut-turut disaat ia bermain catur sebanyak tepat 21 kali.

Note: Soal yang sama bisa dilihat di majalah Zero edisi ke-2 halaman 14(sumber lihat di bawah), namun di sini saya mengoreksi sedikit solusi yang dijabarkan di sana.

Kasus K:
Blok Yang Habis Dibagi n – dari Erdos pada Marta Sved.
Misalkan kita tulis secara acak suatu barisan bilangan bulat yang terdiri dari n suku, maka terdapat suatu blok suku-suku yang berurutan yang jumlahnya habis dibagi n. Contohnya, kita bangun secara acak barisan dengan 7 suku:

54, 22, 9, 15, 24, 59, 102

Perhatikan bahwa terdapat suatu blok: 15, 24, 59 yang jumlahnya 98, habis dibagi 7. Buktikan hasil ini.

Jawab:
Misalkan barisan tersebut adalah 
Sekarang, misalkan simbol  menyatakan deret barisan, yang dijabarkan sbb:





Jika  dapat dibagi n atau  mod 7 = 0, maka pembuktian selesai.

Namun, jika  tidak dapat dibagi n, maka kita tinjau sisa pembagian terhadap n dari  yang mungkin (dari 1 sampai n-1). Artinya, ada n-1 jumlah kemungkinan sisa pembagian. Misalkan jika n=7, maka kemungkinan sisa pembagian terhadap 7 selain nol adalah 1, 2, 3, 4, 5, dan 6.

Namun, karena jumlah blok  ada sebanyak n buah sedangkan kemungkinan sisa pembagian yang berbeda adalah n-1 buah, artinya pasti ada  dan  () yang sisa pembagiannya sama. Karena sisa pembagiannya sama, maka:

Maka, kita telah mendapatkan blok yang habis dibagi n, yaitu dari  sampai .

Kasus J:
Misalkan A adalah himpunan dua puluh bilangan berbeda yang dipilih dari himpunan B = {1, 4, 7, …, 100}. Buktikan bahwa paling tidak ada dua anggota A berbeda yang jumlahnya 104.

Jawab:
Pertimbangkan himpunan bilangan C, himpunan semua pasangan yang jumlahnya 104, yang anggotanya diambil dari B.

C = {(4,100),(7,97),...,(49,54)}.

Terlihat bahwa ada tujuh belas anggota C. Ambil salah satu bilangan dari setiap pasangan di C, tambahkan 1 dan 52 (dua bilangan di B yang tidak ada di C) untuk membentuk A. Karena baru ada sembilan belas anggota, kita harus mengambil salah satu bilangan di C. Apapun bilangan itu, pasangannya sudah ada di A dan jumlahnya 104. Terbukti.

=========================================================================

Materi Pigeonhole principle sesungguhnya banyak sekali ditemukan di kehidupan kita sehari-hari, dan kasusnya tidak sesederhana kasus-kasus di atas. Selain, teori bilangan, prm bisa muncul dalam kasus geometri, trigonometri, dan sebagainya.

Dalam ilmu komputer pun, prm muncul secara alami pada masalah tabel hash. Tumbukan dalam tabel hash tidak dapat dihindari karena banyaknya kunci yang mungkin melebihi batas kapasitas suatu array. Untuk mengatasinya didefinisikan perumuman prm yang bersifat probabilistik.

Namun, masalah-masalah tersebut tidak akan dibahas sekarang. Mungkin, kalau aku ada waktu, materi ini akan saya lanjutkan.. ^^.. See you.

Read More

Pigeonhole Principle ... (i)

Pigeonhole Principle merupakan salah satu teorema matematika yang menarik..

Sebelumnya, perhatikan kasus berikut:

Kasus A:

Misalkan di rumahmu ada sebuah laci dan di dalam laci tersebut ada kaos kaki: 12 hitam dan 10 putih yang tersebar secara acak. Suatu hari, lampu di rumahmu mati, maka berapa kaos kaki MINIMAL yang harus kamu ambil agar dapat memperoleh sepasang kaos kaki dengan warna yang sama??

(Berpikirlah beberapa saat)...

(sudah dipikirkan??)

Kalau sudah, lanjut baca lanjutannya di bawah..
Dan, masih ada banyak sekali kasus yang akan dipaparkan selain di atas.. ^^.
=========================================================================

Pigeonhole Principle

Jawaban kasus A : cukup 3 kaos kaki..

Tentunya, kasus seperti di atas memang sangatlah mudah dan sederhana, namun dalam penerapannya bisa bermacam-macam, dan bisa secara tak terduga mengejutkan...

Pigeonhole Principle:

Jika k + 1 merpati dimasukkan ke dalam k rumah, maka ada satu rumah yang berisi paling tidak 2 merpati.

Note: gambar di atas menunjukkan bahwa ada 9 kotak, dan seharusnya ada 10 merpati. Merpati yang ke-10 yang ditempatkan di rumah manapun menyebabkan rumah itu berisi minimal 2 merpati..

Note: jumlah k+1 itu tidak wajib. Asalkan jumlah merpati lebih besar dari jumlah rumahnya, maka prinsip ini selalu berlaku.

Tentunya, bukti sudah jelas, bukan? Pigeonhole principle sering disebut juga sebagai prm (prinsip rumah merpati) ataupun Dirichlet drawer principle. Nama Dirichlet muncul karena dipercaya pertama kali dinyatakan oleh matematikawan Jerman bernama Gustav Lejeune Dirichlet pada tahun 1834.

Selain kasus kaos kaki di atas, perhatikan juga contoh mudah mengenai prm di bawah:

Kasus B:
Selidikilah kebenaran kasus di bawah ini:
1. Di antara tiga orang, maka pasti ada dua orang yang berjenis kelamin sama.
2. Dari 32 orang, pasti ada 2 orang yang memiliki tanggal lahir yang sama.
3. Jika kn + 1 kelereng didistribusikan ke dalam n kotak, maka satu kotak akan berisi paling tidak k + 1 kelereng.
4. Sebuah garis l di dalam bidang melalui sisi-sisi segitiga ABC dengan tidak melewati titik sudutnya. Maka, garis itu tidak akan melewati ketiga sisi segitiga.

Jawab:
Semua BENAR.
Perhatikan bahwa nomor 3 merupakan bentuk prm yang lebih umum. (prm yang ditulis disini diperoleh untuk k = 1).

Kasus C:
Dapatkah kamu membuktikan bahwa ada paling tidak dua orang penduduk di Bandung yang banyaknya rambut di kepala sama?

Jawab:
Sekilas, mungkin kamu akan berusaha memanggil satu demi satu penduduk di Bandung.. Kemudian, menyuruh mereka mencabuti setiap rambut mereka untuk dihitung.. Wahahaha.. Benar-benar lucu. Namun, untuk membuktikannya, kamu tidak perlu melakukan hal bodoh seperti itu. Gunakan prinsip rumah merpati di atas.

Perkirakan kemungkinan terburuk bahwa jumlah rambut terlebat adalah 1000 helai rambut per inchi persegi. Kemudian asumsikan kemungkinan terburuk bahwa rambut itu menutupi luas 1000 inchi persegi, maka jumlah helai rambut terlebat manusia ada sekitar 1000.000 helai.. (Ini sudah terburuk sekali)..

Membandingkannya dengan jumlah penduduk Bandung, yaitu sekitar 2.500.000 juta jiwa (tahun 2005, dan pasti akan terus bertambah), maka jumlah 1000.000 sekitar 2.5 kali lebih kceil dibandingkan jumlah penduduknya. Di kasus ini, kita dapat menganalogikan 2.500.000 sebagai jumlah merpati, dan 1000.000 sebagai jumlah rumah yang ada. Maka, akan ada paling tidak 2 orang yang memiliki jumlah rambut yang sama.

=========================================================================

Pigeonhole Principle dan Teori Bilangan

Kasus D:
Jika dari barisan bilangan 1,2,3,4,5,...,400 diambil 201 bilangan, maka buktikanlah bahwa dari 201 bilangan tersebut paling tidak ada dua bilangan yang koprima (faktor pembagi terbesarnya 1).

Jawab:
Konon, Erdos pernah mengundang makan siang seorang anak ajaib, Lajos Posa. Di tengah makan siang Erdos bertanya ”Bagaimana kamu membuktikan bahwa jika kita mengambil n+1 bilangan dari himpunan bilangan 1, 2, 3, ..., 2n, maka ada dua bilangan yang koprima?”

Sesaat pertanyaan tersebut tidak cukup jelas. Namun, argumentasi Lajos yang dikemukakan sesaat setelah pertanyaan selesai membuat pertanyaan Erdos lebih jelas: dalam n + 1 bilangan yang terpilih pasti ada dua bilangan yang berbeda satu alias saling berurutan dan dua bilangan tersebut koprima.

Kasus E:
Jika dari barisan bilangan 1,2,3,4,5,...,400 diambil 201 bilangan, maka buktikanlah bahwa dari 201 bilangan tersebut paling tidak ada dua bilangan dimana bilangan yang satu yang membagi bilangan yang lain.

Jawab:
Masalah di bawah ini mirip dengan masalah sebelumnya:
Dari himpunan bilangan bulat 1, 2, 3, ..., 2n, ambil n + 1 bilangan, sebutlah himpunan ini A. Maka selalu ada dua bilangan di A sehingga bilangan yang satu membagi bilangan yang lain. Masalah ini berhasil dibuktikan pula oleh Lajos.

Kita dapat menulis kembali setiap anggota dalam himpunan A dalam bentuk: . Tentunya, karena yang diminta di soal adalah bilangan yang membagi bilangan lain, maka asumsikan bahwa anggota-anggota dalam himpunan A tidak boleh mengandung nilai m yang membagi satu sama lain. Dalam hal ini, m adalah bilangan ganjil yang mungkin dari 1,2,3,..., 2n. Artinya, m maksimal ada sebanyak n buah.

Perhatikan bahwa karena kita mengambil n+1 bilangan, maka artinya pernyataan di atas adalah kontradiksi. Akibatnya, pasti akan ada 2 bilangan dengan nilai m yang sama. Artinya, kedua bilangan itu dapat membagi bilangan yang lain.

=========================================================================
Eit, materi mengenai pigeonhole principle tidak berhenti sampai di sini saja..!!

Masih ada lanjutannya, 

Read More

Mengubah 4 kubus menjadi 3 kubus

Diberikan susunan korek api seperti pada gambar. Terlihat bahwa ada 4 kubus di sana.

Bisakah kalian memindahkan 1 batang korek api, sehingga tersisa 3 kubus?

Puzzle ini diambil juga dari game Professor Layton. (dan sangat mudah sekali, mungkin tidak sampai 1 menit untuk dipecahkan.)

Read More

iseng tanggal lahir

Kadang, temenmu rewel untuk tidak memberitahukan tanggal dan bulan kelahirannya.. Yah, mungkin karena alasan privasi dan sebagainya.. Hahaha. Di sini akan diberitahukan salah satu trik untuk mengetahui tanggal lahir temanmu dengan salah satu permainan teka-teki matematika yang *sangat* sederhana.. XDXD

Berikan instruksi-instruksi di bawah ini pada temanmu sebagai berikut.
1. "Pertama, pikirkan tanggal lahirmu."
2. "Kalikan dengan 5"
3. "Tambahkan dengan 6"
4. "Kalikan dengan 4"
5. "Tambahkan dengan 7"
6. " Kalikan dengan 5"
7. "Selanjutnya, tambahkan dengan bulan kelahiranmu"
8. "Sebutkan angka itu"
9. Kurangkan dengan 165 (Langkah ini hanya boleh kita yang tahu.)

Maka, kita dapat mengetahui tanggal dan bulan lahir temanmu. Sebagai contoh, tanggal lahir temanmu itu 29 dengan bulan 12. Maka, langkahnya seperti ini:
1. Tanggal lahir = 29
2. Kalikan 5: 29x5 = 145
3. Tambahkan 6: 145+6 = 151
4. Kalikan 4: 151x4 = 604
5. Tambahkan dengan 9: 604+9 = 613
6. Kalikan dengan 5: 613x5 = 3065
7. Tambahkan bulan kelahiran: 3065+12 = 3077.
8. Kurangkan dengan 165: 3077-165 = 2912 (Langkah ini hanya kita yang boleh tahu.. Kenapa? Supaya dia mau menyebutkannya.. XDXDXD)

2912 berarti tanggal 29 bulan 12... Mudah bukan??
Bagaimana ini bisa terjadi? Hal ini dapat dijawab dengan mudah, dengan memisalkan tanggal lahir dan bulan lahir sebagai variabel, misalnya x dan y.. Jika dijabarkan, maka akan menghasilkan 100x+y. Sebenarnya, ada contoh lain yang lebih rumit, dengan menggunakan pembagian, modulo, pangkat, akar, dan sebagainya. Teki-teki itu lebih rumit, sehingga tidak dulu dibahas di post ini..

So, temanmu yang sulit memberitahukan tanggal lahirnya tentunya akan ketahuan deh.. Hohohoho.. ^^.. (Btw, kalau untuk mengetahui sekaligus tanggal, bulan, dan tahun lahir, ada lagi cara lain.. Mungkin kamu berniat membuatnya sendiri dengan membentuk 10000x+100y+z dimana x,y, dan z merupakan tanggal, bulan, dan tahun lahir).. ^^

Read More

Bilangan Fibonacci

Tentunya, kita semua mengenal bilangan Fibonacci (atau disebut juga barisan Fibonacci). Suku pertama barisan ini adalah 1, begitu pula dengan suku ke-2. Suku berikutnya merupakan penjumlahan 2 suku sebelumnya.

Suku-suku positif barisan Fibonacci:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

Di post ini, kita akan mengenal lebih jauh mengenai bilangan Fibonacci ini. Dimulai dengan sejarah bilangan Fibonacci, bahkan sampai terciptanya rumus Binet, yang digunakan untuk mencari suku ke-n dari Fibonacci, yaitu sebagai berikut.

dimana  = 

Tolong pembaca jangan mabok dulu melihat rumus di atas. ^^. Justru, dengan melihat post ini diharapkan kemabokan pembaca bisa hilang, karena penurunan rumus ini tuh mudah banget...!! (Walaupun perlu bagi saya selama meneliti barisan Fibonacci ini selama bertahun-tahun... Halah.. Lebay.. ~_~)

=========================================================================

== ASAL MUASAL BARISAN FIBONACCI ==

Barisan Fibonacci berawal dari sebuah kasus yang dikemukakan oleh seorang matematikawan Italia, Fibonacci, dalam bukunya yang berjudul Liber Abaci. Kasus itu dijelaskan sebagai berikut:

Sepasang kelinci muda (jantan dan betina) ditempatkan di suatu pulau. Asumsikan bahwa kelinci tidak akan melahirkan sebelum berumur 2 bulan. Kemudian, setelah berumur 2 bulan, setiap pasang kelinci akan melahirkan sepasang kelinci setiap 1 bulan. Pertanyaannya: Berapa banyak pasang kelinci yang ada di sana setelah n bulan? (Kita juga menggunakan asumsi bahwa kelinci tidak akan pernah mati.)

Kita dapat mengilustrasikan masalah kelinci itu seperti tabel di bawah.
Asumsikan bahwa gambar 1 kelinci berarti 1 pasang kelinci.

Keterangan:
	= kelinci muda
	= kelinci 1 bulan
	= kelinci berumur ≥ 2 bulan

Bulan ke-	Ilustrasi kelinci yang ada di pulau	Total pasang kelinci
1	__	1
2	__	1
3	_________	2
4	_________ __	3
5	_________ ______	5
6		8
7	dan seterusnya...	13

Kasus kelinci saat itu belumlah menjadi perhatian yang yang menarik. Kemudian, pada abad ke-19, Edouard Lucas mendefinisikan kembali barisan tersebut, dan menamakan barisan tersebut sebagai barisan Fibonacci di mana setiap sukunya diberikan simbol .

Barisan Fibonacci dapat didefinisikan kembali sebagai berikut:

.
 untuk 

Note: kita juga dapat mendefinisikan .

Untuk selanjutnya, barisan Fibonacci ini muncul dalam berbagai macam aplikasi. Sebagai contoh, di dalam bidang pertanian, jumlah pola spiral yang muncul pada tanaman (sering disebut sebagaiphyllotaxis) selalu merupakan pola barisan Fibonacci.

=========================================================================

== MENCARI JUMLAH N SUKU PERTAMA BARISAN FIBONACCI ==

Dalam hubungannya mencari jumlah n suku pertama, pembicaraan kita tak terlepas dari deret. Kita beri simbol  untuk menyatakan jumlah n suku pertama tersebut

Note: Pemberian simbol  untuk deret Fibonacci ini tidak universal, dan tidak berlaku di tempat lain.

Agar menjadi gambaran yang jelas, berikut akan disertakan tabel  dan .
Tabel  (barisan Fibonacci)

f1	f2	f3	f4	f5	f6	f7	f8	f9	f10
1	1	2	3	5	8	13	21	34	55

Tabel  (deret Fibonacci)

F1	F2	F3	F4	F5	F6	F7	F8	F9	F10
1	2	4	7	12	20	33	54	88	144

Jelas bahwa kita menemukan identitas berikut:

berlaku untuk .

Berikut bukti identitas tersebut secara eksplisit:
Kita tahu bahwa  untuk . Jika kita mensubstitusikan , maka pernyataan sebelumnya bermakna sama dengan: untuk . Atau, jika kita tulis ulang dengan pemindahan ruas, akan sama dengan:

 untuk 

Oleh karena itu:

 = 
=
 =

TERBUKTI

=========================================================================

== MENCARI FORMULA BARISAN FIBONACCI ==
== RUMUS BINET==

Jika kita ingin mencari suku ke 5 () dari barisan fibonacci, tentunya kita lakukan dengan cara menghitung ulang secara 5 kali. Lebih tepatnya, kita melakukan penjumlahan 5 kali. Lalu bagaimana dengan  atau ? Mampukah kita menghitungnya? Jawabanya: tentu saja sanggup, tapi memakan waktu lama. Cara yang lebih baik yaitu dengan menggunakan komputer, karena komputer mampu menghitung dengan sekejab. Namun, tetap saja, algorima yang digunakan haruslah rekursif, yaitu seperti definisi fungsi Fibonacci sebelumnya di atas. Apakah ada formula lain yang mampu menghitung secara jauh lebih cepat, tanpa melakukan perhitungan secara rekursi??Jawabnya adalah YA.

Berikut diberikan formula (rumus Binet) untuk menentukan suku ke-n dari barisan fibonacci.

dimana  = .

Phi () sering disebut juga sebagai golden number. Nilai  juga sama dengan  atau mendekati 

Tentu saja, kalian bisa mencocokan hasil perhitungan ini dengan hasil perhitungan manual.
Sebagai contoh n = 9. Maka:



Hasilnya tidak diragukan lagi. Memang sama..!!

Mungkin bagi kalian yang pertama kali melihat rumus Binet, awalnya shock.. (Hayolah ngaku.. Aku sendiri tuh shock banget.. :P). Rumus itu sungguh ajaib, karena ruas kanan formulanya penuh dengan bilangan irasional, namun bagian di ruas kiri adalah bilangan bulat. Sungguh ajaib.!! Bagi kalian yang ingin melihat lebih jauh penurunan rumus tersebut, silakan lanjutkan membaca di bawah.. ^^

BUKTI RUMUS BINET

Barisan Fibonacci merupakan barisan kombinasi linear . Namun, kita juga dapat mendekati barisan ini secara geometrik.

Asumsikan bahwa:  dimana a merupakan konstanta awal yang bukan nol. Dengan demikian:

Dengan membagi kedua ruas dengan , kita dapatkan:

Bentuk di atas merupakan bentuk persamaan kuadrat. Oleh karena itu, kita gunakan rumus untuk menyelesaikan persamaan tersebut. Maka, kita dapatkan: dan . Untuk mempermudah penulisan, kita tahu bahwa hasil dari merupakan golden number, maka kita simbolkan dengan . Hasil dari  juga ternyata adalah .

Kita mendapatkan 2 buah r dalam barisan ini. Artinya, barisan fibonacci merupakan barisan geometri kombinasi menggunakan 2 buah rasio tersebut. Ingat kembali asumsi awal bahwa . Karena, kita memiliki 2 buah rasio r, maka kita definisikan kembali

dimana  dan  adalah konstanta bukan nol.

Kombinasi linear tersebut dapat dibuktikan kebenarannya, seperti yang ditunjukkan di kotak warna biru di bawah.

Bukti bahwa barisan Fibonacci dapat didefinisikan sebagai .

Kita buktikan secara induksi matematika. Anggap bahwa  adalah BENAR.

Kita tahu bahwa: , maka:

Namun, kita tahu dari persamaan karakteristik sebelumnya bahwa  dengan membaginya dengan , kita dapatkan . Begitu pula dengan , kita dapatkan .

Karena persamaan  sesuai dengan definisi awal, maka TERBUKTI secara induksi matematik.

   ... (a)
     ... (b)
Dengan menyelesaikan persamaan (a) dan (b), maka kita dapatkan  dan .

Maka, kita sudah mendapatkan semua komponen formula Fibonacci.

Dengan demikian, formula (rumus) Binet terbukti.
Dapat disingkat menjadi:

dimana  = .

=========================================================================

== CLOSING==

Jika dirasa rumus Binet tersebut terlalu menyulitkan, kita bisa menggunakan hampiran yang dapat mengurangi kerumitan tersebut. Karena , maka. Jadi, kita bisa meniadakan unsur . Maka, hampiran rumus Binet adalah sebagai berikut.

untuk n cukup besar.

Barisan fibonacci yang dibahas di post ini merupakan barisan dengan suku-suku positif. Kita juga dapat menuliskan suku-suku negatifnya dan hal ini juga dijelaskan dalam formula Binet, sebagai berikut:

...-21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21,...

Sebenarnya, masih banyak lagi identitas Fibonacci yang ada. Salah satunya sudah dibahas di atas, yaitu . Namun, karena identitas-identitas tersebut sangat banyak dan saya sedikit malas untuk membuatnya, dan juga karena keterbatasan tempat di post ini, maka sebaiknya materi tersebut dibahas lain waktu. Kalau ada request untuk membuat materi mengenai identitas-isentitas Fibonacci, maka saya akan segera membuatnya.. ^^

Sekian, materi post ini. Semoga membantu menghilangkan penasaran kalian.. ^^

Read More