Fibonaccijev broj
U matematici, Fibonaccijevi brojevi oblikuju niz definisan sljedećom rekurzivnom relacijom: F ( n ) := { 0 ako je  n = 0 ; 1 ako je  n = 1 ; F ( n − 1 ) + F ( n − 2 ) ako je  n > 1. {\displaystyle F(n):={\begin{cases}0&{\mbox{ako je }}n=0;\\1&{\mbox{ako je }}n=1;\\F(n-1)+F(n-2)&{\mbox{ako je }}n>1.\\\end{cases}}} To jest, nakon dvije početne vrijedosti, svaki sljedeći broj je zbroj dvaju prethodnika. Prvi Fibonaccijevi brojevi (niz A000045 u OEIS) , također označeni kao Fn, za n = 0, 1, … , su: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514299, 832040... Ponekad se za ovaj niz smatra da počinje na F1 = 1, ali uobičajenije je uključiti F0 = 0. Fibonaccijevi brojevi su imenovani po Leonardu od Pise, poznatom kao Fibonacci, iako su ranije opisani u Indiji. Ako znamo Fibonaccijeve brojeve F m {\displaystyle F_{m}} i F n {\displaystyle F_{n}} onda možemo naći broj F m + n {\displaystyle F_{m+n}} po formuli F m + n = F ( m − 1 ) F n + F m F n + 1 {\displaystyle F_{m+n}=F_{(m-1)}F_{n}+F_{m}F_{n+1}} Također imamo F 2 n = F n ( F n + 1 + F n − 1 ) {\displaystyle F_{2n}=F_{n}(F_{n+1}+F_{n-1})} F 3 n = F n + 1 3 + F n 3 + F n − 1 3 {\displaystyle F_{3n}=F_{n+1}^{3}+F_{n}^{3}+F_{n-1}^{3}} Uopšteno F m n = ∑ k = 1 m ( m k ) ( F n k ( F n − 1 m − k {\displaystyle F_{mn}=\textstyle \sum _{k=1}^{m}{{\binom {m}{k}}(F_{n}^{k}(F_{n-1}^{m-k}}}