Fact-checked by Grok 2 weeks ago

Fibonacci sequence

The Fibonacci sequence is a series of non-negative integers in which each number is the sum of the two preceding ones, typically starting with 0 and 1, yielding the terms 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so forth.^[1] This recurrence relation, denoted as F_n = F_n-1 + F_n-2 for n ≥ 2 with initial conditions F₀ = 0 and F₁ = 1, defines one of the oldest known recursive sequences in mathematics.^[2] The sequence's origins trace back to ancient Indian mathematics, where it was first described around 200 BCE by the scholar Pingala in his work on Sanskrit prosody, Chandaḥśāstra, under the name mātrāmeru.^[1] It was later elaborated in Indian texts, such as those by Gopala and Hemachandra in the 12th century,^[1] before being introduced to the Western world by the Italian mathematician Leonardo of Pisa, better known as Fibonacci, in his 1202 book Liber Abaci.^[3] In Liber Abaci, Fibonacci presented the sequence through a problem modeling the growth of a rabbit population under idealized breeding conditions, starting from a pair of rabbits and assuming no deaths.^[2] The modern term "Fibonacci sequence" was coined in 1877 by the French mathematician Édouard Lucas, who also explored its properties extensively.^[1] The Fibonacci sequence exhibits remarkable mathematical properties, such as the fact that the ratio of consecutive terms (F_n+1 / F_n) converges to the golden ratio φ ≈ 1.6180339887 as n increases, a limit that underpins its aesthetic and structural appeal.^[2] Consecutive Fibonacci numbers are always coprime, meaning their greatest common divisor is 1,^[4] and every third number in the sequence is even.^[5] Beyond pure mathematics, the sequence appears ubiquitously in nature, particularly in phyllotaxis—the arrangement of leaves, seeds, and branches in plants—where Fibonacci numbers optimize packing efficiency and exposure to sunlight, as seen in the spirals of pinecones, sunflowers, and pineapples.^[6] These natural occurrences, along with applications in computer algorithms, art, architecture, and finance, highlight the sequence's interdisciplinary significance.^[2]

History

Indian origins

The earliest known references to patterns equivalent to the Fibonacci sequence appear in ancient Indian mathematics, particularly in the context of Sanskrit prosody. Around 200 BCE, the scholar Pingala, in his treatise Chandaḥśāstra on poetic meters, introduced binary-like patterns through the concept of Meru Prastāra (Mount Meru), a triangular array where the sums of shallow diagonals yield numbers following the sequence 1, 1, 2, 3, 5, 8, and so on. These patterns arose from enumerating possible combinations of short (laghu, one unit) and long (guru, two units) syllables in verses, providing an implicit combinatorial foundation without an explicit recurrence rule.^[7]^[8] This idea was developed further by Virahanka, a mathematician active between the 6th and 7th centuries CE, who explicitly described the method for calculating the number of valid syllable combinations in meters of increasing length. In his work on prosody, Virahanka explained that the total variations for a meter of n units equal the sum of variations for n-1 and n-2 units, applied to examples such as 3 variations for 3 morae and 5 for 4 morae. This approach formalized the sequence in the service of poetic composition, emphasizing its utility in generating rhythmic structures in Sanskrit literature.^[7] By the 12th century, the sequence gained more structured recognition in combinatorial mathematics. Gopala, in a manuscript dated around 1135 CE, commented on and expanded Virahanka's rule, illustrating it with specific counts like 3 ways for 3 morae, 5 for 4, and 8 for 5, thereby reinforcing its application to syllable patterns. Similarly, Hemachandra, writing his Chandonuśāsana between 1142 and 1158 CE under the patronage of the Chaulukya dynasty in Gujarat, presented the sequence as 1, 2, 3, 5, 8, 13, 21 for determining the number of metrical forms, integrating it deeply into the study of poetry and linguistics. These contributions highlight the sequence's role in enumerating tilings or partitions, such as the number of ways to cover a line of length n using segments of 1 and 2 units—a modern interpretive lens that underscores its combinatorial essence in Indian scholarship.^[7]

European adoption

The Italian mathematician Leonardo Fibonacci (c. 1170–1250) introduced the sequence to Europe in his seminal work Liber Abaci, published in 1202, where he posed it as a problem illustrating the idealized growth of a rabbit population over one year.^[9] This presentation highlighted the sequence's utility in modeling iterative processes, embedding it within a broader collection of arithmetic problems aimed at merchants and scholars. Fibonacci's adoption of the sequence occurred amid his efforts to promote the Hindu-Arabic numeral system and efficient computational techniques in medieval Europe, where Roman numerals still dominated cumbersome calculations.^[10] Born in Pisa and educated in North Africa due to his father's diplomatic role, Fibonacci traveled extensively around 1200 to regions including Egypt, Syria, and Provence, gaining exposure to Islamic mathematical traditions that synthesized earlier Indian concepts.^[9] These travels, particularly in Bugia (modern Béjaïa, Algeria), under the tutelage of Arab scholars, informed Liber Abaci's content, bridging Eastern numerical innovations with Western practical needs.^[11] Early recognition emerged in scholarly circles, notably at the court of Holy Roman Emperor Frederick II in the 1220s, where Fibonacci demonstrated his expertise by solving challenges posed by court astronomers like Michael Scotus and Johannes of Palermo.^[9] A revised edition of Liber Abaci in 1228, dedicated to Scotus, further disseminated the work among European intellectuals connected to the Toledan school of translators.^[12] Throughout the 13th century, manuscripts of Liber Abaci were extensively copied and circulated in Italian and broader European academic environments, integrating the sequence into texts on commercial arithmetic and fostering its role in everyday mathematical practice.

Mathematical Definition and Formulation

Recursive definition

The Fibonacci sequence is a classic example of a recursively defined sequence in mathematics. To understand this, first consider the basic concepts: a sequence is an ordered list of numbers, such as 2, 4, 6, 8, ..., while a recurrence relation is an equation that defines each term in the sequence as a function of one or more preceding terms, typically requiring specified initial conditions to generate the full sequence.^[13] The standard recursive definition of the Fibonacci sequence begins with the initial conditions F_0 = 0 and F_1 = 1, followed by the recurrence relation F_n = F_{n-1} + F_{n-2} for all integers n > 1.^[14] This relation means that each subsequent term is the sum of the two immediately previous terms, allowing the sequence to be built iteratively from the starting values. Using this definition, the first thirteen terms (for n = 0 to $12) are:

\begin{align*} F_0 &= 0, \\ F_1 &= 1, \\ F_2 &= 1, \\ F_3 &= 2, \\ F_4 &= 3, \\ F_5 &= 5, \\ F_6 &= 8, \\ F_7 &= 13, \\ F_8 &= 21, \\ F_9 &= 34, \\ F_{10} &= 55, \\ F_{11} &= 89, \\ F_{12} &= 144. \end{align*}

These terms can be verified by direct substitution into the recurrence: for instance, F_3 = F_2 + F_1 = 1 + 1 = 2, and F_4 = F_3 + F_2 = 2 + 1 = 3.^[14] A common variant of the definition omits F_0 and sets F_1 = 1, F_2 = 1, with the same recurrence F_n = F_{n-1} + F_{n-2} for n \geq 3; this produces the sequence starting 1, 1, 2, 3, 5, ..., which aligns with the standard sequence from F_1 onward.^[15] This recursive structure was motivated by a problem in Fibonacci's 1202 book Liber Abaci, modeling the growth of a rabbit population under idealized conditions: a single newborn pair produces a new pair every month starting from the second month, with no deaths, leading to the number of pairs at month n satisfying the same recurrence as the sequence.^[16]

Closed-form expression

The closed-form expression for the nth Fibonacci number F_n is given by Binet's formula:

F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}},

where \phi = \frac{1 + \sqrt{5}}{2} is the golden ratio and \hat{\phi} = \frac{1 - \sqrt{5}}{2} is its conjugate.^[17] This formula arises from solving the linear recurrence relation F_n = F_{n-1} + F_{n-2} using the characteristic equation r^2 - r - 1 = 0, whose roots are precisely \phi and \hat{\phi}.^[18] The general solution to the recurrence is then F_n = A \phi^n + B \hat{\phi}^n, where the constants A and B are determined by the initial conditions F_0 = 0 and F_1 = 1, yielding A = \frac{1}{\sqrt{5}} and B = -\frac{1}{\sqrt{5}}.^[18] To verify, substitute Binet's formula into the recurrence: since \phi and \hat{\phi} satisfy \phi^2 = \phi + 1 and \hat{\phi}^2 = \hat{\phi} + 1, it follows that F_n = F_{n-1} + F_{n-2} holds for n \geq 2.^[19] The initial conditions are also satisfied: F_0 = \frac{\phi^0 - \hat{\phi}^0}{\sqrt{5}} = 0 and F_1 = \frac{\phi - \hat{\phi}}{\sqrt{5}} = 1.^[19] A notable property is that F_n is the integer closest to \frac{\phi^n}{\sqrt{5}}, as the term involving \hat{\phi}^n has absolute value less than \frac{1}{2} for all nonnegative integers n.^[20] Binet's formula was derived by the French mathematician Jacques Philippe Marie Binet in 1843, though the result was actually discovered earlier by Abraham de Moivre in 1718.^[17]

Representations and Computations

Matrix form

The matrix form provides a linear algebraic representation of the Fibonacci sequence, enabling efficient computation through matrix exponentiation. The sequence can be expressed using the companion matrix A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, known as the Fibonacci Q-matrix, where the entries correspond to initial Fibonacci numbers F_2 = 1, F_1 = 1, and F_0 = 0.^[21] Specifically, the vector \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} satisfies the relation \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = A^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}, with the initial vector representing F_1 = 1 and F_0 = 0.^[22] More generally, the powers of this matrix yield Fibonacci entries directly: A^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.^[21] This matrix has a determinant of -1, which follows from the characteristic equation \lambda^2 - \lambda - 1 = 0 and ensures that integer powers preserve the integer nature of Fibonacci numbers.^[23] The structure allows computation of pairs of consecutive Fibonacci terms F_{n+1} and F_n without generating the entire sequence up to n, by applying the matrix power to the initial vector.^[24] For large n, this formulation offers a computational advantage through fast matrix exponentiation, such as repeated squaring, which requires only O(\log n) matrix multiplications to compute A^n.^[24] Each matrix multiplication involves a constant number of operations (four scalar multiplications and two additions for 2×2 matrices), making it suitable for high-precision arithmetic with numbers having hundreds of digits.^[24] This method contrasts with iterative approaches that scale linearly with n, providing exact results unlike approximation-based alternatives.^[24]

Rounding method

One practical method for computing Fibonacci numbers leverages an approximation derived from Binet's formula, where the nth Fibonacci number F_n is the nearest integer to \frac{\phi^n}{\sqrt{5}}, with \phi = \frac{1 + \sqrt{5}}{2} denoting the golden ratio.^[14]^[25] This rounding approach simplifies calculation, as the exact Binet expression F_n = \frac{\phi^n - \psi^n}{\sqrt{5}} (with \psi = \frac{1 - \sqrt{5}}{2}) has a second term that is negligible for approximation purposes.^[25] The validity of this method stems from a strict error bound: the absolute difference satisfies \left| F_n - \frac{\phi^n}{\sqrt{5}} \right| = \left| \frac{\psi^n}{\sqrt{5}} \right| < \frac{1}{2} for all n \geq 0, since |\psi| \approx 0.618 < 1 and \sqrt{5} > 2, ensuring that rounding \frac{\phi^n}{\sqrt{5}} to the nearest integer always yields the exact F_n.^[25] This property holds universally without exceptions in the non-negative indices.^[25] For instance, to compute F_{10}, evaluate \phi^{10} \approx 122.99187, divide by \sqrt{5} \approx 2.23607 to get approximately 55.00000, and round to 55.^[26] Similar computations work reliably for moderate n. While effective for quick estimates and small to medium n, this method encounters limitations for very large n due to floating-point precision constraints in computational environments, where accumulated rounding errors in calculating \phi^n can lead to inaccuracies beyond n \approx 70.^[26] Nonetheless, it remains valuable in programming for efficient approximation when exact values are not required or when combined with arbitrary-precision arithmetic.^[26]

Connections to the Golden Ratio

Binet's formula details

Binet's formula for the Fibonacci numbers, F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}, where \phi = \frac{1 + \sqrt{5}}{2} is the golden ratio and \psi = \frac{1 - \sqrt{5}}{2}, was first derived by Abraham de Moivre around 1718, with later independent discoveries by Daniel Bernoulli and Leonhard Euler in the mid-18th century, before its publication by Jacques Philippe Marie Binet in 1843.^[27] The formula extends naturally to negative indices, yielding F_{-n} = (-1)^{n+1} F_n for positive integers n, which preserves the recurrence relation F_m = F_{m+1} + F_{m-1} when extended backwards from F_0 = 0 and F_1 = 1.^[28] Binet's formula connects closely to the Lucas numbers L_n, which satisfy the same recurrence as the Fibonacci sequence but with initial conditions L_0 = 2 and L_1 = 1; their closed form is L_n = \phi^n + \psi^n, and a key identity links them via L_n = F_{n-1} + F_{n+1} for n \geq 1.^[29] Although \phi and \psi are irrational and \sqrt{5} is irrational, Binet's formula produces integers for all integer n, as verified by induction: the expression satisfies the Fibonacci recurrence F_n = F_{n-1} + F_{n-2} for n \geq 2, and matches the integer initial conditions F_0 = 0 and F_1 = 1, ensuring all subsequent terms are integers.^[30]

Asymptotic magnitude

The asymptotic magnitude of the Fibonacci numbers is captured by the dominant term in Binet's formula, which expresses F_n as F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}, where \phi = \frac{1 + \sqrt{5}}{2} is the golden ratio and \psi = \frac{1 - \sqrt{5}}{2}.^[14] As n \to \infty, F_n \sim \frac{\phi^n}{\sqrt{5}}, since |\psi| < 1 ensures that the term \frac{\psi^n}{\sqrt{5}} approaches zero and becomes negligible compared to the exponentially growing \frac{\phi^n}{\sqrt{5}}.^[14] This approximation reveals the exponential nature of the growth, with F_n = \Theta(\phi^n); more precisely, the natural logarithm satisfies \log F_n \approx n \log \phi - \log \sqrt{5}, highlighting the linear dependence on n in the exponent.^[14] For scale, the Fibonacci sequence grows exponentially with base \phi \approx 1.618, but far more slowly than the factorial n!, which follows Stirling's approximation n! \sim \sqrt{2 \pi n} \, (n/e)^n and thus exhibits super-exponential growth; for instance, F_{20} = 6765, while $20! \approx 2.43 \times 10^{18}.^[14] In algorithmic contexts, this asymptotic form provides tight bounds for the running time of procedures governed by Fibonacci-like recurrences, such as the naive recursive algorithm to compute F_n, which performs \Theta(\phi^n) additions and thus becomes impractical for large n due to the exponential scaling.^[31]

Ratio limits

One of the most remarkable properties of the Fibonacci sequence is the convergence of the ratio of consecutive terms to the golden ratio \phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887. Specifically, \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \phi.^[32] This limit holds because the sequence grows exponentially with base \phi, and the ratios stabilize as n increases, with early approximations such as \frac{F_5}{F_4} = \frac{5}{3} \approx 1.666 and \frac{F_{10}}{F_9} = \frac{55}{34} \approx 1.6176 drawing progressively closer to \phi. A rigorous proof of this convergence utilizes Binet's formula, F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}, where the contribution of the second term, divided by \sqrt{5}, has absolute value less than 0.5 for all n \geq 0 and diminishes rapidly to zero as n grows. Thus, \frac{F_{n+1}}{F_n} = \frac{\phi^{n+1} - (-\phi)^{-(n+1)}}{\phi^n - (-\phi)^{-n}} \cdot \frac{1/\sqrt{5}}{1/\sqrt{5}} simplifies asymptotically to \phi, since the negligible second terms vanish in the limit.^[32]^[33] This ratio's connection to \phi echoes historical geometric insights, as ancient Greek mathematicians, including Euclid in his Elements (circa 300 BCE), constructed regular pentagons where the diagonal-to-side ratio equals \phi exactly, implicitly approximating the same limit through successive polygonal divisions without knowledge of the Fibonacci sequence itself.^[34] Such constructions, used in architecture and art, prefigure the Fibonacci approximations by leveraging the pentagon's self-similar properties tied to \phi.^[35] Furthermore, the continued fraction expansion of \phi = [1; \overline{1,1,1,\dots}] consists of an infinite string of 1s, and its convergents are precisely the ratios \frac{F_{n+1}}{F_n}, which provide the best rational approximations to \phi among all fractions with denominators up to F_n. This linkage underscores the deep interplay between the Fibonacci sequence and the infinite, non-repeating nature of \phi's continued fraction.^[36]^[37]

Identities and Proofs

Combinatorial identities

One prominent combinatorial interpretation of the Fibonacci numbers arises in the context of tiling problems. The (n+1)th Fibonacci number F_{n+1} counts the number of distinct ways to tile a board of length n using tiles of length 1 (singles) and length 2 (dominoes). This can be established recursively: a tiling of an n-board either ends with a single, in which case the preceding n-1 board can be tiled in F_n ways, or ends with a domino, leaving an n-2 board tiled in F_{n-1} ways, yielding the relation F_{n+1} = F_n + F_{n-1}. A combinatorial bijection confirms this by directly enumerating the tilings, where each configuration corresponds uniquely to a sequence of singles and dominoes covering the board without overlaps or gaps.^[14] This tiling interpretation also provides a combinatorial proof for the identity F_{n+1} = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}. The term \binom{n-k}{k} represents the number of tilings of the n-board that use exactly k dominoes (covering $2kunits) andn-2ksingles (covering the remainingn-2kunits), for a total ofn-ktiles. The binomial coefficient arises from choosingkpositions for the dominoes among then-ktotal tiles in the sequence. Summing over all possiblek(from 0 to\lfloor n/2 \rfloor) exhausts all valid tilings, equaling the total F_{n+1}. An alternative proof by induction verifies the summation directly: the base cases hold for small n$, and assuming the identity for smaller values, the Fibonacci recurrence splits the sum accordingly.^[14] Another key combinatorial result is Zeckendorf's theorem, which states that every positive integer can be uniquely expressed as a sum of distinct Fibonacci numbers with no two consecutive indices. Formally, for any positive integer m, there exists a unique set of indices i_1 < i_2 < \cdots < i_r such that i_{j+1} \geq i_j + 2 for all j, and m = F_{i_1} + F_{i_2} + \cdots + F_{i_r}, where typically F_2 = 1, F_3 = 2, etc. This representation avoids the ambiguity of other greedy algorithms and has applications in coding and numeration systems. The theorem is proved by showing that the greedy choice of the largest possible non-exceeding Fibonacci number always yields non-consecutive terms, with uniqueness following from the property that F_{n+1} > \sum_{k=1}^{n-1} F_k.^[38]

Algebraic identities

The algebraic identities of the Fibonacci sequence encompass multiplicative and difference relations that connect terms without relying on summation or combinatorial interpretations. These identities reveal deep structural properties of the sequence and can be derived using methods such as mathematical induction or matrix representations.^[39] One of the most fundamental is Cassini's identity, which states that for any positive integer n,

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

This relation was first observed by the Italian astronomer Giovanni Domenico Cassini around 1680 while studying planetary motions, though it applies more broadly to the Fibonacci sequence.^[40] A proof by mathematical induction proceeds as follows: For the base case n=1, F_2 F_0 - F_1^2 = 1 \cdot 0 - 1^2 = -1 = (-1)^1, which holds (assuming the standard extension F_0 = 0). Assume the identity is true for n = k: F_{k+1} F_{k-1} - F_k^2 = (-1)^k. For n = k+1, compute F_{k+2} F_k - F_{k+1}^2 = (F_{k+1} + F_k) F_k - F_{k+1}^2 = F_{k+1} F_k + F_k^2 - F_{k+1}^2 = F_k^2 - F_{k+1} (F_{k+1} - F_k) = F_k^2 - F_{k+1} F_{k-1} = -(F_{k+1} F_{k-1} - F_k^2) = -(-1)^k = (-1)^{k+1}, confirming the step using the hypothesis and F_{k+1} - F_k = F_{k-1}.^[41]^[42] An alternative proof uses the matrix form of the Fibonacci sequence, where \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n. The determinant of the right-hand side is (-1)^n, and equating determinants gives F_{n+1} F_{n-1} - F_n^2 = (-1)^n.^[39] Cassini's identity generalizes to Catalan's identity, discovered by the Belgian mathematician Eugène Charles Catalan in 1879, which states that for integers n \geq r \geq 1,

F_{n+r} F_{n-r} - F_n^2 = (-1)^{n-r} F_r^2.

When r=1, this reduces to Cassini's identity. A matrix-based proof leverages the property that the determinant of the product of the Fibonacci matrix raised to powers n+r and n-r minus the square of the matrix to power n aligns with the form above, using the constant determinant (-1)^{n-r} and relating to F_r^2. Alternatively, induction on n for fixed r, with base cases verified directly and the inductive step using the recurrence to expand terms, confirms the relation.^[43]^[39] Another key relation is d'Ocagne's identity, formulated by the French mathematician Maurice d'Ocagne in 1891, which asserts that for integers m > n \geq 0,

F_m F_{n+1} - F_{m+1} F_n = (-1)^n F_{m-n}.

This identity highlights bilinear forms in Fibonacci numbers and can be proved using generating functions or matrix methods. For instance, expressing the left side as the determinant of a submatrix derived from the Fibonacci matrix powers yields the right side via the constant determinant property and the difference m-n. An inductive proof fixes n and inducts on m, using the recurrence to relate consecutive terms and reducing to known cases like Cassini's for the base.^[39]^[44]

Generating functions

The ordinary generating function for the Fibonacci sequence, defined by F_0 = 0, F_1 = 1, and F_n = F_{n-1} + F_{n-2} for n \geq 2, is the formal power series

G(x) = \sum_{n=0}^{\infty} F_n x^n.

This function encodes the entire sequence as coefficients of the powers of x.^[45] To derive G(x), substitute the recurrence relation into the series. Specifically,

G(x) = F_0 + F_1 x + \sum_{n=2}^{\infty} F_n x^n = 0 + x + \sum_{n=2}^{\infty} (F_{n-1} + F_{n-2}) x^n.

The sum splits into

\sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n = x \sum_{n=2}^{\infty} F_{n-1} x^{n-1} + x^2 \sum_{n=2}^{\infty} F_{n-2} x^{n-2} = x (G(x) - F_0) + x^2 G(x) = x G(x) + x^2 G(x),

yielding G(x) = x + x G(x) + x^2 G(x). Solving for G(x) gives

G(x) (1 - x - x^2) = x \implies G(x) = \frac{x}{1 - x - x^2},

valid within the radius of convergence |x| < 1/\phi \approx 0.618, where \phi = (1 + \sqrt{5})/2 is the golden ratio.^[45]^[46] The coefficient of x^n in G(x) directly yields F_n, as per the definition of the generating function. To extract a closed form, decompose the rational function via partial fractions. The denominator factors as $1 - x - x^2 = (1 - \phi x)(1 - \hat{\phi} x), where \hat{\phi} = (1 - \sqrt{5})/2. Thus,

\frac{x}{1 - x - x^2} = \frac{A}{1 - \phi x} + \frac{B}{1 - \hat{\phi} x}.

Solving gives A = 1 / \sqrt{5} and B = -1 / \sqrt{5}. Expanding as geometric series,

G(x) = \frac{1}{\sqrt{5}} \sum_{n=0}^{\infty} (\phi^{n} - \hat{\phi}^{n}) x^n,

so the coefficient is F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}, which is Binet's formula.^[46]^[47] An extension to exponential generating functions replaces powers with factorials in the coefficients: E(x) = \sum_{n=0}^{\infty} F_n \frac{x^n}{n!}. Using Binet's formula, this simplifies to

E(x) = \frac{1}{\sqrt{5}} \left( e^{\phi x} - e^{\hat{\phi} x} \right),

which highlights connections to exponential growth but is less commonly used for basic properties than the ordinary form.^[48]

Number Theory Properties

Divisibility rules

A key divisibility property of the Fibonacci sequence states that for positive integers m and n, \gcd(F_m, F_n) = F_{\gcd(m,n)}.^[49] This identity holds because the Fibonacci numbers form a strong divisibility sequence, where the GCD of terms depends solely on the GCD of their positions.^[50] A direct consequence is that F_m divides F_n if and only if m divides n.^[51] Thus, the positive divisors of F_n among the Fibonacci numbers are precisely F_k for each positive divisor k of n. For instance, F_3 = 2 divides F_6 = 8 because 3 divides 6, but F_3 = 2 does not divide F_5 = 5 since 3 does not divide 5.^[51] The smallest positive integer k such that F_k divides F_n is k=1, as F_1 = 1 divides every integer. This notion connects to the broader study of divisibility in the sequence, particularly the rank of appearance (or Fibonacci entry point) of an integer d, defined as the smallest positive integer k such that d divides F_k.^[52]

Fibonacci primes

A Fibonacci prime is a Fibonacci number F_n that is also a prime number. The sequence begins with the small primes F_3 = 2, F_4 = 3, F_5 = 5, F_7 = 13, F_{11} = 89, F_{13} = 233, F_{17} = 1597, F_{23} = 28657, and F_{29} = 514229.^[53] It is a known property that F_n can only be prime if n is prime, except for the case n=4, since composite indices greater than 4 yield composite Fibonacci numbers.^[53] As of November 2025, there are 37 confirmed Fibonacci primes, the largest being F_{201107} with 42,029 digits, verified via ECPP in September 2023.^[54] Larger candidates include probable primes such as F_{104911} (discovered in 2015, 21,925 digits). Ongoing computational efforts have identified 20 additional probable primes up to index 11,964,299, the most recent being F_{11964299} (approximately 2,500,000 digits), discovered on November 2, 2025, though full proofs for these remain pending due to their immense size.^[54] It is conjectured that infinitely many Fibonacci primes exist, supported by probabilistic heuristics indicating that the expected number diverges like \sum 1/n, akin to the density of primes themselves, though this remains unproven.^[53] Conversely, some analyses suggest the possibility of only finitely many, but no definitive resolution has emerged. Factoring large Fibonacci numbers poses significant challenges, as their exponential growth (approximately \phi^n / \sqrt{5}, where \phi is the golden ratio) results in numbers with millions of digits, requiring advanced algorithms like the elliptic curve method or general number field sieve; moreover, even when n is prime, F_n may have algebraic factors detectable via divisibility properties of the sequence.^[55] These difficulties have limited the verification of primality beyond modest indices relative to the sequence's rapid expansion. Historical discoveries of Fibonacci primes accelerated post-2000 through distributed computing projects, with notable finds including F_{2971} (1993, but confirmed later), F_{4723} (2001), and more recent ones like F_{104911} by Bouk de Water in 2015 and F_{201107} via collaborative efforts in 2023, highlighting the role of high-performance computing in extending the known list.^[55]

Pisano periods

The Pisano period, denoted \pi(n), for a positive integer n, is the length of the repeating cycle in the sequence of Fibonacci numbers taken modulo n. This periodicity arises because the Fibonacci recurrence is a linear relation, and there are only finitely many possible pairs of consecutive terms modulo n, ensuring the sequence must eventually repeat. Specifically, \pi(n) is the smallest positive integer k such that F_k \equiv 0 \pmod{n} and F_{k+1} \equiv 1 \pmod{n}, marking the return to the initial conditions (F_0, F_1) = (0, 1).^[56]^[57] For example, modulo 2, the sequence begins $0, 1, 1, 0, 1, 1, \dots and repeats every 3 terms, so \pi(2) = 3. Modulo 5, the sequence is $0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, \dots with period \pi(5) = 20. These periods, also called entry points z(n) in this context, provide the minimal k > 0 where the sequence resets to (0, 1) modulo n.^[56] Several properties govern Pisano periods. If n divides m, then \pi(n) divides \pi(m); for instance, since 17 divides 51, \pi(17) = 36 divides \pi(51) = 72. Additionally, \pi(n) is even for all n > 2. Known bounds include \pi(n) \leq 6n, with equality holding for n = 2 \times 5^k where k \geq 0. These properties stem from the structure of the Fibonacci sequence in the ring of integers modulo n and aid in understanding modular reductions of Fibonacci numbers.^[56]^[58] Pisano periods enable efficient cycle detection in algorithms for computing large Fibonacci numbers modulo n, avoiding exhaustive recurrence calculations by leveraging the repetition. In cryptography, they support methods like integer factorization, where the period of the product of two primes can be derived to aid in breaking down composite numbers.^[56]

Generalizations

Lucas sequences

Lucas sequences generalize the Fibonacci sequence and were introduced by the French mathematician Édouard Lucas in 1876 as a family of integer sequences defined by linear recurrences with integer parameters P and Q.^[59] The primary sequence, denoted U_n(P, Q), satisfies the recurrence relation

U_n = P U_{n-1} - Q U_{n-2}

for n \geq 2, with initial conditions U_0 = 0 and U_1 = 1.^[60] This formulation encompasses the Fibonacci sequence as the special case U_n(1, -1), where the recurrence simplifies to U_n = U_{n-1} + U_{n-2}, yielding the familiar terms 0, 1, 1, 2, 3, 5, ... .^[60] For integer values of P and Q with discriminant D = P^2 - 4Q > 0, the sequences produce integers analogous to Fibonacci numbers.^[61] Each Lucas sequence U_n(P, Q) has a companion sequence V_n(P, Q), defined by the same recurrence

V_n = P V_{n-1} - Q V_{n-2}

but with initial conditions V_0 = 2 and V_1 = P.^[60] In the Fibonacci case (P=1, Q=-1), V_n(1, -1) corresponds to the Lucas numbers, starting with 2, 1, 3, 4, 7, 11, ....^[61] These companion sequences often appear in identities alongside U_n, facilitating proofs and extensions of properties. Many identities for Lucas sequences mirror those of the Fibonacci sequence, preserving structural similarities while incorporating the parameters P and Q. For instance, the Cassini identity generalizes to U_{n+1} U_{n-1} - U_n^2 = -Q^{n-1} for the U_n sequence, and V_{n+1} V_{n-1} - V_n^2 = D Q^{n-1} for V_n, both reducing to the standard Fibonacci Cassini identity F_{n+1} F_{n-1} - F_n^2 = (-1)^n and the corresponding Lucas identity when P=1, Q=-1.^[60] Other common identities include doubling formulas like U_{2n} = U_n V_n, which parallel Fibonacci even-index relations.^[61] Lucas sequences admit Binet-like closed-form expressions using the roots of the characteristic equation x^2 - Px + Q = 0.^[61] Prominent examples include the Pell numbers, given by U_n(2, -1), which follow the recurrence U_n = 2U_{n-1} + U_{n-2} and generate the sequence 0, 1, 2, 5, 12, 29, ...; their companions V_n(2, -1) are the Pell-Lucas numbers.^[60] These sequences share divisibility properties and growth rates similar to Fibonacci numbers, with applications in number theory arising from their parametric flexibility.^[61]

Multidimensional variants

Multidimensional variants of the Fibonacci sequence extend the classical linear recurrence to higher-dimensional structures, such as graphs and lattices, where the counts of certain configurations follow generalized Fibonacci-like patterns. In graph theory, the number of perfect matchings (or domino tilings) in a 2×n grid graph equals the (n+1)th Fibonacci number, providing a combinatorial interpretation that generalizes to higher dimensions. For instance, tilings of a honeycomb strip—a two-dimensional lattice structure—yield sequences satisfying higher-order recurrences akin to tribonacci numbers, with closed-form formulas derived from transfer matrix methods. Similarly, hyperbolic tilings of the plane using triangles or heptagons with specific degrees produce Fibonacci numbers as the count of such tilings, illustrating spatial extensions beyond one-dimensional sequences. The tribonacci sequence represents a direct higher-order generalization, defined by the recurrence T_n = T_{n-1} + T_{n-2} + T_{n-3} for n \geq 4, with initial conditions T_0 = 0, T_1 = 0, T_2 = 1, yielding the sequence 0, 0, 1, 1, 2, 4, 7, 13, .... This sequence arises in combinatorial problems, such as the number of ways to tile a 1×n board with monomers and trimers, and exhibits properties like singular factorization of its infinite word, where singular words are defined based on the recurrence. Further generalizations to k-bonacci sequences, or k-generalized Fibonacci numbers, extend this to F_n^{(k)} = F_{n-1}^{(k)} + \cdots + F_{n-k}^{(k)} for n > k, with initial conditions F_1^{(k)} = \cdots = F_{k-1}^{(k)} = 0, F_k^{(k)} = 1. These sequences admit a Binet-style closed form involving the roots of the characteristic polynomial x^k - x^{k-1} - \cdots - 1 = 0, and they appear in applications like repdigit representations and summation identities. Vector forms of Fibonacci recurrences emerge in the study of lattice paths, where multidimensional paths on grids satisfy vector-valued recurrences analogous to the scalar Fibonacci case. For example, in two-dimensional lattices, the number of compound paths—compositions of steps avoiding certain patterns—follows distributions tied to Zeckendorf representations using Fibonacci numbers, with central limit theorems establishing Gaussian limiting behavior for path lengths. More broadly, projections from higher-dimensional integer lattices onto one dimension can generate quasiperiodic Fibonacci chains, as seen in quasicrystal models where the structure encodes multidimensional periodicity. These vector recurrences count lattice paths in d-dimensional spaces, generalizing the classical one-dimensional case to multivariate generating functions that satisfy Fibonacci-like relations. Recent developments in the 2020s have explored quantum and modular variants of these multidimensional extensions. In quantum computing, laser pulses patterned after the Fibonacci sequence have been used to induce a novel phase of matter in atomic systems, effectively creating a structure that behaves as if it has two time dimensions, with quasiperiodic properties extending classical multidimensional tilings to quantum settings.^[62] On the modular side, investigations into randomly initialized recurrences modulo m reveal new periodicities for Fibonacci-like sequences, generalizing Pisano periods to higher-dimensional or k-step variants and uncovering symmetries in their modular behavior.^[63]

Applications

Pure mathematics

The golden ratio \phi = \frac{1 + \sqrt{5}}{2} admits the infinite continued fraction expansion [\ 1; \overline{1}\ ] = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \cdots}}}, which is the simplest possible periodic continued fraction for an irrational number. The convergents to this expansion are precisely the ratios \frac{F_{n+1}}{F_n}, where F_n denotes the nth Fibonacci number, and these ratios satisfy \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \phi. This connection highlights the role of Fibonacci numbers in approximating irrational numbers via continued fractions, with the error bound |\phi - F_{n+1}/F_n| < 1/(F_n F_{n+1}) establishing their optimality among rational approximations.^[64]^[65] Fibonacci numbers appear in the study of elliptic curves through identities linking reciprocal sums and curve parameters. For instance, the elliptic curve y^2 = x^3 + x^2 - 2x - 1 yields an identity expressing the sum \sum_{n=1}^\infty \frac{(-1)^{n+1}}{F_{2n}} in terms of the curve's L-function at s=2, revealing algebraic dependencies between Fibonacci reciprocals and elliptic curve invariants. Similarly, L-functions associated with non-CM elliptic curves with non-trivial 2-torsion intersect with Fibonacci numbers, where the set of n such that the a_n coefficient is Fibonacci has asymptotic density zero. These links extend to modular forms, where the Fibonacci zeta function \zeta_F(s) = \sum_{n=1}^\infty F_n^{-s} relates to modular forms via criteria determining if a number is Fibonacci, and Fibonacci-Eisenstein series generate semi-modular forms using Fibonacci symmetries instead of partition functions.^[66]^[67]^[68]^[69] In partition theory, Fibonacci numbers enumerate restricted integer partitions, such as those into parts where no part repeats more than once and consecutive parts differ by at least 2, with the generating function tied to Fibonacci polynomials. q-analogues of Fibonacci numbers arise in set partition statistics over pattern-avoiding partitions, where the q-Fibonacci numbers qF_n(q) count partitions avoiding certain 3-2-1 patterns, satisfying q-analogues of classical Fibonacci identities like qF_{n+1}(q) = qF_n(q) + q^{n+1} F_{n-1}(q). These q-Fibonacci polynomials also connect to the Rogers-Ramanujan identities, providing finite versions through compositions and restricted growth functions in partition generating functions.^[70]^[71]^[72] The Zeckendorf representation uniquely expresses every positive integer as a sum of non-consecutive Fibonacci numbers, leading to the sum of Zeckendorf digits as an additive arithmetic function. Under the Erdős-Wintner theorem, the distribution of this digit sum follows a Gaussian law with mean and variance asymptotic to c \log n for some constant c > 0, but effective quantitative bounds on the Kolmogorov distance to normality remain an active research area, with open questions on the precise error terms in uniform estimates for the densities of fixed digit sums. A related unsolved problem concerns the exact asymptotic density of integers whose Zeckendorf digit sum equals a fixed value k, known to be zero but with unresolved finer rates of decay in the effective Erdős-Wintner framework for Zeckendorf expansions.^[73]^[74]

Computer science

The Fibonacci sequence appears prominently in computer science for efficient computation algorithms and data structures. A naive recursive approach to compute the nth Fibonacci number, defined by F(n) = F(n-1) + F(n-2) with base cases F(0)=0 and F(1)=1, leads to exponential time complexity of O(\phi^n), where \phi \approx 1.618 is the golden ratio, due to redundant subproblem calculations.^[31] This inefficiency arises from the branching recursion tree, where each call spawns two subcalls, resulting in approximately \phi^n operations.^[31] Dynamic programming addresses this by memoizing intermediate results, typically using an array to store F(0) to F(n), reducing the time complexity to O(n) with O(n) space, or optimized to O(1) space via iterative computation from the bottom up.^[75] This bottom-up method avoids recursion altogether, computing each value once in linear time.^[75] For even faster computation, matrix exponentiation represents the recurrence as a matrix multiplication: the vector \begin{pmatrix} F(n+1) \\ F(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}, allowing computation in O(\log n) time via exponentiation by squaring.^[75] This approach is particularly useful for large n, as it leverages efficient matrix powering algorithms.^[75] Pisano periods, the cycles in the Fibonacci sequence modulo m, enable optimizations for modular computations by precomputing the period length, avoiding full sequence generation.^[76] In data structures, Fibonacci heaps exploit Fibonacci numbers to achieve superior amortized performance for priority queue operations. Introduced by Fredman and Tarjan, a Fibonacci heap supports insert, decrease-key, and union in amortized O(1) time, with extract-min in amortized O(\log n), by maintaining a collection of heap-ordered trees linked in a root list, where the degree of trees bounds the number of children using Fibonacci properties to ensure lazy merging.^[77] The "Fibonacci" name derives from the analysis showing that a node with degree d has at least F_{d+2} descendants after consolidation, preventing excessive merging costs.^[77] These heaps improve the time complexity of algorithms like Dijkstra's shortest path from O((V+E) \log V) to O(E + V \log V).^[77] The sequence also informs coding techniques in algorithms. Fibonacci search, a divide-and-conquer method for sorted arrays, divides the search interval using Fibonacci numbers instead of halves, eliminating division operations and achieving O(\log n) time similar to binary search but with potentially fewer comparisons in non-uniform distributions.^[78] For instance, to search for a key in a sorted array of size n, the algorithm selects split points at indices F_{k-1} and F_{k-2} for the largest F_k \leq n+1, recursing on the appropriate subarray.^[78] In knapsack problems, the dynamic programming formulation for the unbounded variant mirrors the Fibonacci recurrence, where the optimal value dp for capacity w satisfies dp = \max(dp, dp[w - weight_i] + value_i) over items, solvable in O(nW) time, and special cases with Fibonacci-weighted items yield exact solutions via non-adjacent selections akin to Zeckendorf representations.^[79]

Nature and biology

The Fibonacci sequence manifests in phyllotaxis, the spatial arrangement of leaves, branches, and florets on plants, where organs often emerge at angles approximating 137.5°, known as the golden angle and roughly equal to 360° divided by the square of the golden ratio.^[80] This pattern optimizes packing and sunlight exposure, resulting in visible spirals whose counts are typically consecutive Fibonacci numbers, such as 34 and 55 in sunflower heads.^[80] In sunflowers (Helianthus annuus), these parastichies form interlocking spirals that efficiently fill the seed head.^[81] Similar Fibonacci spirals appear in the bracts of pinecones and the scales of pineapples, where overlapping structures create parastichy patterns with Fibonacci numbers, like 5 and 8 spirals in one direction and 8 and 13 in the other.^[82] These arrangements in conifers and bromeliads promote efficient seed dispersal and structural integrity.^[82] Over 90% of observed plant spirals follow Fibonacci patterns, though ancient fossils reveal non-Fibonacci variants in early land plants.^[82] The original Fibonacci sequence arose from a rabbit population model, where each mature pair produces a new pair monthly after a one-month maturation period, leading to exponential growth without mortality.^[83] However, this idealized scenario overlooks real-world limitations like death rates and resource constraints, making it unrealistic for sustained biological populations.^[83] Extensions incorporate survival and birth parameters into matrix models, allowing analysis of steady-state or declining dynamics in ecological contexts, such as bacterial or insect populations.^[83] In animal morphology, logarithmic spirals in shells and horns approximate Fibonacci growth, enabling proportional expansion while maintaining shape.^[84] The nautilus shell (Nautilus pompilius) exemplifies this with chambers forming a logarithmic spiral tied to the golden ratio, facilitating buoyancy control as the organism grows.^[84] Similarly, horns in species like goats and rams (Capra spp.) follow logarithmic spirals that support incremental keratin deposition without altering curvature.^[85] These patterns link to the golden ratio, optimizing structural efficiency in biological forms.^[86]

Other fields

The Fibonacci sequence and its associated golden ratio have influenced artistic compositions and architectural designs, where proportions approximating φ ≈ 1.618 are employed for aesthetic harmony. In art, Leonardo da Vinci incorporated the golden spiral, derived from successive Fibonacci rectangles, in works such as the Mona Lisa to guide focal points and balance.^[87] Similarly, modern interpretations, including tributes to Piet Mondrian's geometric abstractions, adapt Fibonacci spirals into grid-based patterns to evoke rhythmic progression and visual appeal.^[88] In architecture, the Parthenon's facade dimensions and column spacings reflect golden ratio proportions, a design principle attributed to the ancient Greek architect Phidias.^[87] The Great Pyramid of Giza also exhibits this ratio in its base-to-height measurements, suggesting intentional use for structural and visual stability.^[87] In finance, Fibonacci retracements serve as a tool in technical analysis to predict potential price reversals by identifying support and resistance levels based on key ratios from the sequence. Traders plot these levels between significant highs and lows on charts, with the 61.8% retracement (derived from ratios like 21/34) indicating a deep correction often preceding trend resumption, and the 38.2% level (e.g., 55/144) signaling shallower pullbacks.^[89] The 23.6% level (e.g., 8/34) marks minor retracements, while the non-Fibonacci 50% level is included for its observed market relevance.^[89] Empirical studies on U.S. energy stocks have tested these levels' predictive power, finding mixed profitability depending on market conditions and combined indicators.^[90] The Fibonacci sequence appears in musical structures, particularly in rhythm and scale designs that leverage its additive properties for natural progression. Composers like Béla Bartók used Fibonacci numbers to craft rhythms, as in Music for Strings, Percussion, and Celeste, where a percussion pattern follows 1, 1, 2, 3, 5, 8, 5, 3, 2, 1, 1 beats to create symmetrical tension and release.^[91] Karlheinz Stockhausen's Klavierstück IX employs time signatures and note groupings based on Fibonacci intervals, such as 13/8 bars and eighth-note counts like 1, 3, 6, 11, culminating in a coda of 87 notes.^[91] In scales, the octave's 13 keys and major scale's 8 notes align with Fibonacci ratios, while the white-to-black key proportion (8:5) approximates the golden ratio, influencing keyboard design and harmonic intervals in works by Chopin.^[91] Post-2020 applications include AI-driven pattern recognition, where shape-dependent Fibonacci-p patterns extract textural features from medical images for disease detection. In a 2022 study, these patterns, weighted by Fibonacci numbers and aligned to image shapes, achieved 98.44% accuracy in classifying COVID-19 versus viral pneumonia on chest radiographs using machine learning, outperforming some deep learning methods on small datasets.^[92] More recent advancements, as of 2024, incorporate Fibonacci sequences in machine learning for feature selection and network architectures; for example, the FiboNeXt model uses Fibonacci layering for Alzheimer's disease detection from MRI scans.^[93] In blockchain and cybersecurity, additive Fibonacci generators produce pseudorandom sequences for encryption and consensus protocols, with optimized structures ensuring long periods and high entropy. A 2022 analysis combined classical and modified Fibonacci generators to enhance randomness in cryptographic applications, reducing predictability in distributed systems like blockchains.^[94] By 2025, new cryptographic schemes utilize generalized Fibonacci sequences for blind signatures and self-invertible matrix-based encryption.^[95]^[96]

References

[1]
[PDF] Fibonacci Series, Golden Proportions, and the Human Biology
Jul 2, 2015 · Fibonacci sequences: The Fibonacci sequence was first recognized by the Indian Mathematician, Pingala (300-200 B.C.E.) in his published book ...
[2]
[PDF] The Fibonacci Sequence: Its History, Significance, and ... - CORE
In general, every nth Fibonacci number is divisible by the nth number in the Fibonacci sequence, or is divisible by (Garland, 1987, p. 69). Fibonacci numbers in ...
[3]
Fibonacci - Evansville
Fibonacci was probably the greatest genius of number theory during the 2000 years between Diophantus and Fermat. The sequence. 1, 1, 2, 3, 5, 8, 13, 21, 34, ...<|control11|><|separator|>
[4]
[PDF] Characteristics of Fibonacci-type Sequences - Whitman College
The Fibonacci sequence is a famous sequence of integers both in mathematics and in popular culture. It was introduced to the Latin-speaking world in 1202, in ...
[5]
[PDF] THE FIBONACCI SEQUENCE IN NATURE
The Fibonacci sequence is named after its discoverer Leonardo Pisano Bogollo, who was a famous Italian mathematician otherwise known as Fibonacci. The Fibonacci ...
[6]
[PDF] The So-called Fibonacci Numbers in Ancient and Medieval India
Hemacandra also comments on his own rule, as did Gopala on Virahanka's rule, concluding with “Statement-l. 2, 3,5,8. 13, 21, 34 and in this way, afterwards ...
[7]
[PDF] A Note on the Golden Mean and Fibonacci Numbers - arXiv
The Fibonacci numbers are described by several Indian mathematicians in the centuries following Pingala as being produced by the rule F(n+1) = F(n) + F(n-1).
[8]
Fibonacci (1170 - 1250) - Biography - MacTutor History of Mathematics
Johannes of Palermo, another member of Frederick II's court, presented a number of problems as challenges to the great mathematician Fibonacci. Three of these ...Missing: recognizing | Show results with:recognizing
[9]
Leonard of Pisa (Fibonacci) and Arabic Arithmetic - Muslim Heritage
Jan 14, 2005 · This is the first textbook to introduce into the West, Arabic numerals, which have place value, and thus the first book to describe the methods of doing ...Missing: exposure | Show results with:exposure
[10]
How modern mathematics emerged from a lost Islamic library - BBC
Dec 7, 2020 · In his early 20s, Fibonacci traveled to the Middle East, captivated by ideas that had come west from India through Persia. When he returned to ...Missing: exposure | Show results with:exposure
[11]
[PDF] On the origin of the Fibonacci Sequence - MacTutor
Mar 23, 2014 · This has motivated historians to associate the origin of the Fibonacci sequence with Muslim scholarship in the middle ages. The intent of this ...
[12]
3.6. An Introduction to Recurrence Relations - OpenDSA
A recurrence relation defines a function by means of an expression that includes one or more (smaller) instances of itself.
[13]
Fibonacci Number -- from Wolfram MathWorld
### Recursive Definition of the Fibonacci Sequence
[14]
https://mathworld.wolfram.com/FibonacciNumber.html
[15]
Fibonacci's Rabbits
Fibonacci considers the growth of an idealized (biologically unrealistic) rabbit population, assuming that: a single newly born pair of rabbits (one male, one ...
[16]
Jacques Binet (1786 - 1856) - Biography - MacTutor
Binet is remembered for 'Binet's form' of the Fibonacci numbers. He discovered this formula in 1843 which gives a direct value of the Fibonacci number F n F ...Missing: original | Show results with:original
[17]
[PDF] 4 Linear Recurrence Relations & the Fibonacci Sequence
For us, the important case is the Fibonacci sequence: the characteristic equation is λ. 2 − λ − 1 = 0 =⇒ λ = 1 ±. √. 5. 2. = φ, ˆφ where φ = 1+. √. 5. 2 is the ...
[18]
[PDF] 23.2 General Theory of Recurrence Relations
In some sense, we're done. Once we've specified the recurrence relation and the initial conditions, all subsequent terms are uniquely determined.
[19]
Identities about Fibonacci numbers - UNL Math
Binet's Formula for the Fibonacci numbers. Let V~ -- P(1 + 5)/2 = 1.618 .. be ... n Fn = V~ P-rounded to the nearest integer 5. Fibonacci number bases ...
[20]
Fibonacci Q-Matrix -- from Wolfram MathWorld
The Fibonacci Q-matrix is the matrix defined by Q=[F_2 F_1; F_1 F_0]=[1 1; 1 0], where F_n is a Fibonacci number.Missing: form | Show results with:form
[21]
[PDF] ma 351 lecture notes: formulae for fibonacci numbers using the ...
Apr 16, 2024 · The first few Fibonacci numbers are given by. 0,1,1,2,3,5,8,13,21,34,ททท , and this is sequence A000045 in the Online Encyclopedia of Integer ...<|control11|><|separator|>
[22]
[PDF] FIBONACCI NUMBERS: AN APPLICATION OF LINEAR ALGEBRA 1 ...
For a diagonal matrix, it is very easy to calculate its powers. The sequence of Fibonacci numbers Fn 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... is defined ...
[23]
[PDF] Calculating Fibonacci (and related) numbers efficiently - cs.wisc.edu
Jan 5, 2004 · The Fibonacci sequence F = (1,1,2,3,5,...), where F0 = F1 = 1 and Fn+2 is given by the recurrence Fn+2 = Fn+1 +Fn, represents a wide range ...
[24]
[PDF] The Fibonacci Numbers - Whitman College
Introduction. The term “Fibonacci numbers” is used to describe the series of numbers gener- ated by the pattern. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
[25]
Finding a Formula for the Fibonacci Numbers - Dr Ron Knott
Aug 29, 2023 · We have only defined the nth Fibonacci number in terms of the two before it: the n-th Fibonacci number is the sum of the (n-1)th and the (n-2)th.
[26]
Binet's Formula -- from Wolfram MathWorld
It was derived by Binet in 1843, although the result was known to Euler, Daniel Bernoulli, and de Moivre more than a century earlier.
[27]
Representation of Integers as Sums of Fibonacci and Lucas Numbers
Fibonacci numbers of negative indices can be defined in a natural way and Binet's formula also holds true for all n ∈ Z . Note that F − n = ( − 1 ) n + 1 F n ...
[28]
Lucas Number -- from Wolfram MathWorld
### Binet's Formula for Lucas Numbers and Relation to Fibonacci
[29]
Binet's Formula by Induction
Binet's formula that we obtained through elegant matrix manipulation, gives an explicit representation of the Fibonacci numbers that are defined recursively.
[30]
[PDF] Computing Fibonacci numbers efficiently - Williams College
Sep 25, 2025 · The maximum number of nodes in a binary tree with depth n is 2n −1, so T(n) = O(2n). However, we also need to find a lower bound to claim that ...<|control11|><|separator|>
[31]
[PDF] Fibonacci Numbers and the Golden Ratio - HKUST Math Department
Prove Binet's formula (5.6) by mathematical induction. 2. Use Binet's formula to prove the limit lim n→∞. Fn+1/Fn = Φ. 3. Use the linearization formulas. Φn ...
[32]
The Golden Ratio and Fibonacci - The Math Doctors
Jan 26, 2021 · Together, these are used in the formula for the Fibonacci sequence: F[n] = (Phi^n - (-phi)^n) / sqrt(5). It gets confusing after a while ...<|control11|><|separator|>
[33]
Pentagons - American Mathematical Society
The length of each diagonal of a regular pentagon with side length 1 equals the golden ratio. 1 + 5 2. Proof. Let x denote the length of each diagonal, as shown ...
[34]
[PDF] Golden Ratio and Fibonacci sequence in PentaGonal constRuctions ...
The Golden Ratio appears in pentagon parts, and the Fibonacci sequence, linked to the Golden Ratio, was used in medieval pentagon approximations. The diagonals ...
[35]
The golden ratio, Fibonacci numbers and continued fractions - NRICH
Feb 1, 2011 · This article poses such questions in relation to a few of the properties of the Golden Ratio and Fibonacci sequences and proves these properties.Missing: expansion | Show results with:expansion
[36]
The Golden section ratio: Phi - Dr Ron Knott
Aug 30, 2023 · We will get all the ratios of successive Fibonacci numbers as values which get closer and closer to Φ. You can find out more about continued ...
[37]
Zeckendorf Representation -- from Wolfram MathWorld
### Zeckendorf's Theorem Statement
[38]
[PDF] FIBONACCI NUMBERS AND IDENTITIES 1. Introduction A function ...
The purpose of this section is to list a few identities we found in the literature that can be proved by applying Lemmas 2.1 and 2.2. 4.1. d'Ocagne's Identity.
[39]
[PDF] Fibonacci -numbers and a generalization of Cassini formula
Cassini developed a theory of the remarkable geometrical figures known under the name of Cassini ovals. The mathematical identity that connects three adjacent.
[40]
[PDF] the cassini identity and its relatives - The Fibonacci Quarterly
The Cassini identity for Fibonacci numbers is Fn-1Fn+1 - F2n = (-1)^n. It is a common mathematical fact.
[41]
[PDF] Fibonacci summation identities arise from Catalan's identity
We show how Catalan's identity for the Fibonacci numbers can be leveraged to construct a large family (with some eccentric members) of summation identities ...
[42]
Cassini, d'Ocagne, and Vajda identities for n-step Fibonacci numbers
Jan 17, 2022 · In this paper, we extend results from \cite{jabo} on n-determinants by proving that Cassini, d'Ocagne, Catalan and Vajda identities may be extended to hold for ...
[43]
[PDF] Generating Functions - MIT
Nov 9, 2006 · Solving for F(x) gives the generating function for the Fibonacci sequence: F(x) = x + xF(x) + x2F(x). ⇒. F(x) = x. 1 − x − x2. Sure enough ...
[44]
https://arxiv.org/abs/2201.06269
[45]
Binet's Formula via Generating Functions
A proof of Binet's formula for Fibonacci numbers using generating functions and the method of partial fractions.
[46]
[PDF] Exponential generating functions for Fibonacci identities
Here, we use exponential generating functions to establish some Fibonacci and Lucas identities. 2. THE EXPONENTIAL FUNCTION AND EXPONENTIAL GENERATING FUNCTIONS.
[47]
GCD of Fibonacci Numbers
\mbox{gcd}(f_{m},f_{n})=f_{\text{gcd}(m,n)}. The proof will be based on four lemmas; before stating and proving those I'd like to give an example. Doing that ...Missing: F_gcd( | Show results with:F_gcd(
[48]
[PDF] The Fibonacci Sequence - Berkeley Mathematics
Let p 6= 2, 5 be a prime and suppose that Fp contains a square root of 5. Then Fn is divisible by p if and only if (ϕ/ψ)n = 1 in Fp where ϕ and ψ are distinct ...
[49]
[PDF] When does F divide Fn? A combinatorial solution
Jun 23, 2003 · One of the oldest theorems about Fibonacci numbers states that for Fm > 1,. Fm|Fn if and only if m|n. (1). Indeed, Edouard Lucas proved in his ...Missing: F_m F_n source
[50]
[PDF] Fixed points of the order of appearance in the Fibonacci sequence
... Fibonacci entry point). There are several results about z(n) in the literature. For instance, z(n) < ∞ for all n ≥ 1. The proof of this fact is an ...
[51]
The Prime Glossary: Fibonacci prime
n = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757, 35999, and 81839 ...
[52]
Fibonacci Number - The Prime Pages
Fibonacci Number. The Prime Pages keeps a list of the 5000 largest known primes, plus a few each of certain selected archivable forms and classes. These forms ...
[53]
The Fibonacci Sequence Modulo M, by Marc Renault
One period of the Fibonacci sequence mod m will always contain either 1, 2, or 4 zeros, no matter what the modulus is. Proof. We know U^{\alpha} \equiv \mu I \ ...
[54]
Pisano Period -- from Wolfram MathWorld
The sequence of Fibonacci numbers {F_n} is periodic modulo any modulus m (Wall 1960), and the period (mod m ) is the known as the Pisano period pi(m) ...
[55]
The Mathematical Magic of the Fibonacci Numbers - Dr Ron Knott
Aug 29, 2023 · So if n divides m which we write as n | m then Pisano(n) | Pisano(m). Using the last result, if we find the prime factors of n, n = p1a1 p2a ...
[56]
[PDF] Introduction to Lucas Sequences
Dec 14, 2017 · The sequence {un}n∈N and its companion {vn}n∈N are called Lucas sequences. In 1876 E. Lucas introduced such sequences in the case A,B ∈ Z, and ...
[57]
https://mathworld.wolfram.com/PisanoPeriod.html
[58]
Lucas Sequence -- from Wolfram MathWorld
The sequences are called Lucas sequences, where the definition is usually extended to include U_(-1)=(a^(-1)-b^(-1))/(ab)=(-1)/(ab)=-1/Q.<|separator|>
[59]
Golden Ratio -- from Wolfram MathWorld
The golden ratio, also known as the divine proportion, golden mean, or golden section, is a number often encountered when taking the ratios of distances in ...Missing: ancient | Show results with:ancient
[60]
The Most Irrational Number - AMS :: Feature Column from the AMS
The golden mean satisfies the equation x2 - x - 1 = 0, so its continued fraction expansion is the simplest of all: g = 1+11+11+11+… Its convergents are 1, 2, 3 ...
[61]
[PDF] The Fibonacci sequence and an elliptic curve
In this note, we introduce an identity on infinite series that involves the reciprocal Fibonacci numbers. The identity was discovered from an elliptic curve, ...
[62]
[PDF] L-Functions of Elliptic Curves and Fibonacci Numbers
We prove that if E is non-CM and has non-trivial 2-torsion, then the set of positive integers n such that 1an1 is a Fibonacci number has asymptotic density 0. 1 ...Missing: modular | Show results with:modular
[63]
[PDF] The Fibonacci zeta function and modular forms - David Lowry-Duda
Our key fact for relating the Fibonacci numbers to modular forms is the following criterion for determining whether a number N is Fibonacci. Lemma A ...
[64]
[2108.00840] Semi-modular forms from Fibonacci-Eisenstein series
Aug 2, 2021 · Here we construct a family of Eisenstein-like series to produce semi-modular forms, using symmetries related to Fibonacci numbers instead of partitions.
[65]
Set partition statistics and q-Fibonacci numbers - ScienceDirect.com
We show that the distribution over Π n ( 13 / 2 ) enumerates certain integer partitions, and the distribution over Π n ( 13 / 2 , 123 ) gives q -Fibonacci ...
[66]
[PDF] Set partition statistics and q-Fibonacci numbers
Aug 21, 2006 · Abstract. We consider the set partition statistics ls and rb introduced by Wachs and White and investigate their distribution over set ...
[67]
(PDF) q-Fibonacci Polynomials and the Rogers-Ramanujan Identities
Aug 7, 2025 · We derive some formulas for the Carlitz q-Fibonacci polynomials Fn(t) which reduce to the finite version of the Rogers-Ramanujan identities ...
[68]
[PDF] On the Variation of the Sum of Digits in the Zeckendorf Representation
For r ≥ 0 and d ∈ Z, we consider µ(r)(d), the density of integers n ∈ N for which the sum of digits increases by d when r is added to n.
[69]
Improvement of effective Erdős–Wintner theorem for Zeckendorf ...
In their effective Erdős–Wintner theorem for Zeckendorf expansions, Drmota and the author obtained a uniform Kolmogorov bound with an error term that involves T ...
[70]
Fast Computation of the Fibonacci sequence in Arbitrary Precision
Sep 23, 2023 · We explore various methods for computing the Fibonacci numbers, including the classic method, the Matrix exponentiation method, and the fast-doubling method.<|separator|>
[71]
[PDF] Pisano Periods: A Comparison Study
May 6, 2019 · The Pisano period, denoted π(n), is the period during which the Fibonacci sequence repeats after reducing the original sequence modulo n.Missing: bounds | Show results with:bounds
[72]
Fibonacci heaps and their uses in improved network optimization ...
In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the ...
[73]
[PDF] Fibonacci numbers and Computer algorithms
A function f is unimodal in an interval [a, b] if ƒ has a unique maximum x。 in the interval, and ƒ is strictly increasing to the left of xo and strictly ...
[74]
Dynamic Programming using Knapsack Problem and Fibonacci ...
Jul 6, 2024 · The naive recursive implementation of the Fibonacci sequence has a time complexity of O(2^n). This is because each call to fibonacci(n) results ...Missing: approximation | Show results with:approximation
[75]
Noise and Robustness in Phyllotaxis | PLOS Computational Biology
The most common phyllotactic patterns can be described using spirals, numbers from the Fibonacci sequence and the golden angle. This rich mathematical structure ...
[76]
Novel Fibonacci and non-Fibonacci structure in the sunflower
May 1, 2016 · This citizen science study evaluates the occurrence of Fibonacci structure in the spirals of sunflower (Helianthus annuus) seedheads.
[77]
Fossil study challenges long-held theory on Fibonacci spirals found ...
Jun 16, 2023 · A 3D model of a 407-million-year-old plant fossil has overturned thinking on the evolution of leaves. The research has also led to fresh insights about ...
[78]
https://people.sc.fsu.edu/~inavon/5420a/fibonacci.pdf
[79]
Spiral Form of the Human Cochlea Results from Spatial Constraints
Aug 8, 2017 · The nautilus shell is a perfect biological example of a logarithmic Fibonacci spiral. Correspondingly, logarithmic is also the relation ...
[80]
A Mathematical Analysis of Animal Horns - Bioengineering Hyperbook
The logarithmic spiral was first observed as an “equiangular” spiral by Thompson D'Arcy, as illustrated by the iconic spiral of Nautilus pompilius shell (D'Arcy ...Missing: sources | Show results with:sources
[81]
[PDF] Examples Of The Golden Ratio You Can Find In Nature
Snail shells and nautilus shells follow the logarithmic spiral, as does the cochlea of the inner ear. It can also be seen in the horns of certain goats, and the ...
[82]
[PDF] The Golden Ratio: Mathematics in Nature and Art
Sep 20, 2020 · In this paper I seek to define the Golden Ratio and explore the ratio's history and its connection with the Fi- bonacci Sequence.
[83]
Fibonacci Sequence in Art - Using the Fibonacci Theory in Art
Jul 15, 2022 · The Fibonacci sequence is a mathematical formula that suggests that each number is equal to the sum of the two numbers that precede it.The Rule of Thirds · Examples of the Fibonacci... · Other Examples of the...
[84]
Understanding Fibonacci Retracements and Ratios for Trading ...
Fibonacci retracements help technical traders predict potential market movements by identifying likely support and resistance levels on stock charts.Missing: credible | Show results with:credible
[85]
are Fibonacci retracements profitable? - PMC - PubMed Central
This paper investigates the role of Fibonacci retracements levels, a popular technical analysis indicator, in predicting stock prices of leading U.S. energy ...Missing: credible | Show results with:credible
[86]
[PDF] The Golden Ratio and Fibonacci Sequence in Music
May 8, 2021 · Popular musical theorist, Ernő Lendvai, was one of the first authors to discuss how the golden ratio and Fibonacci sequence were used in the ...
[87]
Automated Detection of COVID-19 Cases on Radiographs using ...
The main advantage of shape-dependent Fibonacci -p patterns is the encoding of the textural patterns aligned in different directions and shapes in the image all ...Missing: post- | Show results with:post-
[88]
Combined Pseudo-Random Sequence Generator for Cybersecurity
Dec 11, 2022 · In this article, we have optimized the structures of the classical additive Fibonacci generator and the modified additive Fibonacci generator when they work ...