Fibonacci sequence

Tile pattern made of squares, the edge lengths of which correspond to the Fibonacci sequence

The Fibonacci sequence is the infinite sequence of natural numbers that (originally) begins with twice the number 1 or (often, in modern notation) is additionally provided with a leading number 0. Then the sum of two consecutive numbers results in the following number:

The numbers it contains are called Fibonacci numbers. The series is named after Leonardo Fibonacci , who used it to describe the growth of a rabbit population in 1202. The result was already known to both the Greeks and the Indians in ancient times .

Further research showed that the Fibonacci sequence also describes numerous other growth processes in nature . It seems like some kind of growth pattern in nature.

The Fibonacci numbers have some notable mathematical peculiarities:

• Because of the relationship to the previous and the following number , growth in nature seems to follow a law of addition.
• The Fibonacci sequence is directly related to the golden ratio . The further you progress in the sequence, the closer the quotient of consecutive numbers approaches the golden ratio (1.618033 ...) (for example 13: 8 = 1.6250; 21:13 ≈ 1.6154; 34:21 ≈ 1, 6190; 55:34 ≈ 1.6176; etc.).
• This approach is alternating; H. the quotients are alternately smaller and larger than the golden ratio.

Definition of the Fibonacci sequence

The first members of the Fibonacci sequence

The Fibonacci sequence is due to the recursive law of formation ${\displaystyle f_{1},\,f_{2},\,f_{3},\ldots }$

${\displaystyle f_{n}=f_{n-1}+f_{n-2}}$   For   ${\displaystyle n\geq 3}$

with the initial values

${\displaystyle f_{1}=f_{2}=1}$

Are defined. That means in words:

• The value is given for the first two numbers . ${\displaystyle 1}$
• Each additional number is the sum of its two predecessors in the sequence.

This results in:

n	f n	n	f n	n	f n	n	f n	n	f n
1	1	11	89	21st	10 946	31	1,346,269	41	165 580 141
2	1	12	144	22nd	17 711	32	2 178 309	42	267 914 296
3	2	13	233	23	28 657	33	3,524,578	43	433 494 437
4th	3	14th	377	24	46 368	34	5,702,887	44	701 408 733
5	5	15th	610	25th	75 025	35	9 227 465	45	1 134 903 170
6th	8th	16	987	26th	121 393	36	14 930 352	46	1 836 311 903
7th	13	17th	1,597	27	196 418	37	24 157 817	47	2 971 215 073
8th	21st	18th	2 584	28	317 811	38	39 088 169	48	4 807 526 976
9	34	19th	4 181	29	514 229	39	63 245 986	49	7 778 742 049
10	55	20th	6 765	30th	832 040	40	102 334 155	50	12 586 269 025

From the requirement that the recursion

${\displaystyle f_{n}=f_{n-1}+f_{n-2}}$

should also apply to whole numbers , you get a clear continuation to the index 0 and negative indices. The following applies: ${\displaystyle n\leq 2}$

${\displaystyle f_{0}=0}$

${\displaystyle f_{-n}=(-1)^{n+1}f_{n}}$ for all ${\displaystyle n>0}$

The expanded Fibonacci sequence then reads

${\displaystyle f_{-7}}$

${\displaystyle f_{-6}}$

${\displaystyle f_{-5}}$

${\displaystyle f_{-4}}$

${\displaystyle f_{-3}}$

${\displaystyle f_{-2}}$

${\displaystyle f_{-1}}$

${\displaystyle f_{0}}$

${\displaystyle f_{1}}$

${\displaystyle f_{2}}$

${\displaystyle f_{3}}$

${\displaystyle f_{4}}$

${\displaystyle f_{5}}$

${\displaystyle f_{6}}$

${\displaystyle f_{7}}$

${\displaystyle \dotsb }$

13

−8

5

−3

2

−1

1

0

1

1

2

3

5

8th

13

${\displaystyle \dotsb }$

and is called the sequence of negaFibonacci numbers.

In addition, the Fibonacci numbers can be generalized to complex numbers , per- finite numbers and to vector spaces .

properties

One of the many remarkable properties of the Fibonacci numbers is that they obey Benford's law .

Relationship to the golden ratio

As noted by Johannes Kepler , the quotient of two consecutive Fibonacci numbers approaches the golden ratio . This follows directly from the approximation formula for large : ${\displaystyle \Phi }$ ${\displaystyle n}$

${\displaystyle \lim _{n\to \infty }{\frac {f_{n+1}}{f_{n}}}=\lim _{n\to \infty }{\Phi ^{n+1} \over \Phi ^{n}}=\Phi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}6180339887}$

These quotients of two consecutive Fibonacci numbers have a remarkable continued fraction representation :

${\displaystyle {\frac {1}{1}}=1\qquad {\frac {2}{1}}=1+{\frac {1}{1}}=[1;1]\qquad {\frac {3}{2}}=1+{\frac {1}{1+{\frac {1}{1}}}}=[1;1,1]\qquad {\frac {5}{3}}=1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1}}}}}}=[1;1,1,1]}$

with the -notation from finite continued fractions . ${\displaystyle [\,;\,]}$

Since these quotients converge towards the golden section in the limit value, this can be described as the infinite periodic continued fraction:

${\displaystyle \Phi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{\;\,\ddots }}}}}}}}=[1;{\overline {1}}]}$

represent. The number is irrational . This means that it cannot be represented by a ratio of two whole numbers. The best way to approximate is to use the quotient of two consecutive Fibonacci numbers. This also applies to generalized Fibonacci sequences for which and assume any natural numbers. ${\displaystyle \Phi }$ ${\displaystyle \Phi }$ ${\displaystyle f_{0}}$ ${\displaystyle f_{1}}$

Relationships between the members of the sequence

Identities :

• ${\displaystyle f_{m+n}=f_{n+1}\;f_{m}+f_{n}\;f_{m-1}}$
• ${\displaystyle f_{m+n}=f_{n}\;L_{m}+(-1)^{m+1}\;f_{n-m}}$with the Lucas sequence (with ), in particular: ${\displaystyle L_{m}=f_{m+1}+\;f_{m-1}=\Phi ^{m}+\Psi ^{m}}$ ${\displaystyle \Psi :=1-\Phi }$
• ${\displaystyle f_{2n}=f_{n}\;L_{n}=f_{n}\;(f_{n+1}+f_{n-1})}$
• ${\displaystyle f_{2n+1}=f_{n}^{2}+f_{n+1}^{2}}$
• ${\displaystyle f_{n}^{2}-f_{n+k}\;f_{n-k}=(-1)^{n-k}f_{k}^{2}}$(Identity of Catalan )
• ${\displaystyle f_{n+1}\;f_{n-1}-f_{n}^{2}=(-1)^{n}}$(Identity of Cassini , special case of the Catalan identity)
• ${\displaystyle f_{m}\;f_{n+1}-f_{n}\;f_{m+1}=(-1)^{n}f_{m-n}}$(Identity of d'Ocagne )

Divisibility :

• ${\displaystyle \operatorname {ggT} (f_{m},f_{n})=f_{\operatorname {ggT} (m,n)}}$
• Any two neighboring Fibonacci numbers are relatively prime, i.e. H. . ${\displaystyle \operatorname {ggT} (f_{n},f_{n+1})=1}$
• ${\displaystyle m\mid n\Rightarrow f_{m}\mid f_{n}}$; for the converse also applies. In particular, for can only be a prime if is a prime number. ${\displaystyle m>2}$ ${\displaystyle f_{n}}$ ${\displaystyle n>4}$ ${\displaystyle n}$
• ${\displaystyle 2\mid f_{n}\Leftrightarrow 3\mid n}$ (Exactly every third Fibonacci number is divisible by 2.)
• ${\displaystyle 3\mid f_{n}\Leftrightarrow 4\mid n}$ (Exactly every fourth Fibonacci number is divisible by 3.)
• ${\displaystyle 4\mid f_{n}\Leftrightarrow 6\mid n}$ (Exactly every sixth Fibonacci number is divisible by 4.)
• ${\displaystyle 5\mid f_{n}\Leftrightarrow 5\mid n}$ (Exactly every fifth Fibonacci number is divisible by 5.)
• ${\displaystyle 7\mid f_{n}\Leftrightarrow 8\mid n}$ (Exactly every eighth Fibonacci number is divisible by 7.)
• ${\displaystyle 16\mid f_{n}\Leftrightarrow 12\mid n}$ (Exactly every twelfth Fibonacci number is divisible by 16.)

The following applies to divisibility by prime numbers using the Jacobi symbol : ${\displaystyle p}$

• ${\displaystyle p\mid f_{p-1}\Leftrightarrow \left({\frac {5}{p}}\right)=1}$
• ${\displaystyle p\mid f_{p+1}\Leftrightarrow \left({\frac {5}{p}}\right)=-1}$

Rows :

• ${\displaystyle \sum _{i=0}^{n}f_{i}=f_{n+2}-1}$
• ${\displaystyle \sum _{i=1}^{2n}(-1)^{i-1}\;f_{i}=-f_{2n-1}+1}$
• ${\displaystyle \sum _{i=1}^{2n+1}(-1)^{i-1}\;f_{i}=f_{2n}+1}$
• ${\displaystyle \sum _{i=1}^{n}f_{i}^{2}=f_{n}\;f_{n+1}}$
• ${\displaystyle \sum _{i=1}^{n}f_{2i-1}=f_{2n}}$
• ${\displaystyle \sum _{i=1}^{n}f_{2i}=f_{2n+1}-1}$

There are numerous other such formulas.

Reciprocal series

The limit of the absolutely converging reciprocal series of Fibonacci numbers

• ${\displaystyle {\sqrt {5}}<\sum _{i=1}^{\infty }{\frac {1}{f_{i}}}<{\sqrt {5}}{\frac {\Phi }{\Phi -1}}}$

is irrational (André-Jeannin; 1989).

In addition, Good (1974) and Hoggatt (1976) showed:

• ${\displaystyle \sum _{n=0}^{\infty }{\frac {1}{f_{2^{n}}}}={\frac {7-{\sqrt {5}}}{2}}}$.

Zeckendorf theorem

→ Main article : Zeckendorf's theorem

The Zeckendorf theorem, named after Edouard Zeckendorf , states that every natural number can be clearly written as the sum of different, not directly consecutive Fibonacci numbers . That is, there is a unique representation of the shape for each ${\displaystyle n>0}$ ${\displaystyle f_{i}}$ ${\displaystyle n\in \mathbb {N} ,n>0}$

${\displaystyle n=\sum _{i=2}^{k}c_{i}f_{i}}$with and for everyone . ${\displaystyle c_{i}\in \{0,1\}}$ ${\displaystyle c_{i}c_{i+1}=0}$ ${\displaystyle i}$

The resulting sequence of zeros and ones is called the Zeckendorf sequence . The Fibonacci code is very closely related to this . ${\displaystyle \left(c_{i}\right)_{i\in 2+\mathbb {N} _{0}}}$

calculation

Moivre-Binet formula

The Fibonacci sequence (red) as the difference between two sequences with irrational terms (black)

The explicit law of formation for the terms of the Fibonacci sequence was discovered independently by the French mathematicians Abraham de Moivre in 1718 and Jacques Philippe Marie Binet in 1843. In between, however, she was also known to the mathematicians Leonhard Euler and Daniel Bernoulli , the latter also providing what is probably the first proof in 1728.

The Fibonacci numbers can be found directly using

${\displaystyle f_{n}={\frac {\Phi ^{n}-\Psi ^{n}}{\Phi -\Psi }},\qquad n\in \mathbb {Z} }$

calculate, where are the two solutions of the characteristic equation . With ${\displaystyle \Phi ,\Psi }$ ${\displaystyle x^{2}-x-1=0}$

${\displaystyle \Phi ={\frac {1+{\sqrt {5}}}{2}}}$

${\displaystyle \Psi =1-\Phi ={\frac {1-{\sqrt {5}}}{2}}=-\Phi ^{-1}}$

is explicit:

${\displaystyle f_{n}={\frac {\Phi ^{n}-\Psi ^{n}}{\sqrt {5}}}={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)}$

The interplay of two irrational numbers and , which leads to an integer result, is remarkable . The figure shows the two sequences and and as their difference. ${\displaystyle \Phi }$ ${\displaystyle \Psi }$ ${\displaystyle \Phi ^{n}/{\sqrt {5}}}$ ${\displaystyle \Psi ^{n}/{\sqrt {5}}}$ ${\displaystyle f_{n}}$

Approximation formula for large numbers

The influence of quickly tends to zero, for example is . This can be used to shorten the calculation by ignoring the term for sufficiently large and rounding the result to the nearest natural number : ${\displaystyle \Psi }$ ${\displaystyle -5^{\scriptstyle -1/2}\Psi \approx +0{,}276}$ ${\displaystyle n}$

${\displaystyle f_{n}={\Bigg \lfloor }{\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{2}}{\Bigg \rfloor }=\left[{\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\right]}$         (Gaussian rounding bracket ) ${\displaystyle [\,\cdot \,]}$

In fact, that works for . ${\displaystyle 0\leq n\in \mathbb {Z} }$

Inductive proof

One of the simplest proofs is inductive. Because of and the beginning of induction is fulfilled. Assume that the formula applies to all values ​​from to ( strong induction assumption ). We show that it must then necessarily also apply to: ${\displaystyle {\tfrac {\Phi ^{0}-\Psi ^{0}}{\sqrt {5}}}=0=f_{0}}$ ${\displaystyle {\tfrac {\Phi ^{1}-\Psi ^{1}}{\sqrt {5}}}=1=f_{1}}$ ${\displaystyle 0}$ ${\displaystyle n}$ ${\displaystyle n+1}$

${\displaystyle {\begin{aligned}f_{n-1}+f_{n}&={\frac {\Phi ^{n-1}-\Psi ^{n-1}+\Phi ^{n}-\Psi ^{n}}{\sqrt {5}}}\\&={\frac {\Phi ^{n-1}(1+\Phi )-\Psi ^{n-1}(1+\Psi )}{\sqrt {5}}}\\&={\frac {\Phi ^{n-1}(\Phi ^{2})-\Psi ^{n-1}(\Psi ^{2})}{\sqrt {5}}}\\&={\frac {\Phi ^{n+1}-\Psi ^{n+1}}{\sqrt {5}}}\\&=f_{n+1}\end{aligned}}}$

We have used that and satisfy the characteristic equation . ${\displaystyle \Phi }$ ${\displaystyle \Psi }$ ${\displaystyle x^{2}=x+1}$

According to the principle of complete induction, the formula must now apply to everyone . ${\displaystyle n}$

Derivation of the Moivre-Binet formula

Binet's formula can be derived using matrix calculations and the eigenvalue problem in linear algebra using the following approach:

${\displaystyle {\begin{pmatrix}0&1\\1&1\end{pmatrix}}^{n}{\begin{pmatrix}f(0)\\f(1)\end{pmatrix}}={\begin{pmatrix}f(n)\\f(n+1)\end{pmatrix}},f(0)=0{\text{ und }}f(1)=1{\text{ mit }}n\geq 0.}$

Now we transform the matrix into a diagonal matrix by considering it as an eigenvalue problem . ${\displaystyle A={\begin{pmatrix}0&1\\1&1\end{pmatrix}}}$ ${\displaystyle D}$

The following applies , where is the matrix of the eigenvectors and the diagonal matrix with the eigenvalues. So it follows: ${\displaystyle A=TDT^{-1}}$ ${\displaystyle T}$ ${\displaystyle D}$

${\displaystyle {\begin{aligned}{\begin{pmatrix}0&1\\1&1\end{pmatrix}}^{n}{\begin{pmatrix}f(0)\\f(1)\end{pmatrix}}&=A^{n}{\begin{pmatrix}f(0)\\f(1)\end{pmatrix}}=\left(TDT^{-1}\right)^{n}{\begin{pmatrix}f(0)\\f(1)\end{pmatrix}}=TD^{n}T^{-1}{\begin{pmatrix}0\\1\end{pmatrix}}\\&={\begin{pmatrix}{\frac {-1-{\sqrt {5}}}{2}}&{\frac {-1+{\sqrt {5}}}{2}}\\1&1\end{pmatrix}}{\begin{pmatrix}{\frac {1-{\sqrt {5}}}{2}}&0\\0&{\frac {1+{\sqrt {5}}}{2}}\end{pmatrix}}^{n}{\begin{pmatrix}-{\frac {1}{\sqrt {5}}}&{\frac {{\sqrt {5}}-1}{2{\sqrt {5}}}}\\{\frac {1}{\sqrt {5}}}&{\frac {{\sqrt {5}}+1}{2{\sqrt {5}}}}\end{pmatrix}}{\begin{pmatrix}0\\1\end{pmatrix}}\\&={\begin{pmatrix}{\frac {-1-{\sqrt {5}}}{2}}&{\frac {-1+{\sqrt {5}}}{2}}\\1&1\end{pmatrix}}{\begin{pmatrix}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}&0\\0&\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\end{pmatrix}}{\begin{pmatrix}-{\frac {1}{\sqrt {5}}}&{\frac {{\sqrt {5}}-1}{2{\sqrt {5}}}}\\{\frac {1}{\sqrt {5}}}&{\frac {{\sqrt {5}}+1}{2{\sqrt {5}}}}\end{pmatrix}}{\begin{pmatrix}0\\1\end{pmatrix}}\\&={\begin{pmatrix}{\frac {-1-{\sqrt {5}}}{2}}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}&{\frac {-1+{\sqrt {5}}}{2}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\\\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}&\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\end{pmatrix}}{\begin{pmatrix}{\frac {{\sqrt {5}}-1}{2{\sqrt {5}}}}\\{\frac {{\sqrt {5}}+1}{2{\sqrt {5}}}}\end{pmatrix}}\\&={\begin{pmatrix}-{\frac {1}{\sqrt {5}}}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\\-{\frac {1}{\sqrt {5}}}\left({\frac {1-{\sqrt {5}}}{2}}\right)\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\end{pmatrix}}\\&={\begin{pmatrix}{\frac {1}{\sqrt {5}}}\left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right]\\{\frac {1}{\sqrt {5}}}\left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+1}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n+1}\right]\end{pmatrix}}\\&={\begin{pmatrix}f(n)\\f(n+1)\end{pmatrix}}\end{aligned}}}$

Derivation using a difference equation

Another derivation possibility follows from the theory of the linear difference equations :

Let it be a geometrical sequence : ${\displaystyle C_{n}=x^{n},n\in \mathbb {N} _{0}}$

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

So if it is chosen so that the characteristic equation is satisfied ( i.e. or ) , i. i.e., satisfies the Fibonacci recursion with the recursion start and . ${\displaystyle x}$ ${\displaystyle x^{2}-x-1=0}$ ${\displaystyle x=\Phi }$ ${\displaystyle x=\Psi \ }$ ${\displaystyle C_{n+1}=C_{n}+C_{n-1}}$ ${\displaystyle C_{n}}$ ${\displaystyle C_{0}=1}$ ${\displaystyle C_{1}=x}$

The recursive sequence , , has the explicit representation . Similarly , , . ${\displaystyle A_{0}=1}$ ${\displaystyle A_{1}=\Phi }$ ${\displaystyle A_{n+1}=A_{n}+A_{n-1}}$ ${\displaystyle A_{n}=\Phi ^{n}}$ ${\displaystyle B_{0}=1}$ ${\displaystyle B_{1}=\Psi }$ ${\displaystyle B_{n}=\Psi ^{n}}$

With and , because of the superposition property , any linear combination of the Fibonacci recursion is sufficient . With the help of a linear system of equations we get and , thus and . Hence it results explicitly . ${\displaystyle A_{n}}$ ${\displaystyle B_{n}}$ ${\displaystyle L_{n}=\alpha A_{n}+\beta B_{n}}$ ${\displaystyle L_{n+1}=L_{n}+L_{n-1}}$ ${\displaystyle \alpha ={\tfrac {1}{\sqrt {5}}}}$ ${\displaystyle \beta =-{\tfrac {1}{\sqrt {5}}}}$ ${\displaystyle L_{0}={\tfrac {\Phi ^{0}-\Psi ^{0}}{\sqrt {5}}}=0=f_{0}}$ ${\displaystyle L_{1}={\tfrac {\Phi ^{1}-\Psi ^{1}}{\sqrt {5}}}=1=f_{1}}$ ${\displaystyle F_{n}={\tfrac {A_{n}-B_{n}}{\sqrt {5}}}={\tfrac {\Phi ^{n}-\Psi ^{n}}{\sqrt {5}}}}$

For results and , i.e. H. the classic Lucas sequence with explicit . ${\displaystyle \alpha =\beta =1}$ ${\displaystyle L_{0}=2}$ ${\displaystyle L_{1}=1}$ ${\displaystyle L_{n}=A_{n}+B_{n}=\Phi ^{n}+\Psi ^{n}}$

Derivation using z-transformation

Since difference equations can be described very elegantly using the z-transformation , the z-transformation can also be used to derive the explicit formula for Fibonacci numbers. In the article Use of the z-transformation to determine explicit formulas of recursion rules , the general procedure is described and then explained using the example of the Fibonacci number sequence.

Alternating approximation

The quotients of successive terms of the Fibonacci sequence are alternately smaller and larger than the golden ratio:

${\displaystyle {\frac {f_{2n}}{f_{2n-1}}}<\Phi <{\frac {f_{2n+1}}{f_{2n}}}}$

Derivation

. A simple derivation can be given using the Moivre-Binet formula. Because for the numbers of the formula mentioned and natural applies: ${\displaystyle \Phi ,\Psi }$ ${\displaystyle n>0}$ ${\displaystyle -\Phi <0<-\Psi ;\qquad |\cdot \Psi ^{2n}>0}$ ${\displaystyle -\Phi \Psi ^{2n}<-\Psi ^{2n+1};\qquad |+\Phi ^{2n+1}}$ ${\displaystyle \Phi ^{2n+1}-\Phi \Psi ^{2n}=\Phi (\Phi ^{2n}-\Psi ^{2n})<\Phi ^{2n+1}-\Psi ^{2n+1};\qquad |:(\Phi ^{2n}-\Psi ^{2n})>0;\quad }$(1) ${\displaystyle \Phi <{\frac {\Phi ^{2n+1}-\Psi ^{2n+1}}{\Phi ^{2n}-\Psi ^{2n}}}={\frac {f_{2n+1}}{f_{2n}}}}$, since the common denominator disappears in the double fraction of the representation of the subsequent members with Moivre-Binet . - Corresponding: ${\displaystyle \Phi -\Psi }$ ${\displaystyle -\Phi <0<-\Psi ;\qquad |\cdot \Psi ^{2n-1}<0}$ ${\displaystyle -\Phi \Psi ^{2n-1}>-\Psi ^{2n};\qquad |+\Phi ^{2n}}$ ${\displaystyle \Phi ^{2n}-\Phi \Psi ^{2n-1}=\Phi (\Phi ^{2n-1}-\Psi ^{2n-1})>\Phi ^{2n}-\Psi ^{2n};\qquad |:(\Phi ^{2n-1}-\Psi ^{2n-1})>0}$ ${\displaystyle \Phi >{\frac {\Phi ^{2n}-\Psi ^{2n}}{\Phi ^{2n-1}-\Psi ^{2n-1}}}={\frac {f_{2n}}{f_{2n-1}}};\quad }$ (2) The inequalities (1) and (2) together make the claim.

The difference between these upper and lower bounds converges rapidly towards zero for increasing , because: ${\displaystyle \Phi }$ ${\displaystyle n}$

${\displaystyle {\frac {f_{2n+1}}{f_{2n}}}-{\frac {f_{2n}}{f_{2n-1}}}={\frac {f_{2n+1}f_{2n-1}-f_{2n}^{2}}{f_{2n}f_{2n-1}}}={\frac {1}{f_{2n}f_{2n-1}}}}$;

when simplifying the counter, the identity of Cassini was used together with . ${\displaystyle (-1)^{2n}=1}$

Generating function

A generating function of the Fibonacci numbers is

${\displaystyle \sum _{n=0}^{\infty }f_{n}z^{n}={\frac {z}{1-z-z^{2}}}={\frac {1}{\Phi -\Psi }}({\frac {1}{1-\Phi z}}-{\frac {1}{1-\Psi z}}).}$

The power series on the left converges for . The de Moivre-Binet formula is obtained from the given partial fraction decomposition . ${\displaystyle |z|<1/\Phi =0{,}618\ldots }$

Derivation of the generating function

For is ${\displaystyle G(z)=\sum _{n=0}^{\infty }f_{n}z^{n}}$ ${\displaystyle \sum _{n=0}^{\infty }f_{n+1}z^{n}=\sum _{n=1}^{\infty }f_{n}z^{n-1}=z^{-1}\sum _{n=1}^{\infty }f_{n}z^{n}=z^{-1}\sum _{n=0}^{\infty }f_{n}z^{n}={\frac {G(z)}{z}}\quad }$, there ; ${\displaystyle f_{0}=0}$ ${\displaystyle \sum _{n=0}^{\infty }f_{n+2}z^{n}=\sum _{n=2}^{\infty }f_{n}z^{n-2}=z^{-2}\sum _{n=2}^{\infty }f_{n}z^{n}=z^{-2}(-z+\sum _{n=0}^{\infty }f_{n}z^{n})={\frac {G(z)-z}{z^{2}}}\quad }$, there and ; ${\displaystyle f_{0}=0}$ ${\displaystyle f_{1}=1}$ the recursion condition therefore induces ${\displaystyle f_{n+2}=f_{n+1}+f_{n}}$ ${\displaystyle \sum _{n=0}^{\infty }f_{n+2}z^{n}=\sum _{n=0}^{\infty }f_{n+1}z^{n}+\sum _{n=0}^{\infty }f_{n}z^{n}\Leftrightarrow }$ ${\displaystyle {\frac {G(z)-z}{z^{2}}}={\frac {G(z)}{z}}+G(z)\quad \mid \cdot z^{2}}$ ${\displaystyle G(z)-z=z\cdot G(z)+z^{2}\cdot G(z)\quad \mid }$; sum up: ${\displaystyle G(z)\cdot (1-z-z^{2})=z}$, with division by (true appropriately chosen ) the given form follows. ${\displaystyle (1-z-z^{2})\neq 0}$ ${\displaystyle z}$

With a suitable generating function, a relationship between the Fibonacci numbers and the binomial coefficients can be represented:

${\displaystyle f_{n\geq 1}=\sum _{k=0}^{[{\frac {n-1}{2}}]}{\tbinom {n-k-1}{k}}}$.

Because for and can also be written without Gaussian brackets: ${\displaystyle \textstyle {\tbinom {n-k-1}{k}}=0}$ ${\displaystyle \textstyle n-k-1\geq 0}$ ${\displaystyle \textstyle k>n-k-1}$

${\displaystyle f_{n\geq 1}=\sum _{k=0}^{n-1}{\tbinom {n-k-1}{k}}=\sum _{k=1}^{n}{\tbinom {n-k}{k-1}}}$.

Derivation

The generating function can also be written: ${\displaystyle \sum _{n=0}^{\infty }f_{n}z^{n}=0+\sum _{n=1}^{\infty }f_{n}z^{n}={\frac {z}{1-z-z^{2}}};\quad }$(1) for the amount that is sufficiently small, the following applies: ${\displaystyle z}$ ${\displaystyle \sum _{l=1}^{\infty }(z+z^{2})^{l}={\frac {z+z^{2}}{1-(z+z^{2})}}={\frac {z(1+z)}{1-z-z^{2}}}\quad \mid :(1+z)\neq 0}$ ${\displaystyle \sum _{l=1}^{\infty }z^{l}(1+z)^{l-1}={\frac {z}{1-z-z^{2}}};\quad }$(2) Equating gives: ${\displaystyle \sum _{n=1}^{\infty }f_{n}z^{n}=\sum _{l=1}^{\infty }z^{l}(1+z)^{l-1}=\sum _{l=1}^{\infty }z^{l}\sum _{k=0}^{l-1}{\tbinom {l-1}{k}}z^{k}=\sum _{n=1}^{\infty }z^{n}\sum _{k=0}^{[{\frac {n-1}{2}}]}{\tbinom {n-k-1}{k}}}$, where [] are Gaussian brackets ; in the forming of were binomial theorem and the Umsummierung with used. ${\displaystyle n=k+l}$ ${\displaystyle \textstyle k\leq l-1\Rightarrow k\leq {\frac {n-1}{2}}}$ Comparison of coefficients results in the specified relationship.

The notation for the generating function also allows the representation: ${\displaystyle G(z)}$

${\displaystyle f_{n}={\frac {1}{n!}}{\frac {\mathrm {d} ^{n}}{\mathrm {d} z^{n}}}G(0).}$

Derivation

In the representation of as an infinite sum, the summand is also dispensable, see previous derivation. ${\displaystyle G(z)}$ ${\displaystyle k=0}$ The -th derivative of the generating function is with the power rule : ${\displaystyle n}$ ${\displaystyle {\frac {d^{n}}{dz^{n}}}G(z)=}$ ${\displaystyle \sum _{k=1}^{\infty }{\frac {d^{n}}{dz^{n}}}f_{k}z^{k}=}$ ${\displaystyle \sum _{k=1}^{n-1}{\frac {d^{n}}{dz^{n}}}f_{k}z^{k}+{\frac {d^{n}}{dz^{n}}}f_{n}z^{n}+\sum _{k=n+1}^{\infty }{\frac {d^{n}}{dz^{n}}}f_{k}z^{k}=}$ ${\displaystyle 0+n!f_{n}+\sum _{k=n+1}^{\infty }{\frac {k!}{(k-n)!}}f_{n}z^{k-n};}$ for the sum of the last line disappears. For this arises with division by the assertion. ${\displaystyle z=0}$ ${\displaystyle z}$ ${\displaystyle n!\neq 0}$

Representation with matrices

The Fibonacci numbers also appear as entries of the powers of the matrix : ${\displaystyle A={\begin{pmatrix}1&1\\1&0\end{pmatrix}}}$

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

For example, the first formula given above for . at the same time describes the summation rule of the Fibonacci sequence, because its product with a pair of consecutive Fibonacci numbers (written as a column matrix) gives the next pair; accordingly generates the -th pair from the start pair . This and the fact that the eigenvalues ​​of precisely the golden ratio and its reciprocal value (the latter with a negative sign ) lead again to the above-mentioned formula by Binet. ${\displaystyle A^{m+n}=A^{m}A^{n}}$ ${\displaystyle f_{m+n}}$ ${\displaystyle A}$ ${\displaystyle A^{n}}$ ${\displaystyle n}$ ${\displaystyle (0,1)}$ ${\displaystyle A}$

Relationship with Pascal's triangle

The Fibonacci numbers can be described using the Pascal triangle . To determine the nth Fibonacci number, take every second number from the nth line of Pascal's triangle and weight it with the corresponding power of five - starting with 0 in ascending order, i.e. H. , , Etc. is then added together and divided by these weighted elements . ${\displaystyle 5^{0}}$ ${\displaystyle 5^{1}}$ ${\displaystyle 5^{2}}$ ${\textstyle 2^{n-1}}$

The picture below illustrates the calculation of the first seven Fibonacci numbers from Pascal's triangle . For easier understanding, the unused elements of Pascal's triangle are grayed out in the picture , the weighting with the ascending powers of five is highlighted in red and the exponents in cyan . ${\displaystyle 2^{n-1}}$

Derivation

Based on the explicit formula for the Fibonacci numbers (see Moivre-Binet formula below in this article) ${\displaystyle f_{n}={\frac {1}{\sqrt {5}}}\cdot \left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right),\quad k\geq 0}$ you can first exclude the term in the denominator and write out the remaining difference using binomial coefficients and then summarize: ${\displaystyle 2^{n}}$ ${\displaystyle {\begin{aligned}f_{n}&={\frac {1}{\sqrt {5}}}\cdot {\frac {1}{2^{n}}}\cdot \left(\left(1+{\sqrt {5}}\right)^{n}-\left(1-{\sqrt {5}}\right)^{n}\right)\\&={\frac {1}{\sqrt {5}}}\cdot {\frac {1}{2^{n}}}\cdot \left(\sum _{i=0}^{n}{\binom {n}{i}}1^{n-i}\cdot \left({\sqrt {5}}\right)^{i}-\sum _{i=0}^{n}{\binom {n}{i}}1^{n-i}\cdot \left(-{\sqrt {5}}\right)^{i}\right)\\&={\frac {1}{{\sqrt {5}}\cdot 2^{n}}}\cdot \sum _{i=0}^{n}{\binom {n}{i}}\cdot \left(\left({\sqrt {5}}\right)^{i}-\left(-{\sqrt {5}}\right)^{i}\right)\\\end{aligned}}}$ The following applies to the difference under the sum symbol: ${\displaystyle \left({\sqrt {5}}\right)^{i}-\left(-{\sqrt {5}}\right)^{i}={\begin{cases}0\ &{\text{falls }}i\,{\text{gerade}}\\2\cdot \left({\sqrt {5}}\right)^{i}\ &{\text{falls }}i\,{\text{ungerade}}\end{cases}}}$ so that you can reduce the sum to odd : ${\displaystyle i}$ ${\displaystyle {\begin{aligned}f_{n}&={\frac {1}{{\sqrt {5}}\cdot 2^{n}}}\cdot \sum _{j=0}^{\lfloor n/2\rfloor }{\binom {n}{2j+1}}\cdot 2\cdot \left({\sqrt {5}}\right)^{2j+1}\\&={\frac {1}{{\sqrt {5}}\cdot 2^{n}}}\cdot \sum _{j=0}^{\lfloor n/2\rfloor }{\binom {n}{2j+1}}\cdot \left({\sqrt {5}}\right)^{2j}\cdot 2{\sqrt {5}}\\&={\frac {{\sqrt {5}}\cdot 2}{{\sqrt {5}}\cdot 2^{n}}}\cdot \sum _{j=0}^{\lfloor n/2\rfloor }{\binom {n}{2j+1}}\cdot \left(\left({\sqrt {5}}\right)^{2}\right)^{j}\\&={\frac {1}{2^{n-1}}}\cdot \sum _{j=0}^{\lfloor n/2\rfloor }{\binom {n}{2j+1}}\cdot 5^{j}.\end{aligned}}}$ The term is thus abbreviated and only powers of five remain under the sum symbol. This explains the apparent paradox that the explicit formula for Fibonacci numbers with their terms delivers whole numbers at all. The rounding off in the total upper limit is also necessary so that the indexing does not exceed the value and the original total limit is adhered to. ${\displaystyle {\sqrt {5}}}$ ${\displaystyle {\sqrt {5}}}$ ${\displaystyle \lfloor n/2\rfloor }$ ${\displaystyle n}$ If you compare the binomial coefficients remaining under the summation symbol with those in Pascal's triangle , you can see that it is every second coefficient in the corresponding line of the triangle (as it is visualized in the picture above). You can also use the formula as ${\displaystyle f_{n}={\frac {1}{2^{n-1}}}\cdot \sum _{j=0}^{\lfloor n/2\rfloor }P_{n,2j+1}\cdot 5^{j}}$ With the designation for a binomial coefficient at the -th place in the -th line of the Pascal triangle (both counted from zero!). As an example, the value for the 7th Fibonacci number is approximately ${\displaystyle P_{n,k}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle {\begin{aligned}f_{7}&={\frac {1}{2^{6}}}\cdot \sum _{j=0}^{3}P_{7,2j+1}\cdot 5^{j}\\&={\frac {1}{64}}\cdot \left(P_{7,1}\cdot 5^{0}+P_{7,3}\cdot 5^{1}+P_{7,5}\cdot 5^{2}+P_{7,7}\cdot 5^{3}\right)\\&={\frac {1}{64}}\cdot \left(7\cdot 1+35\cdot 5+21\cdot 25+1\cdot 125\right)={\frac {832}{64}}=13.\end{aligned}}}$

Generalizations

See also : Generalized Fibonacci Sequence

The classical ("canonical") Fibonacci sequence is characterized by three criteria:

• A linear iteration that incorporates the two preceding terms
• A linear combination of these elements in the sequence in which both predecessors have the coefficient +1
• Both starting links equal +1

Each of these criteria allows a generalization:

• The choice of other starting terms and yields a sequence related to the canonical sequence after the relationship . An example of this is the Lucas sequence . ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle (a_{n})}$ ${\displaystyle a_{n}=u\cdot f_{n-2}+v\cdot f_{n-1}}$ ${\displaystyle (L_{n})}$

For the terms of such a sequence, an explicit law of formation that is generalized compared to the Moivre-Binet formula applies:

${\displaystyle a_{n}\!\,={\frac {k\cdot \Phi ^{n}-l\cdot \Psi ^{n}}{\sqrt {5}}}}$with and . ${\displaystyle k=u\cdot \Psi ^{2}-v\cdot \Psi }$ ${\displaystyle l=u\cdot \Phi ^{2}-v\cdot \Phi }$

The canonical sequence is represented here as a special case , which, because of the characteristic equation, delivers immediately and . ${\displaystyle u=v=1}$ ${\displaystyle k=1}$ ${\displaystyle l=1}$

• The choice of other coefficients for the linear combination yields a sequence for which a different characteristic equation holds. A sequence with the iteration rule

${\displaystyle a_{n}=q\cdot a_{n-2}+p\cdot a_{n-1}}$

has the characteristic equation . The roots of this equation determine the explicit law of formation. If the characteristic equation has roots and , then the law of formation reads ${\displaystyle x^{2}-px-q=0}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$

${\displaystyle a_{n}={\frac {k\cdot \alpha ^{n}-l\cdot \beta ^{n}}{\alpha -\beta }},}$

where and again are determined by the starting members. ${\displaystyle k}$ ${\displaystyle l}$

• An iteration which includes more than two preceding sequence members accordingly has a polynomial of a higher degree than the characteristic equation, the roots of this equation appearing again in the formation law and the coefficients being determined by the initial values. It then applies ${\displaystyle x_{i}}$ ${\displaystyle k_{i}}$

${\displaystyle a_{n}=\sum _{i=1}^{n}{k_{i}x_{i}^{n}}}$.

Examples of such sequences are the Tribonacci and Tetra nacci sequences. The Perrin sequence and the Padovan sequence follow the rule . ${\displaystyle a_{n}=a_{n-2}+a_{n-3}}$

In this context, an iteration that only uses the immediately preceding term delivers a pure power sequence as a degenerate Fibonacci sequence.

Fibonacci sequences in nature

Phyllotaxis

Sunflower with 34 and 55 Fibonacci spirals

Arrangement of circles of equal size at the distance of the golden angle with colored marking of the Fibonacci spirals 8, 13, 21, 34

The leaves ( phyllotaxis ) or fruit stands of many plants are arranged in spirals , the number of these spirals corresponding to the Fibonacci numbers. In this case the angle between architecturally adjacent leaves or fruits with respect to the plant axis is the golden angle . This is because fractions of consecutive Fibonacci numbers best approximate the underlying golden ratio . The spirals are therefore formed by plant elements, the place numbers of which differ in the Fibonacci number in the denominator and thus almost point in the same direction. This spiral arrangement of the leaves around the stem axis gives the plant the best possible light yield. The offset of the leaves by the irrational ratio of the golden angle ensures that periods never appear, as is the case e.g. B. would be the case with 1/4 (0 ° 90 ° 180 ° 270 ° | 0 ° 90 ° ...). This avoids the worst possible case that one leaf is exactly perpendicular to the other and so the leaves create maximum shadows on the leaves below or maximum 'light gaps' arise.

For example, the baskets of the silver thistle (Carlina acaulis) carry hundreds of identical flowers, which are inserted into the bottom of the basket in smaller baskets in a 21-to-55 position, in larger baskets in 34-to-89 and 55-to-144 positions are. The scales of spruce cones as well as pineapple fruits form clockwise and counter-clockwise spirals, the number of scales being given by two consecutive Fibonacci numbers.

For the history of science, reference is made to the book On Growth and Form by D'Arcy Wentworth Thompson (1917).

Family trees

Males of the honey bee ( Apis mellifera ) are known as drones. Interestingly, the Fibonacci sequence describes the number of ancestors in a drone. This is explained by the fact that a drone (generation n  = 1) develops from an unfertilized egg that only contains the genetic material of its mother, the queen bee (generation n  = 2); a drone has no father. A queen, however, has two parents, namely as a mother another queen and as a father a drone (generation n  = 3) etc. The number of all ancestors of a drone in each defined nth generation is the nth Fibonacci number . ${\displaystyle f_{n}}$

To see this, you can use the drawing for the number of rabbits in Fibonacci's model in the " Ancient and Middle Ages in Europe " section. Each pair of immature rabbits corresponds to a drone, each pair of sexually mature rabbits to a queen. The equations of the modeling then contain the number of drones, the number of queens (in each case in the nth generation) and the number of ancestors of a drone in the generation under consideration. ${\displaystyle y_{n}}$ ${\displaystyle x_{n}}$ ${\displaystyle f_{n>1}}$

Fatty acids

Unbranched aliphatic monocarboxylic acids (here: uaM ), to which the fatty acids usually belong, can have different numbers of double bonds in different positions. The number of uaM obeys the Fibonacci sequence as a function of the chain length. This follows from the fact that double bonds in uaM are not adjacent; the rare exceptions are neglected here. Specifically, there is only one aliphatic monocarboxylic acid with one carbon atom: formic acid , one with two carbon atoms: acetic acid , two with three: propionic acid and acrylic acid , etc. With 18 carbon atoms there are 2,584 variants (of which stearic acid , oleic acid , linoleic acid and Linolenic acid are four examples).

To see this, you can use the drawing for the number of rabbits in Fibonacci's model in the section " Ancient and Middle Ages in Europe ". A pair of rabbits of the -th generation corresponds to the -th carbon atom of a uaM, counting starting with the carboxy group . Each pair of immature rabbits corresponds to a carbon atom that can not be followed by a double bond, and each pair of sexually mature rabbits corresponds to a carbon atom that can (or cannot) be followed by a double bond . The connecting links from to or from to correspond to single bonds, the connecting links from to double bonds. In the modeling equations, (or ) is the number of carbon atoms (or ). - Every path from to a carbon atom of the -th generation corresponds exactly to one uaM with carbon atoms; the assignment is bijective . So the number of carbon atoms considered in the -th generation is equal to the number of uaM with carbon atoms. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle c_{n}}$ ${\displaystyle C_{n}}$ ${\displaystyle c_{n}}$ ${\displaystyle C_{n+1}}$ ${\displaystyle C_{n}}$ ${\displaystyle C_{n+1}}$ ${\displaystyle C_{n}}$ ${\displaystyle c_{n+1}}$ ${\displaystyle y_{n}}$ ${\displaystyle x_{n}}$ ${\displaystyle c_{n}}$ ${\displaystyle C_{n}}$ ${\displaystyle c_{1}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle f_{n}}$ ${\displaystyle n}$ ${\displaystyle n}$

history

Calculation of the rabbit task in Liber abbaci

Ancient India

Its earliest mention is under the name mātrāmeru ("mountain of cadence") in the Chhandah-shāstra ("art of prosody ") of the Sanskrit grammarist Pingala (around 450 BC or according to another dating around 200 BC. ). Virahanka (6th century) and especially Acharya Hemachandra (1089–1172) later treated this sequence of numbers in more detail in order to describe the mathematical possibility of forming meters through regular distribution of short and long syllables.

Ancient and Middle Ages in Europe

In the western world, this series was also known in antiquity, Nicomachus of Gerasa (around 100 AD). However, it is associated with the name of the Italian mathematician Leonardo da Pisa , called Fibonacci ( "figlio di Bonacci", son of Bonacci), who in his Liber abbaci ("Book of arithmetic", first version from 1202 not preserved, second version of approx. 1227) described this sequence of numbers with the example of a rabbit breeder who wants to find out how many pairs of rabbits arise from a single pair within a year if each pair gives birth to another pair per month from the second month of life:

The number of rabbits in Fibonacci’s model are the Fibonacci numbers

Fibonacci illustrated this sequence by simply mathematically modeling the growth of a population of rabbits according to the following rules:

1. Each pair of rabbits gives birth to another pair of rabbits per month.
2. A newborn couple does not have offspring until they are two months old (the competition lasts from one month to the next).
3. The animals are in a closed room (“in quodam loco, qui erat undique pariete circumdatus”) so that no animal can leave the population and none can come in from outside.

Fibonacci started the sequence, not entirely consistently, not with a newborn but with a pregnant couple who had their offspring in the first month, so that in the first month there were already 2 couples. In each subsequent month, a number of newborn couples is added to the number of couples who lived in the previous month, which is equal to the number of those couples who had already lived in the previous month, because the offspring of the previous month is still too young, in order to throw offspring for his part. Fibonacci presented the facts for the twelve months of a year (2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377) and pointed to the formation law of the sequence by adding up two consecutive terms of the sequence ( 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13 etc.). He also noted that the sequence can be continued for an infinite number of months according to this principle, which then presupposes immortal rabbits: "et sic posses facere per ordinem de infinitis numeris mensibus." He had further observance of the principle in his received Works not for free.

A 2014 mathematical-historical analysis of the life of Leonardo of Pisa, in particular of his stay in the North African port city of Bejaia (in today's Algeria), came to the conclusion that the background of the Fibonacci sequence was not based on a model of the multiplication of Rabbits are to be looked for (which has been suspected for a long time), but rather to be found with the beekeepers of Bejaia and their knowledge of the bee family tree. In Leonardo's time, Bejaia was an important exporter of beeswax, as the French name of the city (bougie, as the French word for candle) indicates.

After later mathematicians such as Gabriel Lamé (1795–1870) had claimed the discovery of this sequence of numbers for themselves, Édouard Lucas (1842–1891) and others brought back to mind that the oldest known document at the time came from Leonardo da Pisa, and under The name “Fibonacci sequence” (“suite de Fibonacci”, “Fibonacci sequence”, “successione di Fibonacci”) has since become common in most western languages.

Mathematical modeling of the growth of Fibonacci's rabbit population Let the number of sexually mature or the number of non-sexually mature rabbits of the -th generation, correspondingly for generations and . According to the rules given above, with these designations is: ${\displaystyle x_{n}}$ ${\displaystyle y_{n}}$ ${\displaystyle \textstyle n}$ ${\displaystyle \textstyle n-1}$ ${\displaystyle \textstyle n-2}$ ${\displaystyle x_{n}=x_{n-1}+y_{n-1}}$   (1);    (1'); (2); ${\displaystyle x_{n-1}=x_{n-2}+y_{n-2}}$    ${\displaystyle y_{n}=x_{n-1}}$   Inserting (1 ') into (1) and then adding (2) results in: ${\displaystyle x_{n}[+y_{n}]=(x_{n-2}+y_{n-2})+y_{n-1}[+x_{n-1}]}$, for the total number ,   ,   of rabbits of each generation so ${\displaystyle f_{n}=x_{n}+y_{n}}$ ${\displaystyle f_{n-2}=x_{n-2}+y_{n-2}}$ ${\displaystyle f_{n-1}=x_{n-1}+y_{n-1}}$ ${\displaystyle f_{n}=f_{n-2}+f_{n-1}}$, which is equivalent to the given recursive law of formation of the Fibonacci sequence. With this model describes the time shown in the drawing sequence of generations. ${\displaystyle x_{1}=0,y_{1}=1}$

Reception in arts and entertainment

• In entertainment math, the checkerboard paradox and similar geometric fallacies are based on the properties of the Fibonacci sequence.
• The system poem alfabet (1981) by the Danish writer Inger Christensen is based on the Fibonacci sequence.
• The cover of the Canadian band The Organ's debut album , Grab That Gun , was designed by David Cuesta using a grid based on the Fibonacci sequence.
• The artists Mario Merz and Petra Paffenholz deal with the Fibonacci sequence in their installations.
• The vocals in the song Lateralus of the progressive metal band Tool are based on Fibonacci numbers.
• The artist Martina Schettina also deals with the Fibonacci numbers in her mathematical pictures .
• Dan Brown uses the Fibonacci sequence as a secret message in his thriller The Da Vinci Code (2003) (German: Sakrileg , 2004).
• In Darren Aronofsky's film π - System in Chaos , in which the protagonist searches for the “pattern of the world” in the price data of stocks and in the number π, the Fibonacci sequence is mentioned.
• In the series Criminal Minds (season 4, episode 8), a killer kidnaps his victims using the Fibonacci sequence.
• In Lars von Trier's film Nymphomaniac , chapter 5 - small organ school - connects the Fibonacci sequence with a Bach organ movement.
• In the video game Watch Dogs from Ubisoft , in the serial killer mission as numbers that can be found at the individual crime scenes of the victims.
• In the song What's Goes? From Die Orsons KAAS raps the Fibonacci sequence up to the number 144.
• At the Leibstadt nuclear power plant (CH), the south front of the machine house is painted with a curve made up of six orange rectangular elements that rises progressively to the right , the individual (but also added) heights of which correspond to the Fibonacci sequence.
• In the video game Dishonored: Death of the Outsider , the Fibonacci sequence is used as a combination for a bank vault
• In the manga Jojo’s Bizzare Adventure: Steel Ball Run , the Fibonacci representation is used to represent the strength of the protagonist.

• 

  Martina Schettina: Fibonacci's dream, 2008, 40 × 40 cm

• 

  Petra Paffenholz: Fibonacci Cubes (part of the sculpture trail “ Diepholz | Dümmer ”), 2014, 10 cm to 5.50 m

• 

  The Fibonacci Terrace in the Science Center Singapore . The individual plates are arranged in such a way that they form figures in the proportions of the Fibonacci numbers.

• 

  Fibonacci numbers on the Mole Antonelliana in Turin

• 

  The Fibonacci numbers at the Lindenbrauerei in Unna , light installation created by Mario Merz

• 

  The Fibonacci numbers in Zurich's main train station

• 

  Detailed view of Zurich: window crosses and birds

Fibonacci data structures

The Fibonacci sequence gives its name to the following data structures, in whose mathematical analysis it occurs.

• Fibonacci tree
• Fibonacci heap

literature

• Thomas Koshy: Fibonacci and Lucas Numbers with Applications . Wiley, 2001, ISBN 9781118031315
• John H. Conway , Richard K. Guy : The Book of Numbers. Copernicus NY 1996, ISBN 0-387-97993-X .
• Richard A. Dunlap: The Golden Ratio and Fibonacci Numbers. 2nd Edition. World Scientific, Singapore, 1999, ISBN 981-02-3264-0 .
• Huberta Lausch : Fibonacci and the sequence (s). Oldenbourg 2010, ISBN 978-3-486-58910-8 .
• Paulo Ribenboim : The New Book of Prime Number Records. Springer-Verlag 1996, ISBN 0-387-94457-5 .
• The Fibonacci Quarterly. A quarterly magazine since 1963 devoted to the Fibonacci and related episodes.

Web links

Wikibooks: Algorithm Collection: Number Theory: Fibonacci Sequence  - Learning and Teaching Materials

Commons : Fibonacci numbers  - collection of images, videos and audio files

• Fibonacci numbers - very detailed page with additional topics
• Fibonacci Numbers and the Golden Section (English)
• Fibonacci and the golden ratio (PDF; 1.2 MB)
• Video : The Fibonacci numbers (from the TV show Mathematics to touch on the BR-alpha channel ) by Albrecht Beutelspacher
• Video: The Fibonacci Sequence . University of Education Heidelberg (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19898 .

Individual evidence

1. ↑ Follow A000045 in OEIS
2. ^ Parmanand Singh: The So-called Fibonacci numbers in ancient and medieval India . In: Historia Mathematica . 12, No. 3, 1985, pp. 229-244. doi : 10.1016 / 0315-0860 (85) 90021-7 .
3. ↑ ^{a b} Ruben Stelzner (in collaboration with Wolfgang Schad): The golden ratio. The mystery of beauty. In: golden-section.eu. Retrieved October 26, 2015.
4. ↑ Although many of the statements below also apply if the indices (subscripts) are shifted by a fixed amount, this definition has become commonplace. It also has the advantage that the addition to negative indices is symmetrical to 0.
5. ↑ Donald Knuth : Negafibonacci Numbers and the Hyperbolic Plane . Annual meeting. Ed .: The Mathematical Association of America. The Fairmont Hotel, San Jose, CA December 11, 2008 ( allacademic.com ).
6. ↑ Hendrik Lenstra : Profinite Fibonacci numbers . (PDF)
7. ↑ Yvonne Stry, Rainer Schwenkert: Chapter 11 Probability Theory and Statistics , Section 6 Applications , A Strange Digit Distribution and Tax Revision, Subsection 11.6.1, in: Mathematics compact: for engineers and computer scientists , Springer-Verlag, 2006, ISBN 9783540323129
8. ^ Nicolai N. Vorobiev: Fibonacci Numbers. Birkhäuser, Basel 2002, ISBN 3-7643-6135-2 , p. 59 ( online version ).
9. ↑ PDF. At: sternenreise.com.
10. ↑ Paulo Ribenboim: My Numbers, My Friends: Highlights of Number Theory. Springer textbook, 2009, ISBN 978-3-540-87955-8 , pp. 59-62.
11. ↑ Paulo Ribenboim: My Numbers, My Friends: Highlights of Number Theory. Springer textbook, 2009, ISBN 978-3-540-87955-8 , p. 323.
12. ^ Eric W. Weisstein : Zeckendorf Representation . In: MathWorld (English).
13. ↑ In some books de Moivre's discovery is also given as 1730 or the discovery is only attributed to Binet. For de Moivre, Bernoulli and Binet see in this regard Beutelspacher (Albrecht Beutelspacher, Bernhard Petri: The Golden Section. Spectrum, Heidelberg / Berlin / Oxford 1988, ISBN 3-411-03155-7 , p. 90) and Schröder (among others in: Herbert Schröder: Paths to Analysis: Genetic - Geometric - Constructive. Gabler, 2001, ISBN 3-540-42032-0 , p. 12 ( excerpt (Google) )). That the formula was also known to Euler can be found e.g. B. Winkler (Peter Winkler: More mathematical riddles for lovers. Gabler, 2010, ISBN 978-3-8274-2349-8 , p. 46 ( excerpt (Google) )) or Ben-Menahem (Ari Ben-Menahem: Historical Encyclopedia of Natural and Mathematical Sciences. Volume 1. Springer, 2009, ISBN 978-3-540-68831-0 , p. 611 ( excerpt (Google) ))
14. ^ Equation (2.12) in: "Fibonacci numbers and matrices", June 15, 2009, Robert C. Johnson, Department of Mathematical Sciences, Durham University, UK
15. ↑ Follow A000073 in OEIS , Follow A000078 in OEIS
16. ↑ Tony Noe, Tito Piezas III and Eric Weisstein : Fibonacci n-Step Number. Wolfram MathWorld , accessed July 6, 2017 . 
17. ↑ Follow A001608 in OEIS , Follow A000931 in OEIS
18. ↑ G. Hegi: Illustrated flora of Central Europe. Volume VI / 4. 2nd edition 1987. Weissdorn Verlag, Jena, ISBN 3-936055-23-8 .
19. ^ Richard A. Dunlap: The Golden Ratio and Fibonacci Numbers. World Scientific, Singapore 1999, ISBN 981-02-3264-0 , pp. 130-134.
20. ^ S. Schuster, M. Fichtner, S. Sasso: Use of Fibonacci numbers in lipidomics - Enumerating various classes of fatty acids. In: Sci. Rep. 7 (2017) 39821
21. ↑ Parmanand Singh: Acharya Hemachandra and the (so called) Fibonacci Numbers. In: Mathematics Education. 20.1 (Siwan, 1986), ISSN  0047-6269 , pp. 28-30.
22. ^ Friedrich Gustav Lang: Writing to measure. On engraving in ancient literature. In: Novum Testamentum. Vol. 41, Fasc. 1, 1999, pp. 40-57. Lang refers to Nicomachus of Gerasa on p. 55, footnote 86, who listed this series alongside other series of numbers.
23. ^ Baldassare Boncompagni (Ed.): Scritti di Leonardo Pisano matematico del secolo decimoterzo. Vol. I, Tipografia delle scienze matematiche e fisiche. Rome 1857, pp. 283–284 (Chapter XII, 7: “Quot paria coniculorum in uno anno ex uno pario germinentur”).
24. ^ TC Scott, P. Marketos: On the Origin of the Fibonacci Sequence . Ed .: MacTutor History of Mathematics archive , University of St Andrews. March 23, 2014 (English, online at mcs.st-andrews.ac.uk [PDF; 2.1 MB ; accessed on September 25, 2018]).
25. ^ Edouard Lucas: Recherches sur plusieurs ouvrages de Léonard de Pise et sur miscellaneous questions d'arithmétique supérieure. In: Bulletino di bibliografia e di storia delle scienze matematiche e fisiche 10. (1877), pp. 129-193, pp. 239-293.
26. ↑ Graham Hartmann: “No. 1: Tool, 'Lateralus' - Top 21st Century Metal Songs. ” At: loudwire.com. Accessed February 22, 2014.
27. ^ Contribution to MU - The mathematics lesson "Mathematics and Art". Vol. 55, issue 2, April 2009. Friedrich Verlag, publisher Stefan Deschauer, TU Dresden, ISSN  0025-5807 .
28. ^ Ingmar Lehmann : Fibonacci numbers in fine arts and literature. Accessed November 7, 2009 (PDF; 131 kB).
29. ↑ Missing Persons. At: watchdogs.wikia.com.
30. ↑ The Orsons - What's Goes? At: YouTube.com.