Fibonacci Numbers

What are the Fibonacci numbers?

The Fibonacci numbers are the sequence in which every number from the third on is the sum of the two before it, starting from 0 and 1. In symbols F_0=0, F_1=1, F_n=F_n-1+F_n-2 (n\ge2). The first terms are

and F_20=6765, F_30=832 040, F_50=12 586 269 025. Some books start at F_1=F_2=1 and skip F_0; the numbers are the same, so check which convention a source uses.

A rule that defines each term from earlier ones is a recurrence, and this one is linear (the terms are only added, never multiplied together) and of order two (it looks back two places), which is why two starting values are needed. Running it backward gives F_-1=1, F_-2=-1, F_-3=2, and so on, with signs that alternate.

Where the name comes from. Leonardo of Pisa, called Fibonacci, put the sequence in his book Liber Abaci (1202) in a problem about rabbits: a pair has a new pair every month, and a new pair starts to have babies in its second month. Starting with one pair, how many pairs are there after a year? After 1,2,3,5,8,… the answer is 377 pairs, which is F_14. In general there are F_n+2 pairs after n months. The sequence is far older, though: Indian scholars studying the rhythms of poetry described it centuries earlier (see the history below).

Move the slider below to read the exact value of F_n for n up to 120, together with the ratio of neighbors and a first test of a famous formula.

What do the Fibonacci numbers count?

Whenever a counting problem can be split by "what is the last piece?" into two smaller copies of itself, the answer is a Fibonacci number. Take the stairs. Let s_n be the number of ways to climb n stairs taking one or two at a time. The last step was either a 1 (leaving n-1 stairs to climb before it, s_n-1 ways) or a 2 (leaving n-2, s_n-2 ways), so s_n=s_n-1+s_n-2 with s_1=1 and s_2=2. That is the Fibonacci recurrence shifted by one place: s_n=F_n+1, s_10=F_11=89.

The same argument counts many things: - Tilings. The number of ways to cover a strip of length n with squares of length 1 and dominoes of length 2 is F_n+1. Pingala's counts of rhythms made of short and long syllables are the same problem. - Strings. The binary strings of length n with no two 1s in a row number F_n+2: for n=3 they are 000,001,010,100,101, five of them, F_5. The same number counts the subsets of \1,\dots,n\ with no two consecutive numbers. - Rabbits. F_n+2 pairs after n months, as above. - Pascal's triangle. The sums along the shallow diagonals are Fibonacci numbers: C(5,0)+C(4,1)+C(3,2)=1+4+3=8=F_6, where C(n,k) are the binomial coefficients, and in general F_n+1=\sum_kC(n-k,k).

Compositions. Writing n as an ordered sum of 1s and 2s is the stairs problem again: 4=1+1+1+1, 4=1+1+2, 4=1+2+1, 4=2+1+1 and 4=2+2: five ways, F_5. This is why the Fibonacci numbers appear in so many counting exercises, and why the dynamic programming example "climbing stairs" is a Fibonacci computation in disguise (see the section on computing below).

Is there a formula for the nth Fibonacci number?

Yes: Binet's formula F_n=(φ^n-\psi^n)/(√5), where φ=(1+√5)/(2) and \psi=(1-√5)/(2) are the two roots of x^2=x+1. Here is why. Look for solutions of the recurrence of the form F_n=r^n. Then r^n=r^n-1+r^n-2, and dividing by r^n-2 gives r^2=r+1, r=(1±√5)/(2). So φ^n and \psi^n both satisfy the recurrence, and so does every combination Aφ^n+B\psi^n (the recurrence is linear). Choose A and B to match the starting values: F_0=0 gives A+B=0, and F_1=1 gives Aφ+B\psi=1. Since φ-\psi=√5, the solution is A=(1)/(√5)=-B, which is Binet's formula (known earlier to Euler and de Moivre; Jacques Binet published it in 1843).

What the two numbers are. φ=1.6180339887… is the golden ratio, and \psi=1-φ=-\frac1φ=-0.6180339887… has absolute value below 1, so \psi^n shrinks quickly and alternates in sign. For n\ge0 we have \left|(\psi^n)/(√5)\right|\le\frac1√5<\frac12, so F_n is the integer nearest to (φ^n)/(√5): for n=10, (φ^10)/(√5)=55.0036…, which rounds to F_10=55.

The ratio of neighbors. From the formula, F_n+1-φ F_n=\psi^n exactly, so (F_n+1)/(F_n)-φ=(\psi^n)/(F_n)≈((-1)^n)/(√5 F_n^2). The ratio therefore alternates around φ (1,2,1.5,1.667,1.6,1.625,1.615,…) and gets there quickly: it gains about 2\log_10φ≈0.42 decimal places per step, so (F_31)/(F_30) already agrees with φ to ten decimals. Compare the irrational numbers that are hardest to approximate by fractions: the fractions (F_n+1)/(F_n) are exactly the best ones for φ, and they are the slowest-converging continued fraction there is.

A warning for programmers. Computing round(phi ** n / sqrt(5)) with ordinary floating-point numbers is correct for n\le70 and wrong from n=71 (308 061 521 170 130 instead of 308 061 521 170 129): a double has only about 16 digits (see the spacing of floats), and φ^71 must be known to better than one part in 10^15. For exact values use integers.

Which identities do the Fibonacci numbers satisfy?

The Fibonacci numbers satisfy dozens of identities, and a few short proofs explain most of them.

Sums. Since F_k=F_k+2-F_k+1, adding for k=1 to n telescopes: F_1+F_2+…+F_n=F_n+2-F_2=F_n+2-1. For n=10 the ten terms 1,1,2,3,5,8,13,21,34,55 add up to 143, and F_12-1=143 too. In the same way F_1+F_3+…+F_2n-1=F_2n and F_2+F_4+…+F_2n=F_2n+1-1. For squares, a picture of rectangles of sides F_k× F_k stacked into a F_n× F_n+1 rectangle proves F_1^2+F_2^2+…+F_n^2=F_nF_n+1, 1+1+4+9+25=40=5·8.

The matrix proof. Put Q=\beginpmatrix1&1\\1&0\endpmatrix. Then Q\beginpmatrixF_n\\F_n-1\endpmatrix=\beginpmatrixF_n+1\\F_n\endpmatrix, so by induction Q^n=\beginpmatrixF_n+1&F_n\\F_n&F_n-1\endpmatrix. Two facts follow at once. Taking determinants, \det Q=-1 gives Cassini's identity F_n-1F_n+1-F_n^2=(-1)^n. And Q^2n=(Q^n)^2 compares entries to give the doubling formulas F_2n=F_n (2F_n+1-F_n), F_2n+1=F_n^2+F_n+1^2. For example F_20=F_10(2F_11-F_10)=55·123=6765.

The missing square. Cassini with n=6 says F_5F_7-F_6^2=5·13-8^2=1. That is the old puzzle of cutting an 8×8 square (area 64) into four pieces and rearranging them into a 5×13 rectangle (area 65): the pieces cannot fill the rectangle exactly, and along the long diagonal there is a thin sliver gap of area 1 that the eye does not see, because consecutive Fibonacci numbers have a ratio so close to φ.

Divisibility. Consecutive Fibonacci numbers are coprime: a common divisor of F_n+1 and F_n divides F_n+1F_n-1-F_n^2=±1. More generally \gcd(F_m,F_n)=F_\gcd(m,n). So F_m divides F_n whenever m divides n (for example F_6=8 divides F_12=144), every third Fibonacci number is even, every fourth is a multiple of 3 and every fifth a multiple of 5. The proof uses F_m+n=F_m+1F_n+F_mF_n-1, which turns \gcd(F_m,F_n) into \gcd(F_m-n,F_n): the Euclidean algorithm runs on the subscripts.

Pick n below. Each identity has its left side built the long way and its right side from the short formula, with exact numbers, and the last line checks the gcd rule.

How do you compute Fibonacci numbers fast?

The recurrence invites a recursive function, and that is the slowest way to compute a Fibonacci number; a loop is fast enough for most purposes, and fast doubling is the way to reach very large n.

Plain recursion. fib(n) = fib(n-1) + fib(n-2) recomputes the same values over and over. The number of calls C_n satisfies C_n=C_n-1+C_n-2+1 with C_0=C_1=1, which solves to C_n=2F_n+1-1≈(2φ^n+1)/(√5). That is 21 891 calls for n=20, 331 160 281 for n=40, 40 730 022 147 for n=50 (about 41 seconds at a billion calls a second) and about 1.1×10^21 for n=100 (some 36 000 years). The cost grows like φ^n, an exponential, which is the example used in the section on recurrences in the Big-O article.

Memoization and the loop. Remember each value once computed and the calls drop to 2n-1. Better, keep only the last two values in a loop: n-1 additions and no recursion (Python's default limit of 1000 nested calls stops a recursive version near n=1000).

Fast doubling. The identities F_2k=F_k(2F_k+1-F_k) and F_2k+1=F_k^2+F_k+1^2 get (F_2k,F_2k+1) from (F_k,F_k+1), so reading the bits of n from the top, one doubling step per bit gives (F_n,F_n+1) with 3\lceil\log_2n\rceil multiplications. This is exponentiation by squaring applied to the matrix Q of the last section, with the redundant entries dropped. To get F_10^6 it takes 20 steps instead of a million additions.

The numbers get long. F_n has \lfloor n\log_10φ-\log_10√5\rfloor+1 digits, about 0.209 n: F_100 has 21, F_1000 has 209, F_10^5 has 20 899 and F_10^6 has 208 988. So an addition is not one step but about 0.2 n digit operations, and the loop really costs about n^2 digit operations. Fast doubling also wins here, since it multiplies a few very long numbers. Note also that fixed-size integers overflow early: a 32-bit signed integer stops at F_46=1 836 311 903 and a double stops being exact at F_78 (see binary numbers).

Slide n below to compare the four methods and read the first and last digits of the exact answer.

How do you write a number as a sum of Fibonacci numbers?

Zeckendorf's theorem says that every positive integer is a sum of Fibonacci numbers from 1,2,3,5,8,13,… in exactly one way if no two of them may be neighbors in that list. For example 100=89+8+3=F_11+F_6+F_4, 12=8+3+1, 4=3+1. (The list starts at F_2=1, because F_1 is the same number.) Dropping the rule of no neighbors, the same number usually has several sums: 100 can be written in 9 ways with different Fibonacci numbers, such as 89+8+3 and 55+34+8+3, and only one of them has no neighbors.

The greedy method finds it. Take the largest Fibonacci number not above N, subtract it, and repeat on the rest. The rest is smaller than the previous Fibonacci number (otherwise a larger one would have fitted), so the next term is never the neighbor of the one just taken.

Why it is unique. The telescoping sums of the identities section show that the largest sum of non-neighboring Fibonacci numbers below F_k is F_k-1+F_k-3+F_k-5+…=F_k-1 (for k=7: 8+3+1=12=13-1). So a no-neighbors sum for N cannot leave out the largest Fibonacci number F_k\le N: without it the sum would be at most F_k-1<N. The largest term is forced, and the argument repeats on the rest.

Fibonacci digits. Write a 1 for each Fibonacci number used and a 0 for each skipped, from the largest down to F_2: 100 becomes 1000010100 (positions F_11 to F_2), and no two 1s are ever next to each other. It is a number system with Fibonacci numbers as place values, just as binary has powers of two. Because 11 never occurs inside a code word, writing an extra 1 after the last digit marks the end of the word: the Fibonacci code that can store a sequence of numbers without separators, a code that survives a damaged bit better than many others. Ordinary binary uses about \log_2N digits and the Fibonacci system about \log_φ N, about forty-four percent more.

Type a number below to see its Zeckendorf sum, the string of Fibonacci digits next to the binary form and the count of other sums; the table under it lists 1 to 20.

What is the Pisano period?

The remainders of the Fibonacci numbers modulo m repeat with a period called the Pisano period π(m), which lets you find F_n\bmod m for an enormous n by reducing n first. Modulo 10 the sequence is 0,1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,9,9,8,7,5,2,7,9,6,5,1,6,7,3,0,3,3,6,9,5,4,9,3,2,5,7,2,9,1, 0,1,1,… and it starts again after 60 numbers: π(10)=60. So the last digit of F_n is the last digit of F_n\bmod60.

Why the sequence repeats. Look at the pairs (F_n\bmod m, F_n+1\bmod m). There are only m^2 possible pairs, so a pair must come back, and from then on everything repeats, since a pair determines the next. The step (a,b)→(b,a+b) can also be undone, (b,c)→(c-b,b), so the first pair to come back is the very first one, (0,1): the sequence is purely periodic, with no lead-in. In fact π(m)\le6m.

Some values: π(2)=3, π(3)=8, π(4)=6, π(5)=20, π(6)=24, π(7)=16, π(10)=60, π(100)=300, π(1000)=1500, and π(10^k)=15·10^k-1 for k\ge3. So the last two digits repeat every 300 numbers and the last three every 1500.

A worked example. What is the last digit of F_10^18? Since 10^18\bmod60=40 and F_40=102 334 155, it is 5. And with fast doubling and a remainder taken at each step, F_10^18\bmod(10^9+7)=209 783 453 comes out in about sixty steps; no sequence of a quintillion terms is ever written down. This is the standard contest and cryptography use of Fibonacci numbers: "give the answer modulo 10^9+7".

Choose a modulus below, see the remainders and the period, and then find F_n\bmod m for an n of up to thirty digits.

Where do Fibonacci numbers really appear in nature and in algorithms?

The golden ratio φ and the Fibonacci numbers show up in a few places that can be explained, and in many places that are myths.

The golden rectangle. A rectangle with sides in the ratio φ:1 has a special property: cut off a square and what remains is a smaller rectangle with the same ratio, since φ^2=φ+1 makes (1)/(φ-1)=φ. Squares with sides 1,1,2,3,5,8,… fit together into the spiral on this article's cover, and quarter circles drawn inside them approximate the golden spiral. It is an approximation: a true golden spiral grows by φ every quarter turn, while Fibonacci's squares grow by a ratio only close to it.

Seeds, cones and pineapples. In a sunflower head, a pine cone or a pineapple, the seeds or scales sit on two families of spirals, one turning each way, and the two counts are very often neighbors in the Fibonacci sequence: 34 and 55 (or 55 and 89) in sunflower heads, 8 and 13 in many pine cones. There is a reason. A plant that adds each new seed at a fixed turn from the previous one wastes space unless the turn is a fraction of the circle that cannot be well approximated by simple fractions, and (1)/(φ^2) is the hardest such number (see rational approximations of irrationals). The turn is the golden angle (360^\circ)/(φ^2)≈137.5^\circ, and it produces spirals counted by neighboring Fibonacci numbers. This is a model by Helmut Vogel (1979); real plants follow it often, not always.

What is a myth. Claims that the Great Pyramid, the Parthenon, the Mona Lisa or the proportions of the human body were designed with the golden ratio rest on selective measuring or on no evidence, and the shell of a nautilus is a logarithmic spiral that is not golden. A number on a petal count is a Fibonacci number partly because small numbers are everywhere. Treat such statements with suspicion, and ask which measurement was taken and where.

In algorithms. Fibonacci numbers do real work in computing. Euclid's algorithm for the gcd is slowest on consecutive Fibonacci numbers: \gcd(F_n+1,F_n) takes exactly n-1 division steps, and Gabriel Lamé proved in 1844 that the number of steps never exceeds five times the number of digits of the smaller number (often called the first analysis of the running time of an algorithm). Fibonacci search and the golden-section search (see the optimization article) shrink a bracket by the golden ratio. Fibonacci heaps get their name from the Fibonacci numbers that bound the size of their trees.

How do you compute Fibonacci numbers in Python, JavaScript and C++?

Use arbitrary-precision integers (Python's int, JavaScript's BigInt), a loop for ordinary n and fast doubling for huge n, and take remainders at every step when only F_n\bmod m is needed. The first Python program counts the calls of the plain recursion, then computes the same number with a memo, a loop and fast doubling, and checks Binet's formula. A warning: since Python 3.11 an integer of more than 4300 digits cannot be turned into text unless you raise the limit with sys.set_int_max_str_digits, which is why the program prints the number of bits of F_10^6 and not its digits.

from functools import lru_cache
from math import sqrt


def fib_naive(n):
    """Returns (F(n), number of calls) for the plain recursion."""
    if n < 2:
        return n, 1
    a, ca = fib_naive(n - 1)
    b, cb = fib_naive(n - 2)
    return a + b, ca + cb + 1


@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)


def fib_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


def fib_doubling(n):
    """Returns (F(n), F(n + 1)) with F(2k) = F(k)(2F(k+1) - F(k)) and F(2k+1) = F(k)^2 + F(k+1)^2."""
    if n == 0:
        return 0, 1
    a, b = fib_doubling(n // 2)
    c = a * (2 * b - a)
    d = a * a + b * b
    return (d, c + d) if n % 2 else (c, d)


print(fib_naive(20), fib_memo(20), fib_loop(20), fib_doubling(20)[0])
print(fib_naive(25)[1], 2 * fib_loop(26) - 1)               # the calls: 2F(n+1) - 1
print(fib_loop(100), len(str(fib_doubling(1000)[0])), len(str(fib_doubling(20000)[0])))
print(fib_doubling(10 ** 6)[0].bit_length())                 # a number of 208 988 digits, in a blink

phi = (1 + sqrt(5)) / 2
for n in (10, 70, 71, 72):
    print(n, round(phi ** n / sqrt(5)), fib_loop(n))         # Binet in doubles goes wrong at 71
# (6765, 21891) 6765 6765 6765
# 242785 242785
# 354224848179261915075 209 4180
# 694241
# 10 55 55
# 70 190392490709135 190392490709135
# 71 308061521170130 308061521170129
# 72 498454011879265 498454011879264

def zeckendorf(n):
    """Greedy: the largest Fibonacci number that fits, again and again."""
    fibs = [1, 2]
    while fibs[-1] <= n:
        fibs.append(fibs[-1] + fibs[-2])
    out = []
    for f in reversed(fibs):
        if f <= n:
            out.append(f)
            n -= f
    return out


def pisano(m):
    """The period of F(n) mod m: walk the pairs of remainders until (0, 1) returns."""
    a, b, p = 0, 1 % m, 0
    while True:
        a, b = b, (a + b) % m
        p += 1
        if (a, b) == (0, 1 % m):
            return p


def fib_mod(n, m):
    """F(n) mod m for a huge n, by fast doubling with the remainder taken at each step."""
    def go(k):
        if k == 0:
            return 0, 1 % m
        a, b = go(k // 2)
        c = a * (2 * b - a) % m
        d = (a * a + b * b) % m
        return (d, (c + d) % m) if k % 2 else (c, d)
    return go(n)[0]


print(zeckendorf(100), zeckendorf(2026))
print([pisano(m) for m in (2, 3, 5, 10, 100, 1000)])
print(fib_mod(10 ** 18, 10), fib_mod(10 ** 18, 10 ** 9 + 7), fib_mod(10 ** 18, 1000))
print(fib_mod(10 ** 18 % 60, 10), fib_mod(10, 10 ** 9 + 7))  # reduce n by the period first
# [89, 8, 3] [1597, 377, 34, 13, 5]
# [3, 8, 20, 60, 300, 1500]
# 5 209783453 875
# 5 55

const fib = (n) => { let a = 0n, b = 1n; for (let i = 0; i < n; i++) [a, b] = [b, a + b]; return a }
fib(100)                                      // 354224848179261915075n

// fast doubling: F(2k) = F(k)(2F(k+1) - F(k)), F(2k+1) = F(k)^2 + F(k+1)^2
const pair = (n) => {
  if (n === 0n) return [0n, 1n]
  const [a, b] = pair(n >> 1n)
  const c = a * (2n * b - a), d = a * a + b * b
  return n & 1n ? [d, c + d] : [c, d]
}
pair(1000000n)[0].toString().length           // 208988

// plain numbers stop being exact: the first b that is not a safe integer is wrong in its last digit
let a = 0, b = 1, n = 0
while (Number.isSafeInteger(b)) { [a, b] = [b, a + b]; n++ }
;[n, a, b]                                    // [78, 8944394323791464, 14472334024676220]; the true F(79) ends in ...221

// Binet in doubles
const phi = (1 + Math.sqrt(5)) / 2
let k = 0
while (BigInt(Math.round(phi ** k / Math.sqrt(5))) === fib(k)) k++
k                                             // 71

// F(n) mod m for a huge n
const fibMod = (n, m) => {
  const go = (j) => {
    if (j === 0n) return [0n, 1n % m]
    const [x, y] = go(j >> 1n)
    const c = (x * ((2n * y - x) % m + m)) % m, d = (x * x + y * y) % m
    return j & 1n ? [d, (c + d) % m] : [c, d]
  }
  return go(n)[0]
}
;[fibMod(10n ** 18n, 10n), fibMod(10n ** 18n, 1000000007n)]   // [5n, 209783453n]

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
  int a = 0, b = 1;
  for (int i = 0; i < 40; i++) {
    int t = a + b;
    a = b;
    b = t;
  }
  printf("%d\n", a);                                   // F(40); F(47) no longer fits in an int

  int ms[4] = {2, 5, 10, 100};
  for (int k = 0; k < 4; k++) {
    int m = ms[k], x = 0, y = 1 % m, p = 0;
    do {
      int t = (x + y) % m;
      x = y;
      y = t;
      p++;
    } while (!(x == 0 && y == 1));
    printf("%d %d\n", m, p);                           // the Pisano period
  }

  int u = 233, v = 144, steps = 0;                     // Euclid's algorithm on F(13) and F(12)
  while (v != 0) {
    int t = u % v;
    u = v;
    v = t;
    steps++;
  }
  printf("%d %d\n", u, steps);                         // gcd 1 after n - 1 = 11 divisions
  return 0;
}

/* output:
102334155
2 3
5 20
10 60
100 300
1 11
*/

Where do the Fibonacci numbers come from?

The Fibonacci numbers were found in India as a count of poetic rhythms, centuries before Fibonacci's rabbits.

• About 200 BC. The Indian scholar Pingala, in his work on Sanskrit metre, counted the patterns of short and long syllables, which leads to the numbers 1,2,3,5,8,….
• About 700 and 1150. Virahanka stated the rule that each count is the sum of the two before it, and Hemachandra gave it again; Gopala had done so around 1135.
• 1202. Leonardo of Pisa, known as Fibonacci, published Liber Abaci with the rabbit problem and the first terms up to 377. The book mainly taught Europeans the Hindu-Arabic numerals.
• 1730–1843. Abraham de Moivre and Leonhard Euler knew the closed formula; Jacques Binet published it in 1843.
• 1844. Gabriel Lamé used the Fibonacci numbers to bound the steps of Euclid's algorithm.
• 1870s. Édouard Lucas studied the sequence in depth, introduced the companion Lucas numbers 2,1,3,4,7,11,…, used them to test whether large numbers are prime, and gave the sequence the name Fibonacci.
• 1939–1972. Edouard Zeckendorf proved the theorem on sums of Fibonacci numbers (published in 1972, after Gerrit Lekkerkerker's 1952 paper).
• 1963. The Fibonacci Association and its journal, the Fibonacci Quarterly, were founded.
• 1970. Yuri Matiyasevich used the exponential growth of Fibonacci numbers to complete the proof that Hilbert's tenth problem, a general method for solving equations in integers, has no solution.

What mistakes do people make with Fibonacci numbers?

The most common mistakes with Fibonacci numbers are the nine below, each with the correct statement.

Practice: test your understanding

These questions mix everything above. A wrong answer costs nothing here: read the hint and try again.

Summary: Fibonacci numbers at a glance

• Definition: F_0=0, F_1=1, F_n=F_n-1+F_n-2; F_n+1 counts the ways to climb n stairs with steps of 1 or 2.
• Binet: F_n=(φ^n-\psi^n)/(√5), the integer nearest to (φ^n)/(√5); the ratio (F_n+1)/(F_n) is φ+(\psi^n)/(F_n); in doubles it fails at n=71.
• Identities: \sum F_k=F_n+2-1, \sum F_k^2=F_nF_n+1, Cassini (-1)^n, doubling, \gcd(F_m,F_n)=F_\gcd(m,n); all follow from Q=\beginpmatrix1&1\\1&0\endpmatrix.
• Computing: recursion 2F_n+1-1 calls, memo 2n-1, loop n-1 additions, fast doubling 3\lceil\log_2n\rceil multiplications; F_n has 0.209 n digits.
• Zeckendorf: every positive integer is a unique sum of non-neighboring Fibonacci numbers, found greedily; the Fibonacci code is built on it.
• Pisano: F_n\bmod m repeats with period π(m)\le6m; π(10)=60, so reduce n first.
• Nature and algorithms: golden angle 137.5^\circ in seed spirals, Euclid's worst case; the pyramid and painting claims are myths.
• Code: big integers, a loop, fast doubling, remainders at every step.

Glossary: key terms

Fibonacci number

A term of the sequence 0, 1, 1, 2, 3, 5, 8, 13, … in which each term is the sum of the two before it.

Golden ratio

The number 1 plus the square root of 5, over 2, about 1.618, the limit of the ratio of consecutive Fibonacci numbers.

Binet's formula

The closed form for the nth Fibonacci number as the difference of the nth powers of the two roots of x squared equals x plus 1, divided by the square root of 5.

Cassini's identity

The identity that F(n−1) times F(n+1) minus F(n) squared equals minus 1 to the power n.

Fast doubling

A method that finds F(n) with about log n big multiplications by getting F(2k) and F(2k+1) from F(k) and F(k+1).

Zeckendorf representation

The unique way to write a positive integer as a sum of Fibonacci numbers, no two of which are neighbors in the sequence.

Pisano period

The length of the cycle of the Fibonacci numbers modulo m, written pi of m; for m equal to 10 it is 60.

Phyllotaxis

The arrangement of leaves, seeds or scales on a plant, often in spirals whose counts are neighboring Fibonacci numbers.

Lucas numbers

The companion sequence 2, 1, 3, 4, 7, 11, … with the same recurrence as the Fibonacci numbers but different starting values.

Frequently asked questions

References

1. Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1994). Concrete Mathematics (2nd ed.), section 6.6: Fibonacci Numbers. Addison-Wesley.
2. Donald E. Knuth (1997). The Art of Computer Programming, Volume 1 (3rd ed.), section 1.2.8: Fibonacci Numbers. Addison-Wesley.
3. Thomas Koshy (2001). Fibonacci and Lucas Numbers with Applications. Wiley.
4. Laurence Sigler (2002). Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation. Springer.
5. Parmanand Singh (1985). The so-called Fibonacci numbers in ancient and medieval India. Historia Mathematica 12.
6. George Markowsky (1992). Misconceptions about the golden ratio. The College Mathematics Journal 23(1).
7. Gabriel Lamé (1844). Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendus de l'Académie des Sciences 19.

Related articles

• Geometric Sequences and Series: Ratio, Sums and Growth: Geometric sequences and series explained: common ratio, the n-th term, finite and infinite sums, geometric means, compound interest and decay, with practice.
• Big-O Notation: Big-O notation explained: the definition, growth rates from O(1) to O(n!), counting steps in code, best and worst case, recurrences and the Master theorem.
• Irrational Numbers: Definition, Examples, Proofs and Approximations: Irrational numbers explained: why √2 is irrational, which roots are, sums and products, π, e, transcendental numbers and fraction approximations, with practice.
• Arithmetic Sequences and Series: Formulas, Sums and Examples: Arithmetic sequences and series explained: common difference, the n-th term, the sum formula, Gauss’s trick, arithmetic means and word problems, with practice.