Fibonaccijev broj (original) (raw)

S Wikipedije, slobodne enciklopedije

Popločanje s kvadratima čije su stranice po dužini sukcesivni Fibonaccijevi brojevi

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 _F_1 = 1, ali uobičajenije je uključiti _F_0 = 0.

Fibonaccijevi brojevi su imenovani po Leonardu od Pise, poznatom kao Fibonacci, iako su ranije opisani u Indiji.[1][2]

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}}}

Binetova formula je eksplicitno izražavanje vrijednosti F n {\displaystyle F_{n}} kao funkcije od n {\displaystyle n}

F n = ( 1 + 5 2 ) n − ( 1 − 5 2 ) n 5 = φ n − ( − φ ) − n φ − ( − φ ) − 1 = φ n − ( − φ ) − n 2 φ − 1 , {\displaystyle F_{n}={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\varphi -(-\varphi )^{-1}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}},}

gdje je φ = 1 + 5 2 {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}} zlatni presjek. U tom slučaju φ {\displaystyle \varphi } и ( − φ ) − 1 = 1 − φ {\displaystyle (-\varphi )^{-1}=1-\varphi } su rješenja jednačine x 2 − x − 1 = 0 {\displaystyle x^{2}-x-1=0} .

Iz Binetove formule za sve n ⩾ 0 {\displaystyle n\geqslant 0} , slijedi da je F n {\displaystyle F_{n}} za φ n 5 {\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}} najbliže cijelom broju tj. F n = ⌊ φ n 5 ⌉ {\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil }

Za n → ∞ {\displaystyle n\to \infty } je F n ∼ φ n 5 {\displaystyle F_{n}\sim {\frac {\varphi ^{n}}{\sqrt {5}}}} .

Formula se može analitiči prikazati na sljedeći način

F z = 1 5 ( φ z − cos ⁡ π z φ z ) . {\displaystyle F_{z}={\frac {1}{\sqrt {5}}}\left(\varphi ^{z}-{\frac {\cos {\pi z}}{\varphi ^{z}}}\right).}

pri tome F z + 2 = F z + 1 + F z {\displaystyle F_{z+2}=F_{z+1}+F_{z}} vrijedi za svaki kompleksni broj

U teoriji brojeva veliku ulogu igra broj ϕ = 1 + 5 2 {\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}} koji je korjen jednačine x 2 − x − 1 = 0 {\displaystyle x^{2}-x-1=0} i

x n − x n − 1 + x n − 2 = 0 {\displaystyle x^{n}-x^{n-1}+x^{n-2}=0}

Iz Binetove formule

1 5 ( ϕ n − ( − ϕ ) − n ) = φ n − ( − φ ) − n 2 φ − 1 {\displaystyle {\frac {1}{\sqrt {5}}}(\phi ^{n}-(-\phi )^{-n})={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}}}

Gdje je

φ = 1 + 5 2 ≈ 1.61803 39887 ⋯ {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\,39887\cdots }

φ − 1 = 1 − 5 2 = 1 − φ = − 1 φ ≈ − 0.61803 39887 ⋯ {\displaystyle \varphi ^{-1}={\frac {1-{\sqrt {5}}}{2}}=1-\varphi =-{1 \over \varphi }\approx -0.61803\,39887\cdots }

Dalje imamo

φ n = φ n − 1 + φ n − 2 {\displaystyle \varphi ^{n}=\varphi ^{n-1}+\varphi ^{n-2}}

i

( φ − 1 ) n = ( φ − 1 ) n − 1 + ( φ − 1 ) n − 2 {\displaystyle (\varphi ^{-1})^{n}=(\varphi ^{-1})^{n-1}+(\varphi ^{-1})^{n-2}}

Za sve vrijednosti a , b definišimo niz

U n = a φ n + b ( φ − 1 ) n {\displaystyle U_{n}=a\varphi ^{n}+b(\varphi ^{-1})^{n}}

Zadovoljena je i relaciija

U n = a φ n − 1 + b ( φ − 1 ) n − 1 + a φ n − 2 + b ( φ − 1 ) n − 2 = U n − 1 + U n − 2 {\displaystyle U_{n}=a\varphi ^{n-1}+b(\varphi ^{-1})^{n-1}+a\varphi ^{n-2}+b(\varphi ^{-1})^{n-2}=U_{n-1}+U_{n-2}}

Neka su a {\displaystyle a} i b {\displaystyle b} izabrani tako da je U 0 = 0 {\displaystyle U_{0}=0} i U 1 = 1 {\displaystyle U_{1}=1} onda dobijeni niz mora biti Fibonaccijev niz.

Brojevi a {\displaystyle a} i b {\displaystyle b} zafovoljavaju relaciju

a + b = 0 {\displaystyle a+b=0}

a φ n + b ( φ − 1 ) n = 1 {\displaystyle a\varphi ^{n}+b(\varphi ^{-1})^{n}=1}

Odnosno imamo

a = 1 φ − φ − 1 = 1 5 , b = − a {\displaystyle a={\frac {1}{\varphi -\varphi ^{-1}}}={\frac {1}{\sqrt {5}}},\,b=-a}

Uzimajući U 0 {\displaystyle U_{0}} i U 1 {\displaystyle U_{1}} kao početne varijable imamo

U n = a φ n + b ( φ − 1 ) n = 1 {\displaystyle U_{n}=a\varphi ^{n}+b(\varphi ^{-1})^{n}=1}

Odnosno

a = U 1 − U 0 φ − 1 5 {\displaystyle a={\frac {U_{1}-U_{0}\varphi ^{-1}}{\sqrt {5}}}}

b = U 0 φ − U 1 5 {\displaystyle b={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}} .

Posmatrajmo sada

| ( φ − 1 ) n 5 | < 1 2 {\displaystyle \left|{\frac {(\varphi ^{-1})^{n}}{\sqrt {5}}}\right|<{\frac {1}{2}}}

Za n ≥ 0 {\displaystyle n\geq 0} , broj F n {\displaystyle F_{n}} najbliži cio broj je φ n 5 {\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}} , koji se može dobiti iz funkcije

F n = [ φ n 5 ] , n ≥ 0 , {\displaystyle F_{n}=\left[{\frac {\varphi ^{n}}{\sqrt {5}}}\right],\ n\geq 0,}

ili

F n = ⌊ φ n 5 + 1 2 ⌋ , n ≥ 0. {\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor ,\ n\geq 0.}

Slično ako je F>0 Fiboniccijev broj onda možemo odrediti njegov indeks unutar niza.

n ( F ) = ⌊ log φ ⁡ ( F ⋅ 5 + 1 2 ) ⌋ , {\displaystyle n(F)={\bigg \lfloor }\log _{\varphi }\left(F\cdot {\sqrt {5}}+{\frac {1}{2}}\right){\bigg \rfloor },}

gdje se log φ ⁡ ( x ) {\displaystyle \log _{\varphi }(x)} može izračunati korištenjem logaritma druge baze

Primjer

log φ ⁡ ( x ) = ln ⁡ ( x ) / ln ⁡ ( φ ) = log 10 ⁡ ( x ) / log 10 ⁡ ( φ ) {\displaystyle \log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )}

Najveći zajednički djelitelj dva Fibonaccijeva broja je broj čiji je indeks jednak najvećem zajedničkom delitelju njihovih indeksa

Posljedice

F m {\displaystyle F_{m}} je djeljiv sa F n {\displaystyle F_{n}} ako i samo ako je m {\displaystyle m} djeljivo sa n {\displaystyle n} ( bez n = 2 {\displaystyle n=2} )

F m {\displaystyle F_{m}} je prost ako je m {\displaystyle m} prost broj sa isključenjem m = 4 {\displaystyle m=4}

F 13 = 233 {\displaystyle F_{13}=233}

Obratno ne važi tj ako je m {\displaystyle m} prost broj F m {\displaystyle F_{m}} ne mora biti prost

F 19 = 4181 = 37 ∗ 113 {\displaystyle F{19}=4181=37*113}

Njegov polinom x 2 − x − 1 {\displaystyle x^{2}-x-1} ima korjene φ {\displaystyle \varphi } i − φ − 1 {\displaystyle -\varphi ^{-1}}

lim n → ∞ F n + 1 F n = φ . {\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}

1964 godine Cochn je dokazao da su u nizu Fibonaccijevih brojeva jedini kvadrati brojevi sa indeksom 0,,1,2,12 F 0 = 0 2 = 0 {\displaystyle F_{0}=0^{2}=0} , F 1 = 1 2 = 1 {\displaystyle F_{1}=1^{2}=1} , F 2 = 1 2 = 1 {\displaystyle F_{2}=1^{2}=1} , F 12 = 12 2 = 144 {\displaystyle F_{12}=12^{2}=144}

Generirajuća funkcija niza fibonaccijevih brojeva je x + x 2 + 2 x 3 + 3 x 4 + 5 x 5 + ⋯ = ∑ n = 0 ∞ F n x n = x 1 − x − x 2 {\displaystyle x+x^{2}+2x^{3}+3x^{4}+5x^{5}+\dots =\sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}}}

Prvih 21 Fibonaccijevih brojeva F n {\displaystyle F_{n}} za n = 0 , 1 , 2 , 3 , . . . .20 {\displaystyle n=0,1,2,3,....20} [3]

Ovaj niz brojeva može se proširiti i na negativne brojeve.

F n − 2 = F n − F n − 1 , {\displaystyle F_{n-2}=F_{n}-F_{n-1},}

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

Niz brojeva F n {\displaystyle F_{n}} za n = − 8 , − 7 , . . . .0 , 1 , 2 , . . . .8 {\displaystyle n=-8,-7,....0,1,2,....8} [4]

• F 1 + F 2 + F 3 + ⋯ + F n = F n + 2 − 1 {\displaystyle F_{1}+F_{2}+F_{3}+\dots +F_{n}=F_{n+2}-1}
• F 1 + F 3 + F 5 + ⋯ + F 2 n − 1 = F 2 n {\displaystyle F_{1}+F_{3}+F_{5}+\dots +F_{2n-1}=F_{2n}}
• F 2 + F 4 + F 6 + ⋯ + F 2 n = F 2 n + 1 − 1 {\displaystyle F_{2}+F_{4}+F_{6}+\dots +F_{2n}=F_{2n+1}-1}
• F n + 1 F n + 2 − F n F n + 3 = ( − 1 ) n {\displaystyle F_{n+1}F_{n+2}^{}-F_{n}F_{n+3}=(-1)^{n}}
• F 1 2 + F 2 2 + F 3 2 + ⋯ + F n 2 = F n F n + 1 {\displaystyle F_{1}^{2}+F_{2}^{2}+F_{3}^{2}+\dots +F_{n}^{2}=F_{n}F_{n+1}} (см. рис.)
• F n 2 + F n + 1 2 = F 2 n + 1 {\displaystyle F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}}
• F 2 n = F n + 1 2 − F n − 1 2 {\displaystyle F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}}
• 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}}
• F 5 n = 25 F n 5 + 25 ( − 1 ) n F n 3 + 5 F n {\displaystyle F_{5n}=25F_{n}^{5}+25(-1)^{n}F_{n}^{3}+5F_{n}}

Opšte formule

• F n + m = F n − 1 F m + F n F m + 1 = F n + 1 F m + 1 − F n − 1 F m − 1 {\displaystyle F_{n+m}^{}=F_{n-1}F_{m}+F_{n}F_{m+1}=F_{n+1}F_{m+1}-F_{n-1}F_{m-1}}
• F ( k + 1 ) n = F n − 1 F k n + F n F k n + 1 {\displaystyle F_{(k+1)n}^{}=F_{n-1}F_{kn}+F_{n}F_{kn+1}}
• F n = F l F n − l + 1 + F l − 1 F n − l {\displaystyle F_{n}^{}=F_{l}F_{n-l+1}+F_{l-1}F_{n-l}}

F n + 1 = det ( 1 1 0 ⋯ 0 − 1 1 1 ⋱ ⋮ 0 − 1 ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ 1 0 ⋯ 0 − 1 1 ) {\displaystyle F_{n+1}=\det {\begin{pmatrix}1&1&0&\cdots &0\\-1&1&1&\ddots &\vdots \\0&-1&\ddots &\ddots &0\\\vdots &\ddots &\ddots &\ddots &1\\0&\cdots &0&-1&1\end{pmatrix}}} , kao i F n + 1 = det ( 1 i 0 ⋯ 0 i 1 i ⋱ ⋮ 0 i ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ i 0 ⋯ 0 i 1 ) {\displaystyle \ F_{n+1}=\det {\begin{pmatrix}1&i&0&\cdots &0\\i&1&i&\ddots &\vdots \\0&i&\ddots &\ddots &0\\\vdots &\ddots &\ddots &\ddots &i\\0&\cdots &0&i&1\end{pmatrix}}} ,

gdje matrice imaju oblik n × n {\displaystyle n\times n} , i je imaginarna jedinica.

• Fibonaccijeve brojeve možemo izraziti preko Chebyshevih polinoma

F n + 1 = ( − i ) n U n ( − i 2 ) , {\displaystyle F_{n+1}=(-i)^{n}U_{n}\left({\frac {-i}{2}}\right),}

F 2 n + 2 = U n ( 3 2 ) . {\displaystyle F_{2n+2}=U_{n}\left({\frac {3}{2}}\right).}

Za bilo koji n {\displaystyle n}

( 1 1 1 0 ) n = ( F n + 1 F n F n F n − 1 ) . {\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.}

Posljedica

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

Formula za ponovno dobijanje Fibonaccijevih brojeva je

F n + 1 = F n + 5 F n 2 ± 4 2 {\displaystyle F_{n+1}={\frac {F_{n}+{\sqrt {5F_{n}^{2}\pm 4}}}{2}}}

Fibonaccijev niz se često povezuje i sa brojem fi (phi), ili brojem kojeg mnogi zovu i "Božanskim omjerom". Uzmemo li jedan dio Fibonaccijevog niza, 2, 3, 5, 8, te podijelimo li svaki sljedeći broj s njemu prethodnim, dobit ćemo uvijek broj približan broju 1,618(2/3=1,5; 3/5=1,66; 5/8=1,6). Broj 1,618 jeste broj fi. Odnosi mjera kod biljaka, životinja i ljudi, sa zapanjujućom preciznošću se približava broju fi.

Slijedi nekoliko primjera broja fi i njegove povezanosti sa Fibonaccijem i prirodom:

1. U pčelinjoj zajednici, košnici, uvijek je manji broj mužjaka pčela nego ženki pčela. Kada bi podijelili broj ženki sa brojem mužjaka pčela, uvijek bi dobili broj fi.
2. Nautilus (glavonožac), u svojoj konstrukciji ima spirale. Kada bi izračunali odnos svakog spiralnog promjera prema sljedećem dobili bi broj fi.
3. Sjeme suncokreta raste u suprotnim spiralama. Međusobni odnosi promjera rotacije je broj fi.
4. Izmjerimo li čovječju dužinu od vrha glave do poda, zatim to podijelimo s dužinom od pupka do poda, dobijamo broj fi.

• Fibonaccijevi polinomi

1. ↑ Parmanand Singh. Acharya Hemachandra and the (so called) Fibonacci Numbers. Math . Ed. Siwan , 20(1):28-30,1986.ISSN 0047-6269]
2. ↑ Parmanand Singh,"The So-called Fibonacci numbers in ancient and medieval India. Historia Mathematica v12 n3, 229–244,1985
3. ↑ The Fibonacci series Arhivirano 14. 3. 2018. na Wayback Machine: 03. april 2011.
4. ↑ Negafibonacci Numbers and the Hyperbolic Plane Arhivirano 1. 2. 2018. na Wayback Machine

Nedovršeni članak Fibonaccijev broj koji govori o matematici treba dopuniti. Dopunite ga prema pravilima Wikipedije.