Fibonacci Sequence · aiwiki.page

The Fibonacci sequence is a sequence of integers in which each term is the sum of the two preceding terms. Under the standard indexing convention, it begins $0,1,1,2,3,5,8,13,21,34,55,\ldots$ . Its simple definition produces connections among number theory, combinatorics, and algebra. The sequence is named after Fibonacci, the medieval mathematician Leonardo of Pisa, although its formation rule was known in India before his work. (dlmf.nist.gov)

Definition and indexing

The Fibonacci numbers $F_n$ are defined by the initial conditions

F_0=0,\qquad F_1=1,

and the recurrence relation

F_n=F_{n-1}+F_{n-2}\qquad(n\geq2).

Thus $F_2=1$ , $F_3=2$ , and $F_4=3$ . The initial conditions are essential: the same recurrence with different starting values generally produces a different sequence. (dlmf.nist.gov)

Some presentations omit the initial zero and begin with $F_1=F_2=1$ ; others shift the indices. Consequently, “the $n$ th Fibonacci number” is unambiguous only when the indexing convention is specified. This article uses $F_0=0$ and $F_1=1$ . (dlmf.nist.gov)

Historical origins

The sequence arose in Indian studies of Sanskrit poetic meter. If a short syllable contributes one unit of duration and a long syllable contributes two, counting the arrangements of a given total duration leads to the Fibonacci recurrence. Historical scholarship identifies this formation rule in the work of Virahāṅka, dated between approximately 600 and 800 CE, Gopāla before 1135, and Hemacandra around 1150. These precede Fibonacci’s account. (sciencedirect.com)

Fibonacci presented the sequence through a rabbit-breeding problem in Liber abaci, first written in 1202 and revised in 1228. The idealized population begins with one pair; each pair becomes reproductive after a fixed delay and subsequently produces one new pair per month, while no rabbits die. The population in a month equals the surviving population from the previous month plus offspring produced by pairs present two months earlier. This yields the recurrence, not a realistic model of rabbit ecology. (mathshistory.st-andrews.ac.uk)

Closed form and the golden ratio

Although defined recursively, $F_n$ has an explicit expression, commonly called Binet’s formula:

F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}.

The number $\varphi\approx1.6180339887$ is the golden ratio, and $\psi=-1/\varphi$ . (dlmf.nist.gov)

The formula follows by looking for solutions of the recurrence proportional to $r^n$ . Substitution gives the polynomial equation

r^2=r+1,

whose roots are $\varphi$ and $\psi$ . A suitable linear combination of their powers satisfies the two initial conditions. Thus the irrational quantities in Binet’s formula combine to give an integer for every nonnegative integer $n$ . (fibonacci-numbers.surrey.ac.uk)

Because $|\psi|<1$ , its powers tend to zero. Consequently,

F_n\sim\frac{\varphi^n}{\sqrt5}, \qquad \lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi.

The sequence therefore grows exponentially, while ratios of consecutive terms approach the golden ratio. More precisely, for $n\geq0$ ,

F_n=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor.

This rounding identity assumes exact arithmetic; it does not guarantee correct results when large powers are evaluated with limited numerical precision. (fibonacci-numbers.surrey.ac.uk)

Algebraic representations

A matrix packages the recurrence as a single transformation. For $n\geq1$ ,

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

The matrix’s eigenvalues are $\varphi$ and $\psi$ . Its diagonalization supplies another derivation of Binet’s formula. (fibonacci-numbers.surrey.ac.uk)

The ordinary generating function is

G(x)=\sum_{n=0}^{\infty}F_nx^n =\frac{x}{1-x-x^2}.

To derive this expression, multiply the series by $1-x-x^2$ : the recurrence cancels every coefficient beyond the coefficient of $x$ . The identity holds as a formal power series and, analytically, for $|x|<1/\varphi$ . (fibonacci-numbers.surrey.ac.uk)

Counting interpretations

Fibonacci numbers count arrangements built from pieces of size one and two. Consider tiling a strip of $n$ unit cells using single-cell tiles and two-cell dominoes. Every tiling ends either with a single tile, leaving a strip of length $n-1$ , or with a domino, leaving one of length $n-2$ . With one empty tiling and one tiling of length one, the number of tilings is $F_{n+1}$ . The same reasoning counts ordered sums of $n$ whose summands are one or two. (fibonacci-numbers.surrey.ac.uk)

Grouping such tilings by the number $k$ of dominoes gives a formula using binomial coefficients:

F_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}.

There are $n-k$ tiles altogether, and choosing which $k$ are dominoes determines the tiling. This also explains the appearance of Fibonacci numbers in diagonal sums of Pascal’s triangle. (fibonacci-numbers.surrey.ac.uk)

Identities and divisibility

Several identities express the structure of the sequence:

\sum_{k=0}^{n}F_k=F_{n+2}-1,

\sum_{k=0}^{n}F_k^2=F_nF_{n+1},

and Cassini’s identity,

F_{n+1}F_{n-1}-F_n^2=(-1)^n \qquad(n\geq1).

Cassini’s identity follows by taking the determinant of the matrix representation, since the defining matrix has determinant $-1$ . (fibonacci-numbers.surrey.ac.uk)

A central divisibility property is

\gcd(F_m,F_n)=F_{\gcd(m,n)},

where $\gcd$ denotes the greatest common divisor. Consecutive Fibonacci numbers are therefore relatively prime, and $F_m$ divides $F_n$ whenever $m$ divides $n$ . (fibonacci-numbers.surrey.ac.uk)

Fibonacci numbers also provide a unique representation of positive integers. Zeckendorf’s theorem states that every positive integer is a sum of distinct, nonconsecutive Fibonacci numbers drawn from $F_2,F_3,\ldots$ . For example,

100=89+8+3=F_{11}+F_6+F_4.

Excluding $F_1$ avoids ambiguity from the two occurrences of 1. (fibonacci-numbers.surrey.ac.uk)

Computation

Direct recursive evaluation repeats many calculations. An iterative algorithm instead retains two consecutive values and repeatedly replaces them by the next pair. Computing $F_n$ this way requires a number of additions proportional to $n$ , while storing only a fixed number of integer variables. (fibonacci-numbers.surrey.ac.uk)

Faster evaluation uses doubling identities:

F_{2k}=F_k(2F_{k+1}-F_k),

F_{2k+1}=F_k^2+F_{k+1}^2.

These compute a pair of consecutive terms by repeatedly halving the target index, giving logarithmically many arithmetic stages. Matrix exponentiation offers a related method. This is an arithmetic-operation count, not a claim of logarithmic bit-level running time: the integers themselves grow in length with $n$ . (fibonacci-numbers.surrey.ac.uk)

Related sequences

The Lucas numbers follow the same recurrence but begin with $L_0=2$ and $L_1=1$ :

2,1,3,4,7,11,18,\ldots

They satisfy

L_n=F_{n-1}+F_{n+1}\qquad(n\geq1).

They illustrate how changing initial conditions preserves the recurrence while altering its particular solution. (dlmf.nist.gov)

Plant patterns and limits of interpretation

Fibonacci numbers occur frequently in phyllotaxis, the arrangement of leaves and other plant organs. Spiral patterns in flower heads and cones often have clockwise and counterclockwise spiral counts that are consecutive Fibonacci numbers. Mathematical growth models connect these patterns with divergence angles near the golden angle, approximately $137.5^\circ$ , and the rational approximations associated with the golden ratio. (arxiv.org)

These patterns are prevalent, not universal. Some plants exhibit Lucas-number counts or other arrangements. Their occurrence concerns particular growth and packing processes; it does not establish a general law that all natural forms follow the Fibonacci sequence. (fibonacci-numbers.surrey.ac.uk)

References

DLMF: §26.11 Integer Partitions: Compositionsdlmf.nist.gov
DLMF: §24.15 Related Sequences of Numbersdlmf.nist.gov
Fibonacci (1170–1250) — Biography — MacTutor History of Mathematicsmathshistory.st-andrews.ac.uk
Fibonacci's Rabbitsmath.oxford.emory.edu
A Formula for the n-th Fibonacci numberfibonacci-numbers.surrey.ac.uk
Two Proofs of the Fibonacci Numbers Formulafibonacci-numbers.surrey.ac.uk
The Mathematical Magic of the Fibonacci Numbersfibonacci-numbers.surrey.ac.uk
Fibonacci bases and Other Ways of Representing Numbersfibonacci-numbers.surrey.ac.uk
Fibonacci numbers in phyllotaxis: a simple modelarxiv.org
Phyllotaxis, disk packing and Fibonacci numbersarxiv.org
The Fibonacci Numbers and Golden section in Nature — 1fibonacci-numbers.surrey.ac.uk