Фибоначијев Низ

Име је добио по италијанском математичару Фибоначију. Представља низ бројева у коме збир претходна два броја у низу дају вредност наредног члана низа. Индексирање чланова овог низа почиње од нуле а прва два члана су му 0 и 1.

${\displaystyle F(n):={\begin{cases}0&{\mbox{ако је }}n=0;\\1&{\mbox{ако је }}n=1;\\F(n-1)+F(n-2)&{\mbox{ако је }}n>1.\\\end{cases}}}$

То јест, након две почетне вредности, сваки следећи број је збир два претходника. Први Фибоначијеви бројеви (секвенца A000045 у OEIS), такође означени као F_n, за n = 0, 1, … , су:

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

Понекад се за овај низ сматра да почиње на F₁ = 1, али уобичајеније је укључити F₀ = 0. У неким старијим књигама, вредност ${\displaystyle F_{0}=0}$ је изостављена, тако да секвенца почиње са ${\displaystyle F_{1}=F_{2}=1,}$ и понављање је ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$ валидно за n > 2.

Фибоначијеви бројеви су именовани по Леонарду од Писе, познатом као Фибоначи, иако су раније описани у Индији.

Ако су познати Фибоначијеви бројеви ${\displaystyle F_{m}}$ и ${\displaystyle F_{n}}$ онда се може наћи број ${\displaystyle F_{m+n}}$ по формули

${\displaystyle F_{m+n}=F_{(m-1)}F_{n}+F_{m}F_{n+1}}$

Такође важи

${\displaystyle F_{2n}=F_{n}(F_{n+1}+F_{n-1})}$

${\displaystyle F_{3n}=F_{n+1}^{3}+F_{n}^{3}+F_{n-1}^{3}}$

Уопштено

${\displaystyle F_{mn}=\textstyle \sum _{k=1}^{m}{{\binom {m}{k}}(F_{n}^{k}(F_{n-1}^{m-k}}}$

Фибоначијеви бројеви су у снажној вези са златним пресеком: Бинетова формула изражава n-ти Фибоначијев број у смислу n и златног пресека, и подразумева да однос два узастопна Фибоначијева броја тежи златном пресеку како се n повећава.

Фибоначијеви бројеви су добили име по италијанском математичару Леонарду из Пизе, касније познатом као Леонардо Фибоначи. У својој књизи Liber Abaci из 1202. године, Фибоначи је представио овај низ западноевропској математици, иако је тај низ био описан раније у индијској математици, већ 200. године пре нове ере у раду аутора Пингала о набрајању могућих образаца санскртске поезије насталих од слогова две дужине.

Бинетова формула је експлицитно изражавање вредности ${\displaystyle F_{n}}$  као функције од ${\displaystyle n}$ 

${\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}},}$ 

где је ${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$  златни пресек. У том случају ${\displaystyle \varphi }$  и ${\displaystyle (-\varphi )^{-1}=1-\varphi }$  су решења једначине ${\displaystyle x^{2}-x-1=0}$ .

Из Бинетове формуле за све ${\displaystyle n\geqslant 0}$ , следи да је ${\displaystyle F_{n}}$  за ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$  најближе целом броју тј. ${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil }$ 

За ${\displaystyle n\to \infty }$  је ${\displaystyle F_{n}\sim {\frac {\varphi ^{n}}{\sqrt {5}}}}$ .

Формула се може аналитички приказати на следећи начин

${\displaystyle F_{z}={\frac {1}{\sqrt {5}}}\left(\varphi ^{z}-{\frac {\cos {\pi z}}{\varphi ^{z}}}\right).}$ 

при томе ${\displaystyle F_{z+2}=F_{z+1}+F_{z}}$  вреди за сваки комплексни број

У теорији бројева велику улогу игра број ${\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}}$  који је корен једначине ${\displaystyle x^{2}-x-1=0}$  i

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

Из Бинетове формуле

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

Где је

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

${\displaystyle \varphi ^{-1}={\frac {1-{\sqrt {5}}}{2}}=1-\varphi =-{1 \over \varphi }\approx -0.61803\,39887\cdots }$ 

Даље се добија

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

и

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

За све вредности a, b дефинише се низ

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

Задовољена је и релација

${\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}}$ 

Нека су ${\displaystyle a}$  и ${\displaystyle b}$  изабрани тако да је ${\displaystyle U_{0}=0}$  и ${\displaystyle U_{1}=1}$  онда добијени низ мора бити Фибоначијев низ.

Бројеви ${\displaystyle a}$  и ${\displaystyle b}$  задовољавају релацију

${\displaystyle a+b=0}$ 

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

Односно важи

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

Узимајући ${\displaystyle U_{0}}$  i ${\displaystyle U_{1}}$  као почетне варијабле добија се

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

Односно

${\displaystyle a={\frac {U_{1}-U_{0}\varphi ^{-1}}{\sqrt {5}}}}$ 
${\displaystyle b={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}}$ .

Посматрајмо сада

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

За ${\displaystyle n\geq 0}$ , broj ${\displaystyle F_{n}}$  најближи цео број је ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$ , који се може добити из функције

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

или

${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor ,\ n\geq 0.}$ 

Слично ако је F>0 Фибоничијев број онда може одредити његов индекс унутар низа.

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

где се ${\displaystyle \log _{\varphi }(x)}$  може израчунати кориштењем логаритма друге базе

Пример

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

Највећи заједнички делитељ два Фибоначијева броја је број чији је индекс једнак највећем заједничком делитељу њихових индекса

Последице

${\displaystyle F_{m}}$  је дјељив сa ${\displaystyle F_{n}}$  ако и само ако је ${\displaystyle m}$  дељиво са ${\displaystyle n}$  (без ${\displaystyle n=2}$ )

• ${\displaystyle F_{m}}$  је дељиво са ${\displaystyle F_{3}=2}$  само ако је ${\displaystyle m=3k}$ 
• ${\displaystyle F_{m}}$  је дељиво са ${\displaystyle F_{4}=3}$  само ако је ${\displaystyle m=4k}$ 
• ${\displaystyle F_{m}}$  је дељиво са ${\displaystyle F_{5}=5}$  само ако је ${\displaystyle m=5k}$ 

${\displaystyle F_{m}}$  је прост ако је ${\displaystyle m}$  прост број са искључењем ${\displaystyle m=4}$ 

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

Обратно не важи тј ако је ${\displaystyle m}$  прост број ${\displaystyle F_{m}}$  не мора бити прост

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

Његов полином ${\displaystyle x^{2}-x-1}$  има корене ${\displaystyle \varphi }$  и ${\displaystyle -\varphi ^{-1}}$ 

${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}$ 

Године 1964, Коши је доказао да су у низу Фибоначијевих бројева једини квадрати бројеви са индексом 0,,1,2,12 ${\displaystyle F_{0}=0^{2}=0}$ , ${\displaystyle F_{1}=1^{2}=1}$ , ${\displaystyle F_{2}=1^{2}=1}$ , ${\displaystyle F_{12}=12^{2}=144}$ 

Генерирајућа функција низа фибоначијевих бројева је ${\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}}}}$ 

Првих 21 Фибоначијевих бројева ${\displaystyle F_{n}}$  за ${\displaystyle n=0,1,2,3,....20}$ 

Овај низ бројева може се проширити и на негативне бројеве.

${\displaystyle F_{n-2}=F_{n}-F_{n-1},}$ 

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

Низ бројева ${\displaystyle F_{n}}$  за ${\displaystyle n=-8,-7,....0,1,2,....8}$ 

• ${\displaystyle F_{1}+F_{2}+F_{3}+\dots +F_{n}=F_{n+2}-1}$ 
• ${\displaystyle F_{1}+F_{3}+F_{5}+\dots +F_{2n-1}=F_{2n}}$ 
• ${\displaystyle F_{2}+F_{4}+F_{6}+\dots +F_{2n}=F_{2n+1}-1}$ 
• ${\displaystyle F_{n+1}F_{n+2}^{}-F_{n}F_{n+3}=(-1)^{n}}$ 
• ${\displaystyle F_{1}^{2}+F_{2}^{2}+F_{3}^{2}+\dots +F_{n}^{2}=F_{n}F_{n+1}}$  (см. рис.)
• ${\displaystyle F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}}$ 
• ${\displaystyle F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}}$ 
• ${\displaystyle F_{3n}=F_{n+1}^{3}+F_{n}^{3}-F_{n-1}^{3}}$ 
• ${\displaystyle F_{5n}=25F_{n}^{5}+25(-1)^{n}F_{n}^{3}+5F_{n}}$ 

Опште формуле

• ${\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}}$ 
• ${\displaystyle F_{(k+1)n}^{}=F_{n-1}F_{kn}+F_{n}F_{kn+1}}$ 
• ${\displaystyle F_{n}^{}=F_{l}F_{n-l+1}+F_{l-1}F_{n-l}}$ 

${\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}}}$ , као и ${\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}}}$ ,

где матрице имају облик ${\displaystyle n\times n}$ , i је имагинарна јединица.

• Фибоначијеви бројеви се могу изразити преко Чебишевљевих полинома

${\displaystyle F_{n+1}=(-i)^{n}U_{n}\left({\frac {-i}{2}}\right),}$ 
${\displaystyle F_{2n+2}=U_{n}\left({\frac {3}{2}}\right).}$ 

За било који ${\displaystyle n}$ 

${\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.}$ 

Последица

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

Формула за поновно добијање Фибоначијевих бројева је

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

Фибоначијев низ се често повезује и са бројем фи (phi), или бројем којег многи зову и „Божанским односом”. Ако се узме један део Фибоначијевог низа, 2, 3, 5, 8, те подели сваки следећи број с њему претходним, добиће се увек број приближан броју 1,618(2/3=1,5; 3/5=1,66; 5/8=1,6). Број 1,618 јесте број фи. Односи мера код биљака, животиња и људи, са запањујућом прецизношћу се приближава броју фи.

Следи неколико примера броја фи и његове повезаности са Фибоначијем и природом:

1. У пчелињој заједници, кошници, увек је мањи број мужјака пчела него женки пчела. Када би поделили број женки са бројем мужјака пчела, увек би добили број фи.
2. Наутилус (главоножац), у својој конструкцији има спирале. Када би се израчунао однос сваког спиралног пречника према следећем добио би се број фи.
3. Семе сунцокрета расте у супротним спиралама. Међусобни односи пречника ротације је број фи.
4. Ако се измери човечија дужину од врха главе до пода, затим се то подели с дужином од пупка до пода, добија се број фи.

• Фибоначијеви полиноми