Nombor Fibonacci

Pengenalan

Kebanyakan pengenalan melibatkan nombor Fibonacci menarik dari hujah kombinatorik.
F(n) boleh ditafsirkan sebagai bilangan cara menjumlahkan 1 dan 2 kepada n − 1, dengan kelaziman yang F(0) = 0, bermakna tiada jumlah akan menambah sehingga −1, dan F(1) = 1, bermaksud jumlah kosong akan "bertambah" untuk 0.
Ini tertiba bagi perihal penghasil tambah.
Sebagai contoh, 1 + 2 and 2 + 1 adalah dianggap dua jumlah yang berbeza dan dikira dua kali.

Pembuktian

Kita mesti membuktikan bahawa urutan nombor yang ditakrifkan oleh tafsiran kombinatorik di atas memenuhi hubungan jadi semula yang sama dengan nombor Fibonacci (dan jadi sememangnya sama dengan nombor Fibonacci).
Set bagi cara F(n+1) untuk membuat jumlah bertertib 1 dan 2 yang berjumlah ke n boleh dibahagikan kepada dua set tak bertindih. Set pertama yang mengandungi jumlah penghasil tambah pertamanya 1; jumlah baki kepada n−1, maka F(n) menjumlah pada set pertama. Set kedua yang mengandungi jumlah penghasil tambah pertamanya 2; jumlah baki kepada n−2, maka F(n−1) menjumlah pada set kedua. Penghasil tambah pertama hanya boleh jadi 1 atau 2, supaya kedua-dua set menghabiskan set asal. Maka F(n+1) = F(n) + F(n−1).

Pembuktian

Kami mengira bilangan cara menjumlahkan 1 dan 2 sehingga n + 1 supaya sekurang-kurangnya salah satu daripada penghasil tambah adalah 2.
Seperti sebelum ini, terdapat F(n + 2) cara menjumlahkan 1 dan 2 menjadi n + 1 apabila n ≥ 0.
Oleh kerana hanya ada satu jumlah n + 1 yang tidak menggunakan 2, iaitu 1 + … + 1 (syarat n + 1),kita tolak 1 dari F(n + 2).
Setara, kita boleh mempertimbangkan sebutan pertama bagi 2 sebagai penghasil tambah.
Jika, dalam jumlah, penghasil tambah yang pertama adalah 2, maka ada F(n) cara untuk melengkapkan pengiraan bagi n − 1.
Jika penghasil tambah yang kedua ialah 2 tetapi yang pertama adalah 1, maka terdapat F(n − 1) cara untuk melengkapkan pengiraan bagi n − 2.
Teruskan dengan cara ini.
Kemudiannya kita mempertimbangkan penghasil tambah ke-(n + 1).
Jika ia adalah 2 tetapi semua penghasil tambahn sebelumnya adalah 1, maka terdapat F(0) cara untuk melengkapkan pengiraan bagi 0.
Jika suatu jumlah mengandungi 2 sebagai penghasil tambah, sebutan pertama bagi penghasil tambah itu mesti berlaku di antara posisi yang pertama dan yang ke-(n + 1).
Maka F(n) + F(n − 1) + … + F(0) memberikan pengiraan yang dikehendaki.

Other identities

Other identities termasuk  hubungan kepada nombor Lucas yang mempunyai same recursive properties but start with L₀=2 and L₁=1. These properties termasuk F₂ₙ=FₙLₙ.
There are also scaling identities, which take you from Fₙ and Fₙ₊₁ to a variety of things of  form Fan+b; sebagai contoh
 oleh identiti Cassini.
These can be found experimentally using lattice pengurangan, and are useful in setting up  special number field sieve to factorize a nombor Fibonacci. Such relations exist in a very general sense for numbers defined by recurrence relations, see  section on multiplication formulae under Perrin numbers for details.

Pembahagi ganjil

Jika n adalah ganjil, semua pembahagi ganjil Fₙ adalah ≡ 1 (mod 4). 

Ini adalah bersamaan dengan mengatakan bahawa untuk n ganjil semua faktor perdana ganjil Fₙ adalah ≡ 1 (mod 4).
Contohnya,
F₁ = 1, F₃ = 2, F₅ = 5, F₇ = 13, F₉ = 34 = 2×17, F₁₁ = 89, F₁₃ = 233, F₁₅ = 610 = 2×5×61

Kebolehbahagian dengan 11

Sebagai contoh, jadi n = 1:

F₁+F₂+...+F₁₀ = 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143 = 11×13
n = 2:

F₂+F₃+...+F₁₁ = 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89 = 231 = 11×21
n = 3:

F₃+F₄+...+F₁₂ = 2 +  3 + 5 + 8 + 13 + 21 + 34 + 55 + 89 + 144= 374 = 11×34
Malah, identitinya adalah benar bagi semua integer n, bukan hanya yang positif:
n = 0:

F₀+F₁+...+F₉ = 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 = 88 = 11×8
n = −1:

F−1+F₀+...+F₈ = 1 + 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 = 55 = 11×5
n = −2:

F−2+F−1+F₀+...+F₇ = −1 + 1 + 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33 = 11×3

Magnitud nombor Fibonacci

Memandangkan adalah berasimptot kepada , bilangan digit dalam asas perwakilan b  adalah berasimptot kepada .
Dalam asas 10, untuk setiap integer yang lebih besar daripada 1 terdapat 4 atau 5 nombor Fibonacci dengan bilangan digit itu, dalam kebanyakan kes 5.

Aplikasi

Nombor Fibonacci are important dalam run-time analysis of algoritma Euclid to determine  greatest common divisor of two integers:  worst case input for this algoritma is a pair of consecutive nombor Fibonacci.
Yuri Matiyasevich dapat menunjukkan bahawa nombor Fibonacci boleh ditakrifkan daripada persamaan Diophantine, which led to his original solution of Hilbert's tenth problem.
Nombor Fibonacci occur dalam sums of "shallow" diagonals in segi tiga Pascal dan segi tiga Lozanić (see "Binomial coefficient"). (They occur more obviously in segi tiga Hosoya).
Setiap integer positif boleh ditulis dalam cara khusus sebagai hasil pertambahan lebih dari satu nombor Fibonacci yang tersendiri di mana hasil pertambahan tersebut tidak termasuk sebarang daripada dua nombor Fibonacci yang berturutan. This is known as Zeckendorf's theorem, and a sum of nombor Fibonacci that satisfies these conditions is called a Zeckendorf representation.
Prinsip dan nombor Fibonacci juga digunakan dalam pasaran perniagaan di mana ia digunakan dalam algoritma, aplikasi dan strategi perdagangan. Some typical forms termasuk:  Fibonacci fan, Fibonacci Arc, Fibonacci Retracement and  Fibonacci Time Extension.
Nombor Fibonacci digunakan by some pseudorandom number generators.
Nombor Fibonacci digunakan in a polyphase version of  merge sort algoritma in which an unsorted list is divided into two lists whose lengths correspond to sequential nombor Fibonacci - by dividing  list so that  two parts mempunyailengths dalam approximate proportion φ. A tape-drive implementation of  polyphase merge sort was described dalam Art of Computer Programming.
nombor Fibonacci arise dalam analysis of  Fibonacci heap data structure.
A one-dimensional optimization method, called  Fibonacci search technique, uses nombor Fibonacci.
Siri nombor Fibonacci series is used for optional lossy compression dalam IFF 8SVX audio file format used on Amiga computers.  number series  compands  original audio wave similar to logarithmic methods e.g. hukum µ.
In muzik, nombor Fibonacci kadangkalanya digunakan to determine tunings, and, as in visual art, to determine  length or size of content or formal elements. It is commonly thought that  first movement of Béla Bartók's Music for Strings, Percussion, and Celesta was structured using nombor Fibonacci.
Memandangkan faktor pertukaran unit batu kepada kilometer iaitu 1.609344 hampir dengan nisbah keemasan (denoted φ),  decomposition of distance in miles into a sum of nombor Fibonacci becomes nearly  kilometer sum apabila nombor Fibonacci are replaced by their successors. This method amounts to a radix 2 number register in asas nisbah keemasan φ being shifted. To convert from kilometers to miles, shift  register down  jujukan Fibonacci instead.

Periodicity mod n: Pisano periods

It is easily seen that if  members of  jujukan Fibonacci are taken mod n,  resulting sequence must be periodic with period at most .   lengths of  periods for various n form  so-called Pisano periods (jujukan A001175 dalam OEIS).  Determining  Pisano periods in general is an open problem, although untuk sebarang particular n it can be solved as an instance of cycle detection.

Lain-lain

Pada tahun 1963, John H. E. Cohn membuktikan segi empat dalam nombor Fibonacci adalah 0, 1, dan 144.
Pada tahun 1990, Jean-claude Perez menerbitkan karya kukuh berkenaan lengkung dunia dan sensitiviti nombor Fibonacci