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.

Pengenalan Pertama

F n + 1 = F n + F n − 1 {\displaystyle F_{n+1}=F_{n}+F_{n-1}} Nombor Fibonacci ke-n adalah jumlah dua nombor Fibonacci sebelumnya.

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).

Pengenalan Kedua

∑ i = 0 n F i = F n + 2 − 1 {\displaystyle \sum _{i=0}^{n}F_{i}=F_{n+2}-1} Jumlah bagi n pertama nombor Fibonacci adalah nombor Fibonacci ke-(n+2) tolak 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.

Pengenalan Ketiga

Identiti ini mempunyai bentuk yang sedikit berbeza untuk F k {\displaystyle F_{k}} , bergantung kepada sama ada k adalah ganjil atau genap.

∑ i = 0 n − 1 F 2 i + 1 = F 2 n {\displaystyle \sum _{i=0}^{n-1}F_{2i+1}=F_{2n}} ∑ i = 0 n F 2 i = F 2 n + 1 − 1 {\displaystyle \sum _{i=0}^{n}F_{2i}=F_{2n+1}-1}

[12]

Jumlah bagi nombor Fibonacci n-1 pertama, F j {\displaystyle F_{j}} , supaya j ganjil adalah nombor Fibonacci ke-(2n).Jumlah bagi nombor Fibonacci n pertama, F j {\displaystyle F_{j}} , supaya j genap adalah nombor Fibonacci ke-(2n+1) tolak 1.

Pembuktian

Aruhan bagi F 2 n {\displaystyle F_{2n}} :

F 1 + F 3 + F 5 + . . . + F 2 n − 3 + F 2 n − 1 = F 2 n {\displaystyle F_{1}+F_{3}+F_{5}+...+F_{2n-3}+F_{2n-1}=F_{2n}} F 1 + F 3 + F 5 + . . . + F 2 n − 3 + F 2 n − 1 + F 2 n + 1 = F 2 n + F 2 n + 1 {\displaystyle F_{1}+F_{3}+F_{5}+...+F_{2n-3}+F_{2n-1}+F_{2n+1}=F_{2n}+F_{2n+1}} F 1 + F 3 + F 5 + . . . + F 2 n − 3 + F 2 n − 1 + F 2 n + 1 = F 2 n + 2 {\displaystyle F_{1}+F_{3}+F_{5}+...+F_{2n-3}+F_{2n-1}+F_{2n+1}=F_{2n+2}}

Kes asas ini untuk boleh menjadi F 1 = F 2 {\displaystyle F_{1}=F_{2}} .
Aruhan bagi F 2 n + 1 {\displaystyle F_{2n+1}} :

F 0 + F 2 + F 4 + . . . + F 2 n − 2 + F 2 n = F 2 n + 1 − 1 {\displaystyle F_{0}+F_{2}+F_{4}+...+F_{2n-2}+F_{2n}=F_{2n+1}-1} F 0 + F 2 + F 4 + . . . + F 2 n − 2 + F 2 n + F 2 n + 2 = F 2 n + 1 + F 2 n + 2 − 1 {\displaystyle F_{0}+F_{2}+F_{4}+...+F_{2n-2}+F_{2n}+F_{2n+2}=F_{2n+1}+F_{2n+2}-1} F 0 + F 2 + F 4 + . . . + F 2 n − 2 + F 2 n + F 2 n + 2 = F 2 n + 3 − 1 {\displaystyle F_{0}+F_{2}+F_{4}+...+F_{2n-2}+F_{2n}+F_{2n+2}=F_{2n+3}-1}

Kes asas ini untuk boleh menjadi F 0 = F 1 − 1 {\displaystyle F_{0}=F_{1}-1} .

Pengenalan Keempat

∑ i = 0 n i F i = n F n + 2 − F n + 3 + 2 {\displaystyle \sum _{i=0}^{n}iF_{i}=nF_{n+2}-F_{n+3}+2}

Pembuktian

Pengenalan ini boleh ditentukan dalam dua peringkat.Pertama, kita mengira bilangan cara menjumlahkan 1 dan 2 menjadi −1, 0, …, atau n + 1 supaya sekurang-kurangnya salah satu daripada penghasil tambah adalah 2.

Dengan pengenalan kedua kita, terdapat F(n + 2) − 1 cara menjumlahkan kepada n + 1; F(n + 1) − 1 cara menjumlahkan kepada n; …; dan, akhirnya, F(2) − 1 cara menjumlahkan kepada 1.Apabila F(1) − 1 = F(0) = 0, kita boleh menambah semua jumlah n + 1 dan menggunakan pengenalan kedua lagi untuk mendapatkan:    [F(n + 2) − 1] + [F(n + 1) − 1] + … + [F(2) − 1]

= [F(n + 2) − 1] + [F(n + 1) − 1] + … + [F(2) − 1] + [F(1) − 1] + F(0)= F(n + 2) + [F(n + 1) + … + F(1) + F(0)] − (n + 2)= F(n + 2) + [F(n + 3) − 1] − (n + 2)= F(n + 2) + F(n + 3) − (n + 3).

Sebaliknya, kita dapati daripada pengenalan kedua bahawa terdapat

• F(0) + F(1) + … + F(n − 1) + F(n) ways summing to n + 1;
• F(0) + F(1) + … + F(n − 1) cara menjumlahkan kepada n;

……

• F(0) cara menjumlahkan kepada −1.

Menambahkan semua jumlah n + 1, kita dapat melihat bahawa terdapat

• (n + 1) F(0) + n F(1) + … + F(n) cara menjumlahkan kepada −1, 0, …, or n + 1.

Memandangkan kedua-dua kaedah pengiraan merujuk kepada nombor yang sama, kita dapat

(n + 1) F(0) + n F(1) + … + F(n) = F(n + 2) + F(n + 3) − (n + 3)

Akhir sekali, kita melengkapkan bukti dengan membuat tolakan pengenalan di atas daripada n + 1 kali pengenalan kedua.

Pengenalan Kelima

∑ i = 0 n F i 2 = F n F n + 1 {\displaystyle \sum _{i=0}^{n}{F_{i}}^{2}=F_{n}F_{n+1}} Jumlah bagi nombor Fibonacci n yang pertama dikuasa dua adalah hasil darab nombor Fibonacci ke-n dan ke-(n+1).

Pengenalan bagi n berganda

F 2 n = F n + 1 2 − F n − 1 2 = F n ( F n + 1 + F n − 1 ) {\displaystyle F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}=F_{n}(F_{n+1}+F_{n-1})}

[13]

Another Identity

Another identity useful untuk mengira Fn memperoleh nilai besar n ialah

F k n + c = ∑ i = 0 k ( k i ) F c − i F n i F n + 1 k − i , {\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c-i}F_{n}^{i}F_{n+1}^{k-i},}

[13]

from which other identities for specific values of k, n, and c can be derived below, including

F 2 n + k = F k F n + 1 2 + 2 F k − 1 F n + 1 F n + F k − 2 F n 2 {\displaystyle F_{2n+k}=F_{k}F_{n+1}^{2}+2F_{k-1}F_{n+1}F_{n}+F_{k-2}F_{n}^{2}}

for all integers n and k. Dijkstra[9] points out that doubling identities of this type can be used to calculate Fn using O(log n) arithmetic operations. Notice that, with definition of nombor Fibonacci with negative n given dalam introduction, this formula reduces to double n formula apabila k = 0.

(From practical standpoint it should be noticed that calculation involves manipulation of numbers with length (number of digits) Θ ( n ) {\displaystyle {\rm {\Theta }}(n)\,} . Thus actual performance depends mainly upon efficiency of implemented long multiplication, and usually is Θ ( n log ⁡ n ) {\displaystyle {\rm {\Theta }}(n\,\log n)} or Θ ( n log 2 ⁡ 3 ) {\displaystyle {\rm {\Theta }}(n^{\log _{2}3})} .)

Other identities

Other identities termasuk hubungan kepada nombor Lucas yang mempunyai same recursive properties but start with L0=2 and L1=1. These properties termasuk F2n=FnLn.

There are also scaling identities, which take you from Fn and Fn+1 to a variety of things of form Fan+b; sebagai contoh

F 3 n = 2 F n 3 + 3 F n F n + 1 F n − 1 = 5 F n 3 + 3 ( − 1 ) n F n {\displaystyle F_{3n}=2F_{n}^{3}+3F_{n}F_{n+1}F_{n-1}=5F_{n}^{3}+3(-1)^{n}F_{n}} oleh identiti Cassini.

F 3 n + 1 = F n + 1 3 + 3 F n + 1 F n 2 − F n 3 {\displaystyle F_{3n+1}=F_{n+1}^{3}+3F_{n+1}F_{n}^{2}-F_{n}^{3}}

F 3 n + 2 = F n + 1 3 + 3 F n + 1 2 F n + F n 3 {\displaystyle F_{3n+2}=F_{n+1}^{3}+3F_{n+1}^{2}F_{n}+F_{n}^{3}}

F 4 n = 4 F n F n + 1 ( F n + 1 2 + 2 F n 2 ) − 3 F n 2 ( F n 2 + 2 F n + 1 2 ) {\displaystyle F_{4n}=4F_{n}F_{n+1}(F_{n+1}^{2}+2F_{n}^{2})-3F_{n}^{2}(F_{n}^{2}+2F_{n+1}^{2})}

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.